In a variety of PAC learning models, a tradeoff between time and information seems to exist: with unlimited time, a small amount of information suffices, but with time restrictions, more information sometimes seems to be required. In addition, it has long been known that there are concept classes that can ... 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 >>>

The Chinese Remainder Theorem states that a positive integer m is uniquely specified by its remainder modulo k relatively prime integers p_1,...,p_k, provided m < \prod_{i=1}^k p_i. Thus the residues of m modulo relatively prime integers p_1 < p_2 < ... < p_n form a redundant representation of m if ... more >>>

We prove that if a linear error correcting code $\C:\{0,1\}^n\to\{0,1\}^m$ is such that a bit of the message can be probabilistically reconstructed by looking at two entries of a corrupted codeword, then $m = 2^{\Omega(n)}$. We also present several extensions of this result. We show a reduction from the complexity ... more >>>

Spielman showed that one can construct error-correcting codes capable of correcting a constant fraction $\delta << 1/2$ of errors, and that are encodable/decodable in linear time. Guruswami and Sudan showed that it is possible to correct more than $50\%$ of errors (and thus exceed the ``half of the minimum distance ... more >>>

We continue the study of the trade-off between the length of PCPs and their query complexity, establishing the following main results (which refer to proofs of satisfiability of circuits of size $n$): We present PCPs of length $\exp(\tildeO(\log\log n)^2)\cdot n$ that can be verified by making $o(\log\log n)$ Boolean queries. ... 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 >>>

We survey known results regarding locally testable codes and locally testable proofs (known as PCPs), with emphasis on the length of these constructs. Locally testability refers to approximately testing large objects based on a very small number of probes, each retrieving a single bit in the representation of the object. ... 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 >>>

In this work we give two new constructions of $\epsilon$-biased generators. Our first construction answers an open question of Dodis and Smith, and our second construction significantly extends a result of Mossel et al. In particular we obtain the following results: 1. We construct a family of asymptotically good binary ... more >>>

In this paper, we introduce the notion of a Public-Key Encryption (PKE) Scheme that is also a Locally-Decodable Error-Correcting Code. In particular, our construction simultaneously satisfies all of the following properties: \begin{itemize} \item Our Public-Key Encryption is semantically secure under a certain number-theoretic hardness assumption (a specific variant of the ... more >>>

A Noisy Interpolating Set (NIS) for degree $d$ polynomials is a set $S \subseteq \F^n$, where $\F$ is a finite field, such that any degree $d$ polynomial $q \in \F[x_1,\ldots,x_n]$ can be efficiently interpolated from its values on $S$, even if an adversary corrupts a constant fraction of the values. ... more >>>

Computing the Fourier transform is a basic building block used in numerous applications. For data intensive applications, even the $O(N\log N)$ running time of the Fast Fourier Transform (FFT) algorithm may be too slow, and {\em sub-linear} running time is necessary. Clearly, outputting the entire Fourier transform in sub-linear time ... more >>>