Geodesic
Hypercontractive inequalities via SOS, and the Frankl--Rödl graph
Discrete analysis (2016) Cet article a éte moissonné depuis la source Scholastica

Voir la notice de l'article

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 γ\leq 1/4$, the SOS/Lasserre SDP hierarchy at degree $4\lceil \frac{1}{4γ}\rceil$ certifies the statement "the maximum independent set in the Frankl--Rödl graph $\mathrm{FR}^{n}_γ$ has fractional size~$o(1)$". Here $\mathrm{FR}^{n}_γ = (V,E)$ is the graph with $V = \{0,1\}^n$ and $(x,y) \in E$ whenever $Δ(x,y) = (1-γ)n$ (an even integer). In particular, we show the degree-$4$ SOS algorithm certifies the chromatic number lower bound "$χ(\mathrm{FR}^{n}_{1/4}) = ω(1)$", even though $\mathrm{FR}^{n}_{1/4}$ is the canonical integrality gap instance for which standard SDP relaxations cannot even certify "$χ(\mathrm{FR}^{n}_{1/4}) > 3$". Finally, we also give an SOS proof of (a generalization of) the sharp $(2,q)$-hypercontractive inequality for any even integer $q$.
Publié le : 
@article{DAS_2016_a15,
     author = {Manuel Kauers and Ryan O'Donnell and Li-Yang Tan and Yuan Zhou},
     title = {Hypercontractive inequalities via {SOS,} and the {Frankl--R\"odl} graph},
     journal = {Discrete analysis},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DAS_2016_a15/}
}
TY  - JOUR
AU  - Manuel Kauers
AU  - Ryan O'Donnell
AU  - Li-Yang Tan
AU  - Yuan Zhou
TI  - Hypercontractive inequalities via SOS, and the Frankl--Rödl graph
JO  - Discrete analysis
PY  - 2016
UR  - http://geodesic.mathdoc.fr/item/DAS_2016_a15/
LA  - en
ID  - DAS_2016_a15
ER  - 
%0 Journal Article
%A Manuel Kauers
%A Ryan O'Donnell
%A Li-Yang Tan
%A Yuan Zhou
%T Hypercontractive inequalities via SOS, and the Frankl--Rödl graph
%J Discrete analysis
%D 2016
%U http://geodesic.mathdoc.fr/item/DAS_2016_a15/
%G en
%F DAS_2016_a15
Manuel Kauers; Ryan O'Donnell; Li-Yang Tan; Yuan Zhou. Hypercontractive inequalities via SOS, and the Frankl--Rödl graph. Discrete analysis (2016). http://geodesic.mathdoc.fr/item/DAS_2016_a15/