193 citations · 209 across the 11 of their papers we have counts for
11 papers
Assortment Optimization Under the Multivariate MNL Model
Xin Chen, Jiachun Li, Menglong Li +2
We study an assortment optimization problem under a multi-purchase choice model in which customers choose a bundle of up to one product from each of two product categories. Differe…
Satisfiability of Ordering CSPs Above Average
Konstantin Makarychev, Yury Makarychev, Yuan Zhou
We study the satisfiability of ordering constraint satisfaction problems (CSPs) above average. We prove the conjecture of Gutin, van Iersel, Mnich, and Yeo that the satisfiability…
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…
Left Derivations and Strong Commutativity Preserving Maps on Semiprime -Rings
Xiaowei Xu, Jing Ma, Yuan Zhou
In this paper, firstly as a short note, we prove that a left derivation of a semiprime -ring must map into its center, which improves a result by Paul and Halder and som…
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…
Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph
Aditya Bhaskara, Moses Charikar, Venkatesan Guruswami +2
The densest k-subgraph (DkS) problem (i.e. find a size k subgraph with maximum number of edges), is one of the notorious problems in approximation algorithms. There is a significan…
Optimal lower bounds for locality sensitive hashing (except when q is tiny)
Ryan O'Donnell, Yi Wu, Yuan Zhou
We study lower bounds for Locality Sensitive Hashing (LSH) in the strongest setting: point sets in {0,1}^d under the Hamming distance. Recall that here H is said to be an (r, cr, p…