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:
TR97-028 | 12th July 1997
Scott E. Decatur, Oded Goldreich, Dana Ron

Computational Sample Complexity


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


TR98-043 | 27th July 1998
Venkatesan Guruswami, Madhu Sudan

Improved decoding of Reed-Solomon and algebraic-geometric codes.

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


TR98-062 | 28th October 1998
Oded Goldreich, Dana Ron, Madhu Sudan

Chinese Remaindering with Errors

Revisions: 4 , Comments: 1

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


TR99-029 | 31st August 1999
Ilya Dumer, Daniele Micciancio, Madhu Sudan

Hardness of approximating the minimum distance of a linear code

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


TR01-080 | 14th November 2001
Oded Goldreich, Howard Karloff, Leonard Schulman, Luca Trevisan

Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval

Revisions: 3


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


TR02-024 | 24th April 2002
Piotr Indyk

List-decoding in Linear Time

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


TR04-021 | 23rd March 2004
Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan

Robust PCPs of Proximity, Shorter PCPs and Applications to Coding

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


TR04-060 | 22nd July 2004
Eli Ben-Sasson, Madhu Sudan

Simple PCPs with Poly-log Rate and Query Complexity

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


TR05-014 | 30th January 2005
Oded Goldreich

Short Locally Testable Codes and Proofs (Survey)


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


TR05-104 | 16th September 2005
Don Coppersmith, Atri Rudra

On the Robust Testability of Product of Codes

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


TR05-155 | 10th December 2005
Amir Shpilka

Constructions of low-degree and error-correcting epsilon-biased sets

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


TR07-021 | 5th March 2007
Brett Hemenway, Rafail Ostrovsky

Public Key Encryption Which is Simultaneously a Locally-Decodable Error-Correcting Code

Revisions: 3

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


TR08-004 | 2nd January 2008
Zeev Dvir, Amir Shpilka

Noisy Interpolating Sets for Low Degree Polynomials

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


TR08-102 | 9th November 2008
Adi Akavia

Finding Significant Fourier Transform Coefficients Deterministically and Locally

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


TR10-123 | 4th August 2010
Eli Ben-Sasson

Limitation on the rate of families of locally testable codes

Revisions: 1

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


TR10-137 | 29th August 2010
Or Meir

IP = PSPACE using Error Correcting Codes

Revisions: 7

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


TR12-148 | 7th November 2012
Eli Ben-Sasson, Ariel Gabizon, Yohay Kaplan, Swastik Kopparty, Shubhangi Saraf

A new family of locally correctable codes based on degree-lifted algebraic geometry codes

Revisions: 1

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


TR12-172 | 8th December 2012
Mahdi Cheraghchi, Anna Gal, Andrew Mills

Correctness and Corruption of Locally Decodable Codes

Revisions: 1

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


TR13-085 | 13th June 2013
Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, Henning Stichtenoth

Constant rate PCPs for circuit-SAT with sublinear query complexity

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


TR18-090 | 4th May 2018
Eli Ben-Sasson, Swastik Kopparty, Shubhangi Saraf

Worst-case to average case reductions for the distance to a code

Revisions: 1

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


TR19-001 | 5th January 2019
Dmitry Itsykson, Alexander Knop, Andrei Romashchenko, Dmitry Sokolov

On OBDD-based algorithms and proof systems that dynamically change order of variables

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


TR20-038 | 15th March 2020
Ofer Grossman, Justin Holmgren

Error Correcting Codes for Uncompressed Messages

Most types of messages we transmit (e.g., video, audio, images, text) are not fully compressed, since they do not have known efficient and information theoretically optimal compression algorithms. When transmitting such messages, standard error correcting codes fail to take advantage of the fact that messages are not fully compressed.

We ... more >>>


TR20-156 | 22nd October 2020
Sankeerth Rao Karingula, Shachar Lovett

Codes over integers, and the singularity of random matrices with large entries

Revisions: 1

The prototypical construction of error correcting codes is based on linear codes over finite fields. In this work, we make first steps in the study of codes defined over integers. We focus on Maximum Distance Separable (MDS) codes, and show that MDS codes with linear rate and distance can be ... more >>>


TR22-069 | 28th April 2022
Silas Richelson, Sourya Roy

List-Decoding Random Walk XOR Codes Near the Johnson Bound

Revisions: 1

In a breakthrough result, Ta-Shma described an explicit construction of an almost optimal binary code (STOC 2017). Ta-Shma's code has distance $\frac{1-\varepsilon}{2}$ and rate $\Omega\bigl(\varepsilon^{2+o(1)}\bigr)$ and thus it almost achieves the Gilbert-Varshamov bound, except for the $o(1)$ term in the exponent. The prior best list-decoding algorithm for (a variant of) ... more >>>


TR22-095 | 5th July 2022
Meghal Gupta, Rachel Zhang

Efficient Interactive Coding Achieving Optimal Error Resilience Over the Binary Channel

Given a noiseless protocol $\pi_0$ computing a function $f(x, y)$ of Alice and Bob's private inputs $x, y$, the goal of interactive coding is to construct an error-resilient protocol $\pi$ computing $f$ such that even if some fraction of the communication is adversarially corrupted, both parties still learn $f(x, y)$. ... more >>>


TR22-117 | 23rd August 2022
Ronen Shaltiel, Jad Silbak

Error Correcting Codes that Achieve BSC Capacity Against Channels that are Poly-Size Circuits

Guruswami and Smith (J. ACM 2016) considered codes for channels that are poly-size circuits which modify at most a $p$-fraction of the bits of the codeword. This class of channels is significantly stronger than Shannon's binary symmetric channel (BSC), but weaker than Hamming's channels which are computationally unbounded.
Guruswami and ... more >>>


TR23-066 | 4th May 2023
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Protecting Single-Hop Radio Networks from Message Drops

Single-hop radio networks (SHRN) are a well studied abstraction of communication over a wireless channel. In this model, in every round, each of the $n$ participating parties may decide to broadcast a message to all the others, potentially causing collisions. We consider the SHRN model in the presence of stochastic ... more >>>




ISSN 1433-8092 | Imprint