Scott E. Decatur, Oded Goldreich, Dana Ron

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

Venkatesan Guruswami, Madhu Sudan

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

Oded Goldreich, Dana Ron, Madhu Sudan

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

Ilya Dumer, Daniele Micciancio, Madhu Sudan

We show that the minimum distance of a linear code (or

equivalently, the weight of the lightest codeword) is

not approximable to within any constant factor in random polynomial

time (RP), unless NP equals RP.

Under the stronger assumption that NP is not contained in RQP

(random ...
more >>>

Oded Goldreich, Howard Karloff, Leonard Schulman, Luca Trevisan

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

Piotr Indyk

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

Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan

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

Eli Ben-Sasson, Madhu Sudan

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

Oded Goldreich

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

Don Coppersmith, Atri Rudra

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

Amir Shpilka

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

Brett Hemenway, Rafail Ostrovsky

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

...
more >>>

Zeev Dvir, Amir Shpilka

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

Adi Akavia

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

Eli Ben-Sasson

This paper describes recent results which revolve around the question of the rate attainable by families of error correcting codes that are locally testable. Emphasis is placed on motivating the problem of proving upper bounds on the rate of these codes and a number of interesting open questions for future ... more >>>

Or Meir

The IP theorem, which asserts that IP = PSPACE (Lund et. al., and Shamir, in J. ACM 39(4)), is one of the major achievements of complexity theory. The known proofs of the theorem are based on the arithmetization technique, which transforms a quantified Boolean formula into a related polynomial. The ... more >>>

Eli Ben-Sasson, Ariel Gabizon, Yohay Kaplan, Swastik Kopparty, Shubhangi Saraf

We describe new constructions of error correcting codes, obtained by "degree-lifting" a short algebraic geometry (AG) base-code of block-length $q$ to a lifted-code of block-length $q^m$, for arbitrary integer $m$. The construction generalizes the way degree-$d$, univariate polynomials evaluated over the $q$-element field (also known as Reed-Solomon codes) are "lifted" ... more >>>

Mahdi Cheraghchi, Anna Gal, Andrew Mills

Locally decodable codes (LDCs) are error correcting codes with the extra property that it is sufficient to read just a small number of positions of a possibly corrupted codeword in order to recover any one position of the input. To achieve this, it is necessary to use randomness in the ... more >>>

Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, Henning Stichtenoth

The PCP theorem (Arora et. al., J. ACM 45(1,3)) says that every NP-proof can be encoded to another proof, namely, a probabilistically checkable proof (PCP), which can be tested by a verifier that queries only a small part of the PCP. A natural question is how large is the blow-up ... more >>>

Eli Ben-Sasson, Swastik Kopparty, Shubhangi Saraf

Algebraic proof systems reduce computational problems to problems about estimating the distance of a sequence of functions $u=(u_1,\ldots, u_k)$, given as oracles, from a linear error correcting code $V$. The soundness of such systems relies on methods that act ``locally'' on $u$ and map it to a single function $u^*$ ... more >>>

Dmitry Itsykson, Alexander Knop, Andrei Romashchenko, Dmitry Sokolov

In 2004 Atserias, Kolaitis and Vardi proposed OBDD-based propositional proof systems that prove unsatisfiability of a CNF formula by deduction of identically false OBDD from OBDDs representing clauses of the initial formula. All OBDDs in such proofs have the same order of variables. We initiate the study of OBDD based ... more >>>