CSAIL Event Calendar: Previous Series

A New Barrier in Complexity Theory

Speaker: Scott Aaronson , MIT, CSAIL
Date: September 11 2007
Time: 4:15PM to 5:15PM
Location: 32-155
Host: Madhu Sudan, MIT

Any resolution of the P versus NP problem will have to overcome two barriers: relativization and natural proofs. Yet over the last decade, we have seen circuit lower bounds (for example, that PP does not have linear-size circuits) that overcome both barriers simultaneously. So the question arises of whether there is a third barrier to progress on the central questions in complexity theory.

In this talk we present such a barrier, which we call "algebraic relativization" or "algebrization." The idea is that, when we relativize some complexity class inclusion, we should give the simulating machine access not only to an oracle A, but also to the low-degree extension of A over a finite field or ring. We show that, while the results IP=PSPACE and MIP=NEXP fail to relativize, they nevertheless algebrize. On the other hand, we also show that any proof of P!=NP (or even P=BPP, or NEXP not in P/poly) would require non-algebrizing techniques, of which we currently have not a single example.

We also exhibit a surprising connection between algebrization and communication complexity. Using this connection, we give an MA-protocol for the Inner Product function with O(sqrt(n) log(n)) communication, and a communication complexity conjecture whose truth would imply P!=NP.

Joint work with Avi Wigderson.

See other events that are part of Theory Colloquium Fall 2007

See other events happening in September 2007