ECCC-Report TR14-068https://eccc.weizmann.ac.il/report/2014/068Comments and Revisions published for TR14-068en-usFri, 27 Jun 2014 13:35:51 +0300
Revision 1
| Zero Knowledge and Circuit Minimization |
Eric Allender,
Bireswar Das
https://eccc.weizmann.ac.il/report/2014/068#revision1We 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.Fri, 27 Jun 2014 13:35:51 +0300https://eccc.weizmann.ac.il/report/2014/068#revision1
Paper TR14-068
| Zero Knowledge and Circuit Minimization |
Eric Allender,
Bireswar Das
https://eccc.weizmann.ac.il/report/2014/068We 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.Mon, 05 May 2014 04:17:24 +0300https://eccc.weizmann.ac.il/report/2014/068