Approximability and Proof Complexity

January 23, 2013

How hard is it to certify that a given optimization task
does *not* have a good solution? For example, if a graph has
chromatic number 100, must there be a succinct proof that it is not
3-colorable? If so, what precisely is the "complexity" of that proof?
Lasserre and Parrilo have shown that if a proof can be carried out in
the "Sum-Of-Squares" proof system of Grigoriev et al. then that proof
can actually be *found* efficiently. We explore this connection
between proof complexity and optimization and show that it leads to
efficient algorithms for the known "hard instances" of the
Balanced-Separator, Max-Cut, and Vertex-Cover problems.

*Joint work with Yuan Zhou, Manuel Kauers, and Li-Yang Tan.*