193 citations · 209 across the 11 of their papers we have counts for
6 papers · 1 filter
Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs
Ryan O'Donnell, John Wright, Chenggang Wu +1
Building on work of Cai, Fürer, and Immerman \cite{CFI92}, we show two hardness results for the Graph Isomorphism problem. First, we show that there are pairs of nonisomorphic -…
Locally Testable Codes and Cayley Graphs
Parikshit Gopalan, Salil Vadhan, Yuan Zhou
We give two new characterizations of ($\F_2$-linear) locally testable error-correcting codes in terms of Cayley graphs over $\F_2^h$: \begin{enumerate} \item A locally testable cod…
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…