Skip to content Skip to navigation

Zero Knowledge and Circuit Minimization

Zero Knowledge and Circuit Minimization

Author Name: 

Eric Allender and Bireswar Das

Publication Type: 
Conference Publications
Publication Date: 
August, 2014
Best paper award, MFCS 2015
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.