What are natural examples of non-relativizable proofs?

What are natural examples of non-relativizable proofs?

• As I understand it, a proof that P=NP or P≠NP would need to be non-relativizable (as in recursion theory oracles). Virtually all proofs seem to be relativizable, though. What are good examples of non relativizable proofs, of the sort that a P=NP/P≠NP proof would need to be, that are not trivial or contrived? (I am not a recursion theorist, so please pardon the lack of citations.) [EDIT: better http://mathoverflow.net/questions/55933/what-proofs-cannot-be-relativized post]

• Answer:

  As Steven notes, the canonical example is $\mathsf{IP} = \mathsf{PSPACE}$. This collapse does not relativize, in the sense that there is an oracle $A$, subject to which $\mathsf{IP}^A \ne \mathsf{PSPACE}^A$. The intuition why the known proof of this result avoids the relativization barrier is that it uses arithmetization (Yonatan alluded to this in a comment): an interactive protocol for the $\mathsf{PSPACE}$-complete problem TQBF is given by considering an extension of a quantified boolean formula to a low-degree polynomial over a suitably large field. If we are given a relativized boolean formula (with oracle gates), such an extension does not exist. There is a refinement of the relativization barrier -- algebrization -- due to http://www.scottaaronson.com/papers/alg.pdf. Generically, the arithmetization technique is not enough to circumvent the algebrization barrier. A complexity class inclusion $\mathsf{C} \subseteq \mathsf{D}$ algebrizes if for any oracle $A$ and any extension $\tilde{A}$ of $A$ to low-degree polynomials over a finite field, $\mathsf{C}^A \subseteq \mathsf{D}^{\tilde{A}}$. A separation $\mathsf{C} \not \subset \mathsf{D}$ algebrizes if for all $A$, and all extensions $\tilde{A}$, $\mathsf{C}^{\tilde{A}} \not \subset \mathsf{D}^{A}$. Aaronson and Wigderson show that $\mathsf{IP} = \mathsf{PSPACE}$ algebrizes, but many other results, including $\mathsf{NP} \not \subset \mathsf{P}$, do not. A recent example of a technique that does not algebrize or relativize is http://www.stanford.edu/~rrwill/acc-lbs.pdf that $\mathsf{NEXP} \not \subset \mathsf{ACC}$. The separation does not algebrize: there is an oracle $A$ and a low-degree extension $\tilde{A}$ such that $\mathsf{NEXP}^{\tilde{A}} \subset \mathsf{ACC}^A$. Intuitively the reason why the proof avoids the barrier is that it relies on the existence of a faster-than-trivial satisfiability algorithm for $\mathsf{ACC}$ circuits, and the algorithm uses non-relativizing and non-algebrizing properties of such circuits. Ryan notes in the paper that all known faster-than-trivial satisfiability algorithms break down when oracles or algebraic extensions of oracles are added. There is also an interesting approach to understanding relativization through logic. In an old manuscript, http://www.cs.berkeley.edu/~vazirani/pubs/relativizing.ps define a system of axioms such that the relativizing results are exactly those that follow from the axioms, while non-relativizing results are independent from the system. A paper by http://www.cs.sfu.ca/~kabanets/papers/act-full.pdf does something similar for algebrization by introducing an additional axiom to the ones defined by Arora, Impagliazzo and Vazirani. They show that most known non-relativizing results follow from their axioms, while P vs NP, among others, is independent of them. Apologies if I got something wrong, I am not quite an expert.