193 citations · 209 across the 11 of their papers we have counts for
4 papers · 2 filters
Hypercontractive inequalities via SOS, and the Frankl--Rödl graph
Manuel Kauers, Ryan O'Donnell, Li-Yang Tan +1
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 <…
Approximability and proof complexity
Ryan O'Donnell, Yuan Zhou
This work is concerned with the proof-complexity of certifying that optimization problems do \emph{not} have good solutions. Specifically we consider bounded-degree "Sum of Squares…
Hypercontractivity, Sum-of-Squares Proofs, and their Applications
Boaz Barak, Fernando G. S. L. Brandão, Aram W. Harrow +3
We study the computational complexity of approximating the 2->q norm of linear operators (defined as ||A||_{2->q} = sup_v ||Av||_q/||v||_2), as well as connections between this que…
Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems
Venkatesan Guruswami, Ali Kemal Sinop, Yuan Zhou
Partitioning the vertices of a graph into two roughly equal parts while minimizing the number of edges crossing the cut is a fundamental problem (called Balanced Separator) that ar…