Hypercontractive inequalities via SOS, with an application to Vertex-Cover
Manuel Kauers, Ryan W. O’Donnell, Li-Yang Tan, Yuan Zhou · arXiv (Cornell University) · 2012
Our main result is a formulation and proof of the reverse hypercontractive inequality in the sum-ofsquares (SOS) proof system. As a consequence, we show that for any constant γ> 0, the O(1/γ)-round SOS/Lasserre SDP hierarchy certifies the statement “Min-Vertex-Cover(G n γ) ≥ (1 − on(1))|V|”, where G n γ = (V,E) is the “Frankl–Rödl graph ” with V = {0,1} n and (x,y) ∈ E whenever ∆(x,y) = (1−γ)n. This is despite the fact that k rounds of various LP and SDP hierarchies fail to certify the statement +ǫ)|V| ” once γ = γ(k,ǫ)> 0 is small enough. Finally, we also give an SOS proof of (a generalization of) the sharp (2,q)-hypercontractive inequality for any even integer q. “Min-Vertex-Cover(G n γ) ≥ ( 1 2 1