The Sum-of-Squares (SoS) hierarchy, also known as Lasserre hierarchy, has
emerged as a promising tool in optimization. However, it remains unclear
whether fixed-degree SoS proofs can be automated [O’Donnell (2017)]. Indeed,
there are examples of polynomial systems with bounded coefficients that admit
low-degree SoS proofs, but these proofs necessarily involve numbers with an
exponential number of bits, implying that low-degree SoS proofs cannot always
be found efficiently.
A sufficient condition derived from the Nullstellensatz proof system
[Raghavendra and Weitz (2017)] identifies cases where bit complexity issues can
be circumvented. One of the main problems left open by Raghavendra and Weitz is
proving any result for refutations, as their condition applies only to
polynomial systems with a large set of solutions.
In this work, we broaden the class of polynomial systems for which degree-$d$
SoS proofs can be automated. To achieve this, we develop a new criterion and we
demonstrate how our criterion applies to polynomial systems beyond the scope of
Raghavendra and Weitz’s result. In particular, we establish a separation for
instances arising from Constraint Satisfaction Problems (CSPs). Moreover, our
result extends to refutations, establishing that polynomial-time refutation is
possible for broad classes of polynomial time solvable constraint problems,
highlighting a first advancement in this area.

Este artículo explora los viajes en el tiempo y sus implicaciones.

Descargar PDF: