This paper continues the investigation of the connection between proof systems and approximation. The emphasis is on proving ``tight'' non-approximability results via consideration of measures like the ``free bit complexity'' and the ``amortized free bit complexity'' of proof systems. The first part of the paper presents a collection of new ... 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 >>>

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 >>>

We give a new proof showing that it is NP-hard to color a 3-colorable graph using just four colors. This result is already known (Khanna, Linial, Safra 1992), but our proof is novel as it does not rely on the PCP theorem, while the earlier one does. This highlights a ... more >>>

Using known results regarding PCP, we present simple proofs of the inapproximability of vertex cover for hypergraphs. Specifically, we show that (1) Approximating the size of the minimum vertex cover in $O(1)$-regular hypergraphs to within a factor of~1.99999 is NP-hard. (2) Approximating the size of the minimum vertex cover in ... 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 >>>

Locally testable codes are error-correcting codes that admit very efficient codeword tests. Specifically, using a constant number of (random) queries, non-codewords are rejected with probability proportional to their distance from the code. Locally testable codes are believed to be the combinatorial core of PCPs. However, the relation is less immediate ... more >>>

We continue the investigation of locally testable codes, i.e., error-correcting codes for whom membership of a given word in the code can be tested probabilistically by examining it in very few locations. We give two general results on local testability: First, motivated by the recently proposed notion of robust probabilistically ... more >>>

We give constructions of PCPs of length n*polylog(n) (with respect to circuits of size n) that can be verified by making polylog(n) queries to bits of the proof. These PCPs are not only shorter than previous ones, but also simpler. Our (only) building blocks are Reed-Solomon codes and the bivariate ... more >>>

The notion of promise problems was introduced and initially studied by Even, Selman and Yacobi (Information and Control, Vol.~61, pages 159-173, 1984). In this article we survey some of the applications that this notion has found in the twenty years that elapsed. These include the notion of ``unique solutions'', the ... 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 >>>

Given a function f:F^m \rightarrow F over a finite field F, a low degree tester tests its proximity to an m-variate polynomial of total degree at most d over F. The tester is usually given access to an oracle A providing the supposed restrictions of f to affine subspaces of ... more >>>

We highlight a common theme in four relatively recent works that establish remarkable results by an iterative approach. Starting from a trivial construct, each of these works applies an ingeniously designed sequence of iterations that yields the desired result, which is highly non-trivial. Furthermore, in each iteration, the construct is ... more >>>

more >>>

We show a construction of a PCP with both sub-constant error and almost-linear size. Specifically, for some constant alpha in (0,1), we construct a PCP verifier for checking satisfiability of Boolean formulas that on input of size n uses log n + O((log n)^{1-alpha}) random bits to query a constant ... more >>>

An interactive-PCP (say, for the membership $x \in L$) is a proof that can be verified by reading only one of its bits, with the help of a very short interactive-proof. We show that for membership in some languages $L$, there are interactive-PCPs that are significantly shorter than the known ... more >>>

In the undirected Edge-Disjoint Paths problem with Congestion (EDPwC), we are given an undirected graph with $V$ nodes, a set of terminal pairs and an integer $c$. The objective is to route as many terminal pairs as possible, subject to the constraint that at most $c$ demands can be routed ... 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 define a non-uniform model of PCPs of Proximity, and observe that in this model the non-uniform verifiers can always be made very efficient. Specifically, we show that any non-uniform verifier can be modified to run in time that is roughly polynomial in its randomness and query complexity. more >>>

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 >>>

The well known dichotomy conjecture of Feder and Vardi states that for every finite family Γ of constraints CSP(Γ) is either polynomially solvable or NP-hard. Bulatov and Jeavons re- formulated this conjecture in terms of the properties of the algebra P ol(Γ), where the latter is the collection of those ... more >>>

We study the maximization version of the fundamental graph coloring problem. Here the goal is to color the vertices of a $k$-colorable graph with $k$ colors so that a maximum fraction of edges are properly colored (i.e., their endpoints receive different colors). A random $k$-coloring properly colors an expected fraction ... 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 >>>