DIMACS Theoretical Computer Science Seminar

Title: Zero Knowledge and Circuit Minimization

Speaker: Eric Allender, Rutgers University

Date: Wednesday, November 19, 2014 11:00-12:00pm

Location: CoRE Bldg, Room 301A, Rutgers University, Busch Campus, Piscataway, NJ

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
CSP (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.

See: http://www.math.rutgers.edu/~sk1233/theory-seminar/S14/