Revision #1 Authors: Eric Allender, Bireswar Das

Accepted on: 27th June 2014 13:35

Downloads: 1883

Keywords:

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.

TR14-068 Authors: Eric Allender, Bireswar Das

Publication: 5th May 2014 04:17

Downloads: 2835

Keywords:

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.