It has been known since [Zyablov and Pinsker 1982] that a random $q$-ary code of rate $1-H_q(\rho)-\eps$ (where $0<\rho<1-1/q$, $\eps>0$ and $H_q(\cdot)$ is the $q$-ary entropy function) with high probability is a $(\rho,1/\eps)$-list decodable code. (That is, every Hamming ball of radius at most $\rho n$ has at most $1/\eps$ ... 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 not be constant and ... 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 upon (Guruswami-Rudra STOC06) where ... 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} errors, i.e., achieve ... more >>>

We consider the following simple algorithm for feedback arc set problem in weighted tournaments --- order the vertices by their weighted indegrees. We show that this algorithm has an approximation guarantee of $5$ if the weights satisfy \textit{probability constraints} (for any pair of vertices $u$ and $v$, $w_{uv}+w_{vu}=1$). Special cases ... more >>>

Ben-Sasson and Sudan in~\cite{BS04} asked if the following test is robust for the tensor product of a code with another code-- pick a row (or column) at random and check if the received word restricted to the picked row (or column) belongs to the corresponding code. Valiant showed that for ... 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 a lot of interest ... more >>>