Hypercontractive inequalities via SOS, and the Frankl--Rödl graph
From MaRDI portal
Publication:2826231
DOI10.19086/da.612zbMath1423.68347arXiv1212.5324OpenAlexW2569769046MaRDI QIDQ2826231
Yuan Zhou, Manuel Kauers, Ryan O'Donnell, Li-Yang Tan
Publication date: 10 October 2016
Published in: Discrete Analysis (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1212.5324
Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Graph theory (including graph drawing) in computer science (68R10) Boolean functions (06E30)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A tight quantitative version of Arrow's impossibility theorem
- On the hardness of approximating minimum vertex cover
- A fast algorithm for proving terminating hypergeometric identities
- Noise stability of functions with low influences: invariance and optimality
- Hypercontraction principle and random multilinear forms
- Positivity improving operators and hypercontractivity
- Approximating the independence number via the \(\vartheta\)-function
- A quantitative Arrow theorem
- On reverse hypercontractivity
- Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
- Tight Gaps for Vertex Cover in the Sherali-Adams SDP Hierarchy
- New approximation guarantee for chromatic number
- Integrality gaps for sparsest cut and minimum linear arrangement problems
- New Tools for Graph Coloring
- Vertex Cover Resists SDPs Tightened by Local Hypermetric Inequalities
- Extending SDP Integrality Gaps to Sherali-Adams with Applications to Quadratic Programming and MaxCutGain
- Conditional Hardness for Approximate Coloring
- Forbidden Intersections
- Approximate graph coloring by semidefinite programming
- On the Shannon capacity of a graph
- The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover
- Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers
- On the Hardness of 4-Coloring a 3-Colorable Graph
- Optimisation globale et théorie des moments
- Why you should remove zeros from data before guessing
- Breaking the multicommodity flow barrier for o(√log n)-approximations to sparsest cut
- SDP Integrality Gaps with Local ell_1-Embeddability
- Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES
- Integrality gaps for Sherali-Adams relaxations
- CSP gaps and reductions in the lasserre hierarchy
- Handbook of Enumerative Combinatorics
- The Holonomic Toolkit
- Integrality Gaps of $2-o(1)$ for Vertex Cover SDPs in the Lovász–Schrijver Hierarchy
- Hypercontractivity, sum-of-squares proofs, and their applications
- A quantitative gibbard-satterthwaite theorem without neutrality
- Majority is stablest
- Approximability and proof complexity
- On the hardness of approximating the chromatic number
- Complexity of Null- and Positivstellensatz proofs
