Are there canonical non-relativizing techniques?

Question

In a lot of domains, there are canonical techniques which everybody working in the field should master. For example, for logspace reductions, the "bit trick" for composition consisting of not constructing the full output of the composed function, but always asking to recompute the result for every bit of output, permitting to keep logspace constraints.

My question is about non-relativizing techniques. Do theoricians have outlined some fundamental non-relativizing operations, or is there a different trick for each known non-relativizing proof ?

Answer 1

There's really only one "flagship" non-relativizing technique: namely, arithmetization (the technique used in the proofs of IP=PSPACE, MIP=NEXP, PP⊄SIZE(n^k), MA_EXP⊄P/poly, and several other results).

However, the proof that all NP languages have computational zero-knowledge proofs (assuming one-way functions exist), due to Goldreich, Micali, and Wigderson, used a different non-relativizing technique (namely, the symmetries of the 3-COLORING problem).

Arora, Impagliazzo, and Vazirani argued that even "local checkability," the property of NP-complete problems used in the proof of the original Cook-Levin Theorem (as well as the PCP Theorem), should count as a non-relativizing technique (though Lance Fortnow wrote a paper arguing the opposite). The sticking point is whether it makes sense to relativize the complexity class of "locally checkable problems."

The pebbling arguments used in results from the 1970s such as TIME(n)≠NTIME(n) have been put forward as another example of a non-relativizing technique.

For more, you might want to check out my algebrization paper with Wigderson, and especially the references therein. We had to pretty much catalogue the existing non-relativizing techniques in order to figure out which ones were and weren't encompassed by the algebrization barrier.

Addendum: I just realized that I forgot to mention measurement-based quantum computing (MBQC), which was recently used to great effect by Broadbent, Fitzsimons, and Kashefi to obtain quantum complexity theorems (such as QMIP = MIP*, and BQP = MIP with entangled BQP provers and BPP verifier) that most likely fail to relativize.