Skip to content Skip to navigation
Seminar
11/19/2014 11:00 am
CoRE A(Room 301)

Zero Knowledge and Circuit Minimization

Eric Allender, Rutgers University

Organizer(s): Swastik Kopparty and Shubhangi Saraf

Abstract

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.