We show that, assuming the Unique Games Conjecture, it is NP-hard to approximate Max 2-Sat within $\alpha_{LLZ}^{-}+\epsilon$, where $0.9401 < \alpha_{LLZ}^{-} < 0.9402$ is the believed approximation ratio of the algorithm of Lewin, Livnat and Zwick.

This result is surprising considering the fact that balanced instances of Max 2-Sat, i.e. ... more >>>

We study the approximability of the \maxcsp problem over non-boolean domains, more specifically over $\{0,1,\ldots,q-1\}$ for some integer $q$. We obtain a approximation algorithm that achieves a ratio of $C(q) \cdot k/q^k$ for some constant $C(q)$ depending only on $q$. Further, we extend the techniques of Samorodnitsky and Trevisan to ... more >>>

We study the approximability of predicates on $k$ variables from a
domain $[q]$, and give a new sufficient condition for such predicates
to be approximation resistant under the Unique Games Conjecture.
Specifically, we show that a predicate $P$ is approximation resistant
if there exists a balanced pairwise independent distribution over
more >>>

The parallel repetition theorem states that for any two-prover game,
with value $1- \epsilon$ (for, say, $\epsilon \leq 1/2$), the value of
the game repeated in parallel $n$ times is at most
$(1- \epsilon^c)^{\Omega(n/s)}$, where $s$ is the answers' length
(of the original game) and $c$ is a universal ... more >>>

The Unique Games Conjecture (UGC) is possibly the most important open problem in the research of PCPs and hardness of approximation. The conjecture is a strengthening of the PCP Theorem, predicting the existence of a special type of PCP verifiers: 2-query verifiers that only make unique tests. Moreover, the UGC ... more >>>

We study Locally Testable Codes (LTCs) that can be tested by making two queries to the tested word using an affine test. That is, we consider LTCs over a finite field F, with codeword testers that only use tests of the form $av_i + bv_j = c$, where v is ... more >>>

We study the approximability of two natural Boolean constraint satisfaction problems: Horn satisfiability and exact hitting set. Under the Unique Games conjecture, we prove the following optimal inapproximability and approximability results for finding an assignment satisfying as many constraints as possible given a {\em
near-satisfiable} instance.

\begin{enumerate}
\item Given ... more >>>

In this paper, we consider the problem of approximately solving a system of homogeneous linear equations over reals, where each
equation contains at most three variables.

Since the all-zero assignment always satisfies all the equations exactly, we restrict the assignments to be ``non-trivial". Here is
an informal statement of our ... more >>>

The Unique Games conjecture (UGC) has emerged in recent years as the starting point for several optimal inapproximability results. While for none of these results a reverse reduction to Unique Games is known, the assumption of bijective projections in the Label Cover instance seems critical in these proofs. In this ... more >>>

We present an approximation scheme for optimizing certain Quadratic Integer Programming problems with positive semidefinite objective functions and global linear constraints. This framework includes well known graph problems such as Minimum graph bisection, Edge expansion, Uniform sparsest cut, and Small Set expansion, as well as the Unique Games problem. These ... more >>>

We establish almost tight upper and lower approximation bounds for the Vertex Cover problem on dense k-partite hypergraphs.

more >>>