Title: An Axiomatic Approach to Algebrization
Speaker: Russell Impagliazzo, University of California, San Diego
Date: Wednesday, March 11, 2009 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Starting with Baker, Gill, and Solovay, oracle constructions have been used to show that ``relativizing techniques'' cannot resolve many complexity issues, such as $P vs. NP$. However, many results in complexity, particularly those using algebraic methods, do not relativize. Recently, Aaronson and Wigderson introduced a new form of barrier for this class of techniques, called algebrization. An algebrization of a containment between classes is a containment of one class relative to any oracle within the other class relative to an algebraic extension of the oracle. They showed that while almost all of the known containments and strict inclusions algebrize, most of the open problems in complexity do not.
One interpretation of this work is that the arithmetization method may be near its limits. However, it is unclear how to formalize algebrization of more complicated complexity statements than collapses or separations, and whether the algebrizing statements are, e.g., closed under \emph{modus ponens}; so it is conceivable that several algebrizing premises could imply (in a relativizing way) a non-algebrizing conclusion. In this paper, we propose an axiomatic approach to algebrization, which complements and clarifies the above. We consider a new axiom, \emph{Arithmetic Checkability}, which intuitively says that all $\NP$ languages have verifiers that are efficiently computable low-degree polynomials (over the integers). Arithmetic checkability is easily proven true using standard arithmetic techniques (and is implicit in earlier work), but is not relativizing. We say that a result is algebrizing in our sense if it follows from Arithmetic Checkability by relativizing techniques. While provability from Arithmetic Checkability does not capture ``all known techniques'', our results indicate that it captures a large subset of them that can intuitively be called ``arithmetic interpolation techniques.'' More precisely, using a construction due to Fortnow, we show that arithmetic checkability holds relative to arbitrarily powerful oracles. We also show that most of the algebrizing collapses and separations from AW08 such as $\IP=\PSPACE$, $\NP \subset \ZKIP$ if one-way functions exist, $\MA\text{-}\EXP\not\subset \P/\poly$, etc., are provable from Arithmetic Checkability.
On the other hand, many of the open complexity questions (including most of those shown to require non-algebrizing techniques in \cite{AW08}), such as ``$\P$ vs.\$\NP$'', ``$\NP$ vs. $\BPP$'', etc., are independent from Arithmetic Checkability. Arithmetic Checkability is also insufficient to prove one known result, $\NEXP=\MIP$ (although relative to an oracle satisfying Arithmetic Checkability, $\NEXP^O$ restricted to poly-length queries is contained in $\MIP^O$, mirroring a similar result by Aaronson and Wigderson).
Joint work with Valentine Kabanets, Simon Fraser University and Antonina Kolokolova, Memorial U. of Newfoundland.