
Fedor Part

(JetBrains)

A first order theory for constant degree Sum of Squares , Part 2
 Abstract:

The Unique Games Conjecture (UGC) predicts that a certain universal algorithm achieves an optimal approximation for a large class of NP optimization problems. This algorithm can be seen as a proof searching procedure for the constant degree SumofSquares (SoS) proof system, which is automatizable via semidefinite programming. The actual strength of this algorithm and, possibly, the fate of UGC depend on what is derivable in constant degree SoS.
In some cases one can argue that the SoS algorithm achieves a bound on an instance by taking some known "ZFC" proof that the optimum meets the bound and trying to redo the proof in constant degree SoS. For example, for the integrality gap instance for LP and SDP hierarchies, that is based on FranklRodl graphs, one can show that the SoS algorithm meets the bound on the size of a maximal independent set, guaranteed by the the FranklRodl theorem, by proving the theorem in constant degree SoS.
In this talk, we will present work in progress on the conceptual analysis of the reasoning constant degree SoS is capable of. In particular, we will sketch the definition of a firstorder theory, which under propositional translation corresponds to constant degree SoS. This is joint work with Neil Thapen and Iddo Tzameret.

Fedor Part

(JetBrains)

A first order theory for constant degree Sum of Squares
 Abstract:

The Unique Games Conjecture (UGC) predicts that a certain universal algorithm achieves an optimal approximation for a large class of NP optimization problems. This algorithm can be seen as a proof searching procedure for the constant degree SumofSquares (SoS) proof system, which is automatizable via semidefinite programming. The actual strength of this algorithm and, possibly, the fate of UGC depend on what is derivable in constant degree SoS.
In some cases one can argue that the SoS algorithm achieves a bound on an instance by taking some known "ZFC" proof that the optimum meets the bound and trying to redo the proof in constant degree SoS. For example, for the integrality gap instance for LP and SDP hierarchies, that is based on FranklRodl graphs, one can show that the SoS algorithm meets the bound on the size of a maximal independent set, guaranteed by the the FranklRodl theorem, by proving the theorem in constant degree SoS.
In this talk, we will present work in progress on the conceptual analysis of the reasoning constant degree SoS is capable of. In particular, we will sketch the definition of a firstorder theory, which under propositional translation corresponds to constant degree SoS. This is joint work with Neil Thapen and Iddo Tzameret.
Pavel Pudlak, Neil Thapen
organizers