We give a new construction of algebraic codes which are efficiently list decodable from a fraction $1-R-\epsilon$ of adversarial errors where $R$ is the rate of the code, for any desired positive constant $\epsilon$. The worst-case list size output by the algorithm is $O(1/\epsilon)$, matching the existential bound for random ... more >>>

We prove the following results concerning the combinatorics of list decoding, motivated by the exponential gap between the known upper bound (of $O(1/\gamma)$) and lower bound (of $\Omega_p(\log (1/\gamma))$) for the list-size needed to decode up to radius $p$ with rate $\gamma$ away from capacity, i.e., $1-h(p)-\gamma$ (here $p\in (0,1/2)$ ... 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 prove that, assuming the Unique Games Conjecture (UGC), every problem in the class of ordering constraint satisfaction problems (OCSP) where each constraint has constant arity is approximation
resistant. In other words, we show that if $\rho$ is the expected fraction of constraints satisfied by a random ordering, then obtaining ... more >>>

We prove the following strong hardness result for learning: Given a distribution of labeled examples from the hypercube such that there exists a monomial consistent with $(1-\epsilon)$ of the examples, it is $\mathrm{NP}$-hard to find a halfspace that is correct on $(1/2+\epsilon)$ of the examples, for arbitrary constants $\epsilon > ... 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 prove almost tight hardness results for finding independent sets in bounded degree graphs and hypergraphs that admit a good
coloring. Our specific results include the following (where $\Delta$, assumed to be a constant, is a bound on the degree, and
$n$ is the number of vertices):

\begin{itemize}
more >>>

In this paper, we consider coding schemes for computationally bounded channels, which can introduce an arbitrary set of errors as long as (a) the fraction of errors is bounded with high probability by a parameter p and (b) the process which adds the errors can be described by a sufficiently ... 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 >>>

For every fixed finite field $\F_q$, $p \in (0,1-1/q)$ and $\varepsilon >
0$, we prove that with high probability a random subspace $C$ of
$\F_q^n$ of dimension $(1-H_q(p)-\varepsilon)n$ has the
property that every Hamming ball of radius $pn$ has at most
$O(1/\varepsilon)$ codewords.

This answers a ... more >>>

Locally testable codes (LTCs) are error-correcting codes for which membership, in the code, of a given word can be tested by examining it in very few locations. Most known constructions of locally testable codes are linear codes, and give error-correcting codes
whose duals have (superlinearly) {\em many} small weight ... 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 >>>

A classic result due to Hastad established that for every constant \eps > 0, given an overdetermined system of linear equations over a finite field \F_q where each equation depends on exactly 3 variables and at least a fraction (1-\eps) of the equations can be satisfied, it is NP-hard to ... more >>>

Algebraic codes that achieve list decoding capacity were recently
constructed by a careful ``folding'' of the Reed-Solomon code. The
``low-degree'' nature of this folding operation was crucial to the list
decoding algorithm. We show how such folding schemes conducive to list
decoding arise out of the Artin-Frobenius automorphism at primes ... more >>>

We design the first efficient algorithms and prove new combinatorial bounds for list decoding tensor products of codes and interleaved codes.

1)We show that for every code, the ratio of its list decoding radius to its minimum distance stays unchanged under the tensor product operation (rather than squaring, as one ... more >>>

We prove that binary linear concatenated codes with an outer algebraic code (specifically, a folded Reed-Solomon code) and independently and randomly chosen linear inner codes achieve the list-decoding capacity with high probability. In particular, for any $0 < \rho < 1/2$ and $\epsilon > 0$, there exist concatenated codes of ... more >>>

We construct binary linear codes that are efficiently list-decodable
up to a fraction $(1/2-\eps)$ of errors. The codes encode $k$ bits
into $n = {\rm poly}(k/\eps)$ bits and are constructible and
list-decodable in time polynomial in $k$ and $1/\eps$ (in
particular, in our results $\eps$ need ... 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 >>>

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 give a polynomial time construction of binary codes with the best
currently known trade-off between rate and error-correction
radius. Specifically, we obtain linear codes over fixed alphabets
that can be list decoded in polynomial time up to the so called
Blokh-Zyablov bound. Our work builds ... more >>>

We study the average-case hardness of the class NP against
deterministic polynomial time algorithms. We prove that there exists
some constant $\mu > 0$ such that if there is some language in NP
for which no deterministic polynomial time algorithm can decide L
correctly on a $1- (log n)^{-\mu}$ fraction ... more >>>

We give an explicit (in particular, deterministic polynomial time)
construction of subspaces $X
\subseteq \R^N$ of dimension $(1-o(1))N$ such that for every $x \in X$,
$$(\log N)^{-O(\log\log\log N)} \sqrt{N}\, \|x\|_2 \leq \|x\|_1 \leq \sqrt{N}\, \|x\|_2.$$
If we are allowed to use $N^{1/\log\log N}\leq N^{o(1)}$ random bits
and ... more >>>

We prove a strong inapproximability result for routing on directed
graphs with low congestion. Given as input a directed graph on $N$
vertices and a set of source-destination pairs that can be connected
via edge-disjoint paths, we prove that it is hard, assuming NP
doesn't have $n^{O(\log\log n)}$ time randomized ... more >>>

We give new constructions of randomness extractors and lossless condensers that are optimal to within constant factors in both the seed length and the output length. For extractors, this matches the parameters of the current best known construction [LRVW03]; for lossless condensers, the previous best constructions achieved optimality to within ... more >>>

Much progress has been made on decoding algorithms for
error-correcting codes in the last decade. In this article, we give an
introduction to some fundamental results on iterative, message-passing
algorithms for low-density parity check codes. For certain
important stochastic channels, this line of work has enabled getting
very close to ... more >>>

Much progress has been made on decoding algorithms for
error-correcting codes in the last decade. In this article, we give an
introduction to some fundamental results on iterative, message-passing
algorithms for low-density parity check codes. For certain
important stochastic channels, this line of work has enabled getting
very close to ... more >>>

Learning an unknown halfspace (also called a perceptron) from
labeled examples is one of the classic problems in machine learning.
In the noise-free case, when a halfspace consistent with all the
training examples exists, the problem can be solved in polynomial
time using linear programming. However, ... more >>>

For every $0 < R < 1$ and $\eps > 0$, we present an explicit
construction of error-correcting codes of rate $R$ that can be list
decoded in polynomial time up to a fraction $(1-R-\eps)$ of errors.
These codes achieve the ``capacity'' for decoding from {\em adversarial} ... more >>>

This paper is concerned with a new family of error-correcting codes
based on algebraic curves over finite fields, and list decoding
algorithms for them. The basic goal in the subject of list decoding is
to construct error-correcting codes $C$ over some alphabet $\Sigma$
which have good rate $R$, and at ... more >>>

We prove a version of the derandomized Direct Product Lemma for
deterministic space-bounded algorithms. Suppose a Boolean function
$g:\{0,1\}^n\to\{0,1\}$ cannot be computed on more than $1-\delta$
fraction of inputs by any deterministic time $T$ and space $S$
algorithm, where $\delta\leq 1/t$ for some $t$. Then, for $t$-step
walks $w=(v_1,\dots, v_t)$ ... more >>>

An error-correcting code is said to be {\em locally testable} if it has an
efficient spot-checking procedure that can distinguish codewords
from strings that are far from every codeword, looking at very few
locations of the input in doing so. Locally testable codes (LTCs) have
generated ... more >>>

Maximum-likelihood decoding is one of the central algorithmic
problems in coding theory. It has been known for over 25 years
that maximum-likelihood decoding of general linear codes is
NP-hard. Nevertheless, it was so far unknown whether maximum-
likelihood decoding remains hard for any specific family of
more >>>

We present an explicit construction of codes that can be list decoded
from a fraction $(1-\eps)$ of errors in sub-exponential time and which
have rate $\eps/\log^{O(1)}(1/\eps)$. This comes close to the optimal
rate of $\Omega(\eps)$, and is the first sub-exponential complexity
construction to beat the rate of $O(\eps^2)$ achieved by ... more >>>

By the breakthrough work of Håstad, several constraint satisfaction
problems are now known to have the following approximation resistance
property: satisfying more clauses than what picking a random
assignment would achieve is NP-hard. This is the case for example for
Max E3-Sat, Max E3-Lin and Max E4-Set Splitting. A notable ... 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 define number-theoretic error-correcting codes based on algebraic
number fields, thereby providing a generalization of Chinese Remainder
Codes akin to the generalization of Reed-Solomon codes to
Algebraic-geometric codes. Our construction is very similar to
(and in fact less general than) the one given by (Lenstra 1986), but
the ... 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 ... more >>>

We introduce the notion of covering complexity of a probabilistic
verifier. The covering complexity of a verifier on a given input is
the minimum number of proofs needed to ``satisfy'' the verifier on
every random string, i.e., on every random string, at least one of the
given proofs must be ... more >>>

We prove hardness results for approximating set splitting problems and
also instances of satisfiability problems which have no ``mixed'' clauses,
i.e all clauses have either all their literals unnegated or all of them
negated. Recent results of Hastad imply tight hardness results for set
splitting when all sets have size ... more >>>

We present an improved list decoding algorithm for decoding
Reed-Solomon codes. Given an arbitrary string of length n, the
list decoding problem is that of finding all codewords within a
specified Hamming distance from the input string.

It is well-known that this decoding problem for Reed-Solomon
codes reduces to the ... more >>>

It is known that there exists a PCP characterization of NP
where the verifier makes 3 queries and has a {\em one-sided}
error that is bounded away from 1; and also that 2 queries
do not suffice for such a characterization. Thus PCPs with
3 queries ... more >>>