Trinh Huynh: Hardness amplification for polynomial threshold proof systems

Using known results from multiparty number-on-forehead communication complexity, we exhibit a simple hardness amplification method that converts any t-CNF formula of large rank complexity in Resolution, for constant t, into a new related formula requring large rank and tree-like size complexity in much stronger proof systems, namely polynomial threshold proof systems, which consist of all systems for proving propositional tautologies by manipulating degree-k polynomial inequalities (collectively denoted as Th(k) proof systems). This method works for any k < log log n, where n is the size of the formula. These include Gomory-Chvatal cutting-planes (CP) (as a special case of Th(1)) and Lovasz-Schrijver systems (as special cases of Th(2)). This method thus yields new rank and tree-like size lower bounds for a large number of natural formulas in these systems, whereas previously, lower bounds for only a handful of problems were known.

For every even constant t>5, we also obtain strong integrality gap results for the MAX-t-SAT problem for Th(1) systems, which include CP. We also show that Th(k) systems are strictly stronger than Th(k-1) systems, for every k<loglog n, in terms of rank and tree-like size.

This is joint work with Paul Beame and Toniann Pitassi.

The speaker was invited by Jakob Nordström.