We show optimal (up to constant factor) NP-hardness for Max-k-CSP over any domain,
whenever k is larger than the domain size. This follows from our main result concerning predicates
over abelian groups. We show that a predicate is approximation resistant if it contains a subgroup that
is ... more >>>

We construct a PCP based on the hyper-graph linearity test with 3 free queries. It has near-perfect completeness and soundness strictly less than 1/8. Such a PCP was known before only assuming the Unique Games Conjecture, albeit with soundness arbitrarily close to 1/16.

At a technical level, our ... more >>>

We formulate a new connection between instance compressibility \cite{Harnik-Naor10}), where the compressor uses circuits from a class $\C$, and correlation with
circuits in $\C$. We use this connection to prove the first lower bounds
on general probabilistic multi-round instance compression. We show that there
is no
probabilistic multi-round ... more >>>