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

Fingerprint

Sum of squares
Reverse Inequality
Q-integers
Proof System
Graph in graph theory
Formulation
Generalization

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this

Kauers, M., O'Donnell, R., Tan, L. Y., & Zhou, Y. (2014). Hypercontractive inequalities via SOS, and the frankl-rodl graph. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 (pp. 1644-1658). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery,.

Hypercontractive inequalities via SOS, and the frankl-rodl graph. / Kauers, Manuel; O'Donnell, Ryan; Tan, Li Yang; Zhou, Yuan.

Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014. Association for Computing Machinery, 2014. p. 1644-1658 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

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

Kauers, M, O'Donnell, R, Tan, LY & Zhou, Y 2014, Hypercontractive inequalities via SOS, and the frankl-rodl graph. in Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, pp. 1644-1658, 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, OR, United States, 1/5/14.
Kauers M, O'Donnell R, Tan LY, Zhou Y. Hypercontractive inequalities via SOS, and the frankl-rodl graph. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014. Association for Computing Machinery,. 2014. p. 1644-1658. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).
Kauers, Manuel ; O'Donnell, Ryan ; Tan, Li Yang ; Zhou, Yuan. / Hypercontractive inequalities via SOS, and the frankl-rodl graph. Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014. Association for Computing Machinery, 2014. pp. 1644-1658 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).
@inproceedings{9275dbd170dc4aa6847ebbd2c67cf1b5,
title = "Hypercontractive inequalities via SOS, and the frankl-rodl graph",
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{\"o}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.",
author = "Manuel Kauers and Ryan O'Donnell and Tan, {Li Yang} and Yuan Zhou",
year = "2014",
month = "1",
day = "1",
language = "English (US)",
isbn = "9781611973389",
series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",
publisher = "Association for Computing Machinery,",
pages = "1644--1658",
booktitle = "Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014",

}

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/1/1

Y1 - 2014/1/1

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

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,

ER -