Allender, EricEricAllenderDas, BireswarBireswarDas2025-08-302025-08-302017-10-0110.1016/j.ic.2017.04.0042-s2.0-85019010794http://repository.iitgn.ac.in/handle/IITG2025/22386We 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.trueGraph Isomorphism | Minimum Circuit Size Problem | NP-intermediate problem | Statistical Zero KnowledgeArticle109026512-8October 201738arJournal23WOS:000412282400002