News Archives

[Colloquium] Zero Knowledge and Circuit Minimization

March 26, 2015

Watch Colloquium:

MOV FILE

  • Date: Thursday, 3/26/15
  • Time: 11:00 AM - 12:15 PM
  • Place: Mechanical Engineering, Room 218

Speaker: Eric Allender, ACM 
Title: Zero Knowledge and Circuit Minimization

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:
http://ftp.cs.rutgers.edu/pub/allender/szk.mcsp.pdf

About the speaker:
Eric Allender is a Fellow of the ACM, and is the Editor-in-Chief of ACM
Transactions on Computation Theory. He got his PhD from Georgia Tech in
1985, and has been at Rutgers University ever since, serving as chair of
the CS department from 2006 to 2009.