Hypercontractive inequalities via SOS, and the frankl-rodl graph

Manuel Kauers, Ryan O'Donnell, Li Yang Tan, Yuan Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
PublisherAssociation for Computing Machinery,
Pages1644-1658
Number of pages15
ISBN (Print)9781611973389
StatePublished - Jan 1 2014
Externally publishedYes
Event25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 - Portland, OR, United States
Duration: Jan 5 2014Jan 7 2014

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
CountryUnited States
CityPortland, OR
Period1/5/141/7/14

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Hypercontractive inequalities via SOS, and the frankl-rodl graph'. Together they form a unique fingerprint.

Cite this