Allender, EricEricAllenderDas, BireswarBireswarDas2025-08-302025-08-302014-01-01[9783662444641]10.1007/978-3-662-44465-8_32-s2.0-84906218370http://repository.iitgn.ac.in/handle/IITG2025/21284We 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. © 2014 Springer-Verlag Berlin Heidelberg.falseConference Paper1611334925-32201423cpBook Series4