TY - GEN
T1 - Hypercontractive inequalities via SOS, and the frankl-rodl graph
AU - Kauers, Manuel
AU - O'Donnell, Ryan
AU - Tan, Li Yang
AU - Zhou, Yuan
PY - 2014
Y1 - 2014
N2 - Our main result is a formulation and proof of the reverse hypercontractive inequality in the sum-of-squares (SOS) proof system. As a consequence we show that for any constant 0 < γ < 1/4, the SOS/Lasserre SDP hierarchy at degree 4[1/4γ]certifies the statement "the maximum independent set in the Frankl-Rödl graph FRnγ has fractional size o( 1)". Here FRnγ = (V,E) is the graph with V = {0,1 }n and (x, y) ∈ E whenever δ(x,y) = (1 - γ)n (an even integer). In particular, we show the degree-4 SOS algorithm certifies the chromatic number lower bound "x(FRn1/4) = ω(l)", even though FRn1/4 is the canonical integrality gap instance for which standard SDP relaxations cannot even certify "x(FRn1/4) > 3". Finally, we also give an SOS proof of (a generalization of) the sharp (2, q)-hypercontractive inequality for any even integer q.
AB - Our main result is a formulation and proof of the reverse hypercontractive inequality in the sum-of-squares (SOS) proof system. As a consequence we show that for any constant 0 < γ < 1/4, the SOS/Lasserre SDP hierarchy at degree 4[1/4γ]certifies the statement "the maximum independent set in the Frankl-Rödl graph FRnγ has fractional size o( 1)". Here FRnγ = (V,E) is the graph with V = {0,1 }n and (x, y) ∈ E whenever δ(x,y) = (1 - γ)n (an even integer). In particular, we show the degree-4 SOS algorithm certifies the chromatic number lower bound "x(FRn1/4) = ω(l)", even though FRn1/4 is the canonical integrality gap instance for which standard SDP relaxations cannot even certify "x(FRn1/4) > 3". Finally, we also give an SOS proof of (a generalization of) the sharp (2, q)-hypercontractive inequality for any even integer q.
UR - http://www.scopus.com/inward/record.url?scp=84902095948&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84902095948&partnerID=8YFLogxK
U2 - 10.1137/1.9781611973402.119
DO - 10.1137/1.9781611973402.119
M3 - Conference contribution
AN - SCOPUS:84902095948
SN - 9781611973389
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 1644
EP - 1658
BT - Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
PB - Association for Computing Machinery
T2 - 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
Y2 - 5 January 2014 through 7 January 2014
ER -