Alternation-Trading Proofs, Linear Programming, and Lower Bounds

Ryan Williams
A fertile area of recent research has demonstrated concrete polynomial time lower bounds for solving natural hard problems on restricted computational models. Among these problems are Satisfiability, Vertex Cover, Hamilton Path, $\text{MOD}_6\text{-SAT}$, Majority-of-Majority-SAT, and Tautologies, to name a few. The proofs of these lower bounds follow a certain proof-by-contradiction strategy that we call {\em alternation-trading}. An important open problem is to determine how powerful such proofs can possibly be. We propose a methodology for studying...