Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR14-068 | 27th June 2014 13:35

Zero Knowledge and Circuit Minimization

RSS-Feed




Revision #1
Authors: Eric Allender, Bireswar Das
Accepted on: 27th June 2014 13:35
Downloads: 2603
Keywords: 


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

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.


Paper:

TR14-068 | 5th May 2014 04:16

Zero Knowledge and Circuit Minimization


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

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.



ISSN 1433-8092 | Imprint