There is an increasing interest in quantum algorithms for problems of integer programming
and combinatorial optimization. Classical solvers for such problems employ relaxations …

We prove that pseudorandom sets in the Grassmann graph have near-perfect expansion.
This completes the last missing piece of the proof of the 2-to-2-Games Conjecture (albeit …

We study the computational complexity of approximating the 2-to-q norm of linear operators
(defined as| A| 2-> q= maxv≠ 0| Av| q/| v| 2) for q> 2, as well as connections between this …

Given a complete graph G=(V, E) where each edge is labeled+ or−, the CORRELATION
CLUSTERING problem asks to partition V into clusters to minimize the number of+ edges …

Subexponential time approximation algorithms are presented for the Unique Games and
Small-Set Expansion problems. Specifically, for some absolute constant c, the following two …

We consider two problems that arise in machine learning applications: the problem of
recovering a planted sparse vector in a random linear subspace and the problem of …

Over the last twenty years, an exciting interplay has emerged between proof systems and
algorithms. Some natural families of algorithms can be viewed as a generic translation from …

Parameterization and approximation are two popular ways of co** with NP-hard
problems. More recently, the two have also been combined to derive many interesting …

In the list-decodable learning setup, an overwhelming majority (say a 1–β-fraction) of the
input data consists of outliers and the goal of an algorithm is to output a small list of …

Finding cliques in random graphs and the closely related" planted" clique variant, where a
clique of size k is planted in a random G (n, 1/2) graph, have been the focus of substantial …