Boaz Barak, Oded Goldreich

We put forward a new type of

computationally-sound proof systems, called universal-arguments,

which are related but different from both CS-proofs (as defined

by Micali) and arguments (as defined by Brassard, Chaum and

Crepeau). In particular, we adopt the instance-based

prover-efficiency paradigm of CS-proofs, but follow the

computational-soundness condition of ...
more >>>

Oded Goldreich, Madhu Sudan

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

Eli Ben-Sasson, Oded Goldreich, Madhu Sudan

We present upper bounds on the size of codes that are locally

testable by querying only two input symbols. For linear codes, we

show that any $2$-locally testable code with minimal distance

$\delta n$ over a finite field $F$ cannot have more than

$|F|^{3/\delta}$ codewords. This result holds even ...
more >>>

Scott Aaronson

Several researchers, including Leonid Levin, Gerard 't Hooft, and

Stephen Wolfram, have argued that quantum mechanics will break down

before the factoring of large numbers becomes possible. If this is

true, then there should be a natural "Sure/Shor separator" -- that is,

a set of quantum ...
more >>>

Venkatesan Guruswami

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

Venkatesan Guruswami, Alexander Vardy

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

Luca Trevisan

Error-correcting codes and related combinatorial constructs

play an important role in several recent (and old) results

in computational complexity theory. In this paper we survey

results on locally-testable and locally-decodable error-correcting

codes, and their applications to complexity theory and to

cryptography.

Locally decodable codes are error-correcting codes ... more >>>

Venkatesan Guruswami, Atri Rudra

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

Venkatesan Guruswami, Valentine Kabanets

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

Joshua Buresh-Oppenheim, Valentine Kabanets, Rahul Santhanam

We consider the problem of amplifying uniform average-case hardness

of languages in $\NP$, where hardness is with respect to $\BPP$

algorithms. We introduce the notion of \emph{monotone}

error-correcting codes, and show that hardness amplification for

$\NP$ is essentially equivalent to constructing efficiently

\emph{locally} encodable and \emph{locally} list-decodable monotone

codes. The ...
more >>>

Tali Kaufman, Madhu Sudan

We show that random sparse binary linear codes are locally testable and locally decodable (under any linear encoding) with constant queries (with probability tending to one). By sparse, we mean that the code should have only polynomially many codewords. Our results are the first to show that local decodability and ... more >>>

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson

The classical Direct-Product Theorem for circuits says

that if a Boolean function $f:\{0,1\}^n\to\{0,1\}$ is somewhat hard

to compute on average by small circuits, then the corresponding

$k$-wise direct product function

$f^k(x_1,\dots,x_k)=(f(x_1),\dots,f(x_k))$ (where each

$x_i\in\{0,1\}^n$) is significantly harder to compute on average by

slightly smaller ...
more >>>

Stasys Jukna, Georg Schnitger

A completion of an m-by-n matrix A with entries in {0,1,*} is obtained

by setting all *-entries to constants 0 or 1. A system of semi-linear

equations over GF(2) has the form Mx=f(x), where M is a completion of

A and f:{0,1}^n --> {0,1}^m is an operator, the i-th coordinate ...
more >>>

Victor Chen, Elena Grigorescu, Ronald de Wolf

We construct efficient data structures that are resilient against a constant fraction of adversarial noise. Our model requires that the decoder answers most queries correctly with high probability and for the remaining queries, the

decoder with high probability either answers correctly or declares ``don't know.'' Furthermore, if there is no ...
more >>>

Swastik Kopparty, Shubhangi Saraf

In this paper, we give surprisingly efficient algorithms for list-decoding and testing

{\em random} linear codes. Our main result is that random sparse linear codes are locally testable and locally list-decodable

in the {\em high-error} regime with only a {\em constant} number of queries.

More precisely, we show that ...
more >>>

Atri Rudra, steve uurtamo

We prove the following results concerning the list decoding of error-correcting codes:

We show that for any code with a relative distance of $\delta$

(over a large enough alphabet), the

following result holds for random errors: With high probability,

for a $\rho\le \delta -\eps$ fraction of random errors (for any ...
more >>>

Venkatesan Guruswami, Adam Smith

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

Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin

Locally decodable codes are error-correcting codes that admit efficient decoding algorithms; any bit of the original message can be recovered by looking at only a small number of locations of a corrupted codeword. The tradeoff between the rate of a code and the locality/efficiency of its decoding algorithms has been ... more >>>

Michael Viderman

Inspired by recent construction of high-rate locally correctable codes with sublinear query complexity due to

Kopparty, Saraf and Yekhanin (2010) we address the similar question for locally testable codes (LTCs).

In this note we show a construction of high-rate LTCs with sublinear query complexity.

More formally, we show that for ...
more >>>

Madhu Sudan

The last two decades have seen enormous progress in the development of sublinear-time algorithms --- i.e., algorithms that examine/reveal properties of ``data'' in less time than it would take to read all of the data. A large, and important, subclass of such properties turn out to be ``linear''. In particular, ... more >>>

Michael Viderman

Sipser and Spielman (IEEE IT, 1996) showed that any $(c,d)$-regular expander code with expansion parameter $> \frac{3}{4}$ is decodable in \emph{linear time} from a constant fraction of errors. Feldman et al. (IEEE IT, 2007)

proved that expansion parameter $> \frac{2}{3} + \frac{1}{3c}$ is sufficient to correct a constant fraction of ...
more >>>

Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan

Affine-invariant properties are an abstract class of properties that generalize some

central algebraic ones, such as linearity and low-degree-ness, that have been

studied extensively in the context of property testing. Affine invariant properties

consider functions mapping a big field $\mathbb{F}_{q^n}$ to the subfield $\mathbb{F}_q$ and include all

properties that form ...
more >>>

Swastik Kopparty

We study the list-decodability of multiplicity codes. These codes, which are based on evaluations of high-degree polynomials and their derivatives, have rate approaching $1$ while simultaneously allowing for sublinear-time error-correction. In this paper, we show that multiplicity codes also admit powerful list-decoding and local list-decoding algorithms correcting a large fraction ... more >>>

Madhu Sudan, Noga Ron-Zewi

Over a finite field $\F_q$ the $(n,d,q)$-Reed-Muller code is the code given by evaluations of $n$-variate polynomials of total degree at most $d$ on all points (of $\F_q^n$). The task of testing if a function $f:\F_q^n \to \F_q$ is close to a codeword of an $(n,d,q)$-Reed-Muller code has been of ... more >>>

Alan Guo, Madhu Sudan

We prove that the class of locally testable affine-invariant properties is closed under sums, intersections and "lifts". The sum and intersection are two natural operations on linear spaces of functions, where the sum of two properties is simply their sum as a vector space. The "lift" is a less natural ... more >>>

Michael Viderman

An error-correcting code $C \subseteq \F^n$ is called $(q,\epsilon)$-strong locally testable code (LTC) if there exists a randomized algorithm (tester) that makes at most $q$ queries to the input word. This algorithm accepts all codewords with probability 1 and rejects all non-codewords $x\notin C$ with probability at least $\epsilon \cdot ... more >>>

Michael Viderman

An error-correcting code $C \subseteq \F^n$ is called $(q,\epsilon)$-strong locally testable code (LTC) if there exists a tester that makes at most $q$ queries to the input word. This tester accepts all codewords with probability 1 and rejects all non-codewords $x\notin C$ with probability at least $\epsilon \cdot \delta(x,C)$, where ... more >>>

Michael Viderman