Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > NP-INTERMEDIATE PROBLEM:
Reports tagged with NP-Intermediate Problem:
TR14-068 | 5th May 2014
Eric Allender, Bireswar Das

Zero Knowledge and Circuit Minimization

Revisions: 1

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 RP^MCSP.

This is the first theorem relating the computational power of Graph Isomorphism and MCSP, despite the long history these ... more >>>




ISSN 1433-8092 | Imprint