Hypercontractive inequalities via SOS, and the Frankl-Rödl graph

Hypercontractive inequalities via SOS, and the Frankl-Rödl graph, Discrete Analysis 2016:4, 20 pp.

One of the major unsolved problems in theoretical computer science is the unique games conjecture of Subhash Khot. Its importance lies in the fact that it would imply that many of our best known approximation algorithms are optimal (assuming that P\(\ne\)NP). As with the statement that P\(\ne\)NP, many results have now been proved assuming the unique-games conjecture. However, theoretical computer scientists are much less confident that it is true than they (mostly) are that P\(\ne\)NP.

A possible challenge to the unique games conjecture comes from the so-called sum-of-squares algorithm, which for some problems has turned out to be better than the algorithms based on semidefinite programming that had previously been thought likely to be best possible. Suppose we wish to prove that a system of real polynomial equations \(P_1=\dots=P_m=0\) in \(k\) variables cannot be simultaneously solved. It can be shown that this is equivalent to the existence of polynomials \(Q_1,\dots,Q_m\) and \(S\) such that \(S\) is a sum of squares of polynomials and \(\sum_iP_iQ_i+S=-1\). More interestingly from a computational point of view, there are often situations where the polynomials \(Q_i\) and \(S\) have low degree, and when that is the case they can be found efficiently. Furthermore, many interesting problems can be reformulated as polynomial equations of this type.

In particular, Barak, Brandão, Harrow, Kelner, Steurer and Zhou found an SOS proof of a hypercontractive inequality. Hypercontractive inequalities are bounds for the norms of certain convolution operators from \(L_p\) to \(L_q\), where the ground sets of these spaces are the discrete cube: the proof obtained by Barak et al was for \(p=2\) and \(q=4\). They have many applications, in particular to proving integrality gaps: that is, optimization problems with significantly different bounds if the answers are required to be integers. If the inequalities can be proved by SOS methods, then that raises the possibility of finding SOS certifications of integrality gaps, which has been achieved for several problems. Although none of these applications is yet powerful enough to refute the unique games conjecture, it is still a promising line of enquiry.

In this paper the authors obtain a sum-of-squares proof for the hypercontractivity inequality with \(p=2\) and \(q=2k\) for any integer \(k\). They also find a sum-of-squares proof for a reverse hypercontractive inequality. One consequence of the main results is a degree-4 SOS certification that a certain graph defined by Frankl and Rödl has unbounded chromatic number, despite the fact that standard semidefinite linear programming relaxations of the problem cannot even certify a lower bound better than 3.