TY - JOUR
TI - Zero Knowledge and Circuit Minimization
DO - https://doi.org/doi:10.7282/T38K7CJT
AU - Allender, Eric
AU - Das, Bireswar
PY - 2017
T2 - Information and Computation
VL -
IS -
SP - 2
EP - 8
AB - 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
KW - Graph Isomorphism
KW - Minimum Circuit Size Problem
KW - NP-Intermediate Problem
KW - Statistical
Zero Knowledge
LA - English
ER -