Speaker: Antonina Kolokolova, Memorial University
Title: Axiomatic approach to complexity barriers
Abstract:
The main questions in complexity theory such as P vs. NP remain unresolved. Moreover, on a meta-level, there are several results that state that certain classes of techniques cannot be used to resolve these questions. A classic example of such "barrier" result is the relativization of Baker, Gill and Solovay'75: the statement that no technique such as diagonalization which is insensitive to access to extra information (oracles) can resolve the P vs. NP and similar questions. A more recent result along these lines is the algebrization barrier of Aaronson and Wigderson'2008, which shows that a large class of non-relativizing techniques such as arithmetization similarly cannot resolve the main open problems. Such barrier results resemble independence from a logical theory, however, even for relativization this similarity was not studied much, except for an unpublished paper by Arora, Impagliazzo and Vazirani.
Here, I will talk about their approach and how we extend it to capture algebrization. Our framework avoids using different oracles on the two sides of inclusions/separations, and allows for more complex statements, while formalizing most of AW'08 positive and negative results. We also show that there is a known non-algebrizing complexity statement: NEXP=MIP.
Based on joint work with Impagliazzo and Kabanets, in particular our STOC'09 paper.