Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > ERROR-CORRECTING CODES:
Reports tagged with Error-correcting codes:
TR01-093 | 2nd December 2001
Boaz Barak, Oded Goldreich

Universal Arguments and their Applications


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


TR02-050 | 5th August 2002
Oded Goldreich, Madhu Sudan

Locally Testable Codes and PCPs of Almost-Linear Length

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


TR03-019 | 3rd April 2003
Eli Ben-Sasson, Oded Goldreich, Madhu Sudan

Bounds on 2-Query Codeword Testing.

Revisions: 1


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


TR03-079 | 8th November 2003
Scott Aaronson

Multilinear Formulas and Skepticism of Quantum Computing

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


TR03-080 | 12th November 2003
Venkatesan Guruswami

Better Extractors for Better Codes?

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


TR04-040 | 4th May 2004
Venkatesan Guruswami, Alexander Vardy

Maximum-likelihood decoding of Reed-Solomon codes is NP-hard

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


TR04-043 | 20th May 2004
Luca Trevisan

Some Applications of Coding Theory in Computational Complexity

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


TR05-019 | 9th February 2005
Venkatesan Guruswami, Atri Rudra

Tolerant Locally Testable Codes

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


TR05-057 | 19th May 2005
Venkatesan Guruswami, Valentine Kabanets

Hardness amplification via space-efficient direct products

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


TR06-154 | 13th December 2006
Joshua Buresh-Oppenheim, Valentine Kabanets, Rahul Santhanam

Uniform Hardness Amplification in NP via Monotone Codes

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


TR07-060 | 11th July 2007
Tali Kaufman, Madhu Sudan

Sparse Random Linear Codes are Locally Decodable and Testable

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


TR08-079 | 31st August 2008
Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson

Uniform Direct-Product Theorems: Simplified, Optimized, and Derandomized

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


TR09-008 | 15th January 2009
Stasys Jukna, Georg Schnitger

Min-Rank Conjecture for Log-Depth Circuits

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


TR09-079 | 21st September 2009
Victor Chen, Elena Grigorescu, Ronald de Wolf

Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation

Revisions: 1

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


TR09-115 | 13th November 2009
Swastik Kopparty, Shubhangi Saraf

Local list-decoding and testing of random linear codes from high-error


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


TR10-007 | 12th January 2010
Atri Rudra, steve uurtamo

Two Theorems in List Decoding

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


TR10-077 | 26th April 2010
Venkatesan Guruswami, Adam Smith

Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate

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


TR10-148 | 23rd September 2010
Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin

High-rate codes with sublinear-time decoding

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


TR10-171 | 11th November 2010
Michael Viderman

A Note on high-rate Locally Testable Codes with sublinear query complexity

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


TR11-005 | 20th January 2011
Madhu Sudan

Testing Linear Properties: Some general themes

Revisions: 1

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


TR11-058 | 15th April 2011
Michael Viderman

Linear time decoding of regular expander codes

Revisions: 1

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


TR11-079 | 9th May 2011
Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan

On Sums of Locally Testable Affine Invariant Properties

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


TR12-044 | 22nd April 2012
Swastik Kopparty

List-Decoding Multiplicity Codes

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


TR12-046 | 24th April 2012
Madhu Sudan, Noga Ron-Zewi

A new upper bound on the query complexity for testing generalized Reed-Muller codes

Revisions: 1

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


TR12-048 | 25th April 2012
Alan Guo, Madhu Sudan

Some closure features of locally testable affine-invariant properties

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


TR12-168 | 26th November 2012
Michael Viderman

Strong LTCs with inverse polylogarithmic rate and soundness

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


TR13-022 | 5th February 2013
Michael Viderman

Strong LTCs with inverse poly-log rate and constant soundness

Revisions: 1

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


TR15-020 | 31st January 2015
Michael Viderman

Explicit Strong LTCs with inverse poly-log rate and constant soundness

Revisions: 1

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




ISSN 1433-8092 | Imprint