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 ... more >>>