For roughly four decades, two of the best-studied problems in NP that are not known to be in P or to be NP complete have been:
* Graph Isomorphism, and
* MCSP (the Minimum Circuit Size Problem).
Yet there had been no theorem, relating the complexity of these two problems to each other.
Until now.
We give a simple argument -- drawing on the connection between MCSP and time-bounded Kolmogorov
complexity -- showing that not only Graph Isomorphism, but every problem in the complexity class SZK
(Statistical Zero Knowledge) is BPP reducible to MCSP.
Joint work with Bireswar Das.