The main result of this paper is a simple, yet generic, composition theorem for low error two-query probabilistically checkable proofs (PCPs). Prior to this work, composition of PCPs was well-understood only in the constant error regime. Existing composition methods in the low error regime were non-modular (i.e., very much tailored ... more >>>

Given a pair of finite groups $G$ and $H$, the set of homomorphisms from $G$ to $H$ form an error-correcting code where codewords differ in at least $1/2$ the coordinates. We show that for every pair of {\em abelian} groups $G$ and $H$, the resulting code is (locally) list-decodable from ... more >>>

Given two binary linear codes R and C, their tensor product R \otimes C consists of all matrices with rows in R and columns in C. We analyze the "robustness" of the following test for this code (suggested by Ben-Sasson and Sudan~\cite{BenSasson-Sudan04}): Pick a random row (or column) and check ... more >>>

Let C={c_1,...,c_n} be a set of constraints over a set of variables. The {\em satisfiability-gap} of C is the smallest fraction of unsatisfied constraints, ranging over all possible assignments for the variables. We prove a new combinatorial amplification lemma that doubles the satisfiability-gap of a constraint-system, with only a linear ... more >>>

We study the approximate-coloring(q,Q) problem: Given a graph G, decide whether \chi(G) \le q or \chi(G)\ge Q. We derive conditional hardness for this problem for any constant 3\le q < Q. For q \ge 4, our result is based on Khot's 2-to-1 conjecture [Khot'02]. For q=3, we base our hardness ... more >>>

Given a $k$-uniform hypergraph, the E$k$-Vertex-Cover problem is to find a minimum subset of vertices that ``hits'' every edge. We show that for every integer $k \geq 5$, E$k$-Vertex-Cover is NP-hard to approximate within a factor of $(k-3-\epsilon)$, for an arbitrarily small constant $\epsilon > 0$. This almost matches the ... more >>>

We show Minimum Vertex Cover NP-hard to approximate to within a factor of 1.3606. This improves on the previously known factor of 7/6. more >>>

This paper shows SVP_\infty and CVP_\infty to be NP-hard to approximate to within any factor up to $n^{1/\log\log n}$. This improves on the best previous result \cite{ABSS} that showed quasi-NP-hardness for smaller factors, namely $2^{\log^{1-\epsilon}n}$ for any constant $\epsilon>0$. We show a direct reduction from SAT to these problems, that ... more >>>

The label-cover problem was introduced in \cite{ABSS} and shown there to be quasi-NP-hard to approximate to within a factor of $2^{\log^{1-\delta}n}$ for any {\em constant} $\delta>0$. This combinatorial graph problem has been utilized \cite{ABSS,GM,ABMP} for showing hardness-of-approximation of numerous problems. We present a direct combinatorial reduction from low error-probability PCP ... more >>>

This paper strengthens the low-error PCP characterization of NP, coming closer to the ultimate BGLR conjecture. Namely, we prove that witnesses for membership in any NP language can be verified with a constant number of accesses, and with an error probability exponentially small in the number of bits accessed, as ... more >>>

This paper shows finding the closest vector in a lattice to be NP-hard to approximate to within any factor up to $2^{(\log{n})^{1-\epsilon}}$ where $\epsilon = (\log\log{n})^{-\alpha}$ and $\alpha$ is any positive constant $<{1\over 2}$. more >>>