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.