Zero knowledge and circuit minimization

Eric Allender, Bireswar Das

Research output: Contribution to journalArticlepeer-review

16 Scopus citations

Abstract

We show that every problem in the complexity class SZK (Statistical Zero Knowledge) is efficiently reducible to the Minimum Circuit Size Problem (MCSP). In particular Graph Isomorphism lies in RPMCSP. This is the first theorem relating the computational power of Graph Isomorphism and MCSP, despite the long history these problems share, as candidate NP-intermediate problems.

Original languageEnglish (US)
Pages (from-to)2-8
Number of pages7
JournalInformation and Computation
Volume256
DOIs
StatePublished - Oct 2017

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Keywords

  • Graph Isomorphism
  • Minimum Circuit Size Problem
  • NP-intermediate problem
  • Statistical Zero Knowledge

Fingerprint

Dive into the research topics of 'Zero knowledge and circuit minimization'. Together they form a unique fingerprint.

Cite this