Electronic Colloquium on Computational Complexity
Login | Register | Classic Style

Reports tagged with List decoding:
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 >>>

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

TR03-042 | 15th May 2003
Luca Trevisan

List Decoding Using the XOR Lemma

We show that Yao's XOR Lemma, and its essentially equivalent
rephrasing as a Direct Product Lemma, can be
re-interpreted as a way of obtaining error-correcting
codes with good list-decoding algorithms from error-correcting
codes having weak unique-decoding algorithms. To get codes
with good rate and efficient list decoding algorithms
one needs ... 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 >>>

TR05-132 | 8th November 2005
Venkatesan Guruswami

Algebraic-geometric generalizations of the Parvaresh-Vardy codes

This paper is concerned with a new family of error-correcting codes
based on algebraic curves over finite fields, and list decoding
algorithms for them. The basic goal in the subject of list decoding is
to construct error-correcting codes $C$ over some alphabet $\Sigma$
which have good rate $R$, and at ... more >>>

TR08-020 | 7th March 2008
Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan

Decodability of Group Homomorphisms beyond the Johnson Bound

Given a pair of finite groups $G$ and $H$, the set of homomorphisms from $G$ to $H$ form an error-correcting code where codewords differ in at least $1/2$ the coordinates. We show that for every pair of {\em abelian} groups $G$ and $H$, the resulting code is (locally) list-decodable from ... more >>>

TR08-034 | 19th January 2008
Dan Gutfreund, Guy Rothblum

The Complexity of Local List Decoding

Revisions: 1

We study the complexity of locally list-decoding binary error correcting codes with good parameters (that are polynomially related to information theoretic bounds). We show that computing majority over $\Theta(1/\eps)$ bits is essentially equivalent to locally list-decoding binary codes from relative distance $1/2-\eps$ with list size $\poly(1/\eps)$. That is, a local-decoder ... more >>>

TR08-036 | 14th March 2008
Venkatesan Guruswami, Atri Rudra

Soft decoding, dual BCH codes, and better list-decodable eps-biased codes

We construct binary linear codes that are efficiently list-decodable
up to a fraction $(1/2-\eps)$ of errors. The codes encode $k$ bits
into $n = {\rm poly}(k/\eps)$ bits and are constructible and
list-decodable in time polynomial in $k$ and $1/\eps$ (in
particular, in our results $\eps$ need ... 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 >>>

TR08-105 | 26th November 2008
Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra, Prasad Raghavendra

List Decoding Tensor Products and Interleaved Codes

We design the first efficient algorithms and prove new combinatorial bounds for list decoding tensor products of codes and interleaved codes.

1)We show that for every code, the ratio of its list decoding radius to its minimum distance stays unchanged under the tensor product operation (rather than squaring, as one ... more >>>

TR08-111 | 14th November 2008
Shachar Lovett, Tali Kaufman

The List-Decoding Size of Reed-Muller Codes

Revisions: 2

In this work we study the list-decoding size of Reed-Muller codes. Given a received word and a distance parameter, we are interested in bounding the size of the list of Reed-Muller codewords that are within that distance from the received word. Previous bounds of Gopalan, Klivans and Zuckerman~\cite{GKZ08} on the ... more >>>

TR09-001 | 26th November 2008
Venkatesan Guruswami

Artin automorphisms, Cyclotomic function fields, and Folded list-decodable codes

Algebraic codes that achieve list decoding capacity were recently
constructed by a careful ``folding'' of the Reed-Solomon code. The
``low-degree'' nature of this folding operation was crucial to the list
decoding algorithm. We show how such folding schemes conducive to list
decoding arise out of the Artin-Frobenius automorphism at primes ... more >>>

TR09-004 | 15th January 2009
Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan

Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers

Revisions: 2

We extend the ``method of multiplicities'' to get the following results, of interest in combinatorics and randomness extraction.
\item We show that every Kakeya set in $\F_q^n$, the $n$-dimensional vector space over the finite field on $q$ elements, must be of size at least $q^n/2^n$. This bound is tight ... 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 >>>

TR11-080 | 11th May 2011
mohammad iftekhar husain, steve ko, Atri Rudra, steve uurtamo

Storage Enforcement with Kolmogorov Complexity and List Decoding

We consider the following problem that arises in outsourced storage: a user stores her data $x$ on a remote server but wants to audit the server at some later point to make sure it actually did store $x$. The goal is to design a (randomized) verification protocol that has the ... more >>>

TR11-165 | 8th December 2011
Elena Grigorescu, Chris Peikert

List Decoding Barnes-Wall Lattices

Revisions: 2

The question of list decoding error-correcting codes over finite fields (under the Hamming metric) has been widely studied in recent years. Motivated by the similar discrete structure of linear codes and point lattices in $R^{N}$, and their many shared applications across complexity theory, cryptography, and coding theory, we initiate the ... more >>>

TR13-031 | 22nd February 2013
Irit Dinur, Elazar Goldenberg

Clustering in the Boolean Hypercube in a List Decoding Regime

Revisions: 2

We consider the following clustering with outliers problem: Given a set of points $X \subset \{-1,1\}^n$, such that there is some point $z \in \{-1,1\}^n$ for which at least $\delta$ of the points are $\epsilon$-correlated with $z$, find $z$. We call such a point $z$ a $(\delta,\epsilon)$-center of X.

In ... more >>>

TR14-087 | 12th July 2014
Abhishek Bhowmick, Shachar Lovett

List decoding Reed-Muller codes over small fields

Revisions: 1

The list decoding problem for a code asks for the maximal radius up to which any ball of that radius contains only a constant number of codewords. The list decoding radius is not well understood even for well studied codes, like Reed-Solomon or Reed-Muller codes.

Fix a finite field $\mathbb{F}$. ... more >>>

TR14-104 | 9th August 2014
Atri Rudra, Mary Wootters

It'll probably work out: improved list-decoding through random operations

In this work, we introduce a framework to study the effect of random operations on the combinatorial list decodability of a code.
The operations we consider correspond to row and column operations on the matrix obtained from the code by stacking the codewords together as columns. This captures many natural ... more >>>

TR15-077 | 4th May 2015
Arnab Bhattacharyya, Abhishek Bhowmick

Using higher-order Fourier analysis over general fields

Higher-order Fourier analysis, developed over prime fields, has been recently used in different areas of computer science, including list decoding, algorithmic decomposition and testing. We extend the tools of higher-order Fourier analysis to analyze functions over general fields. Using these new tools, we revisit the results in the above areas.

... more >>>

TR15-096 | 5th June 2015
Abhishek Bhowmick, Shachar Lovett

Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory

Let $f$ be a polynomial of degree $d$ in $n$ variables over a finite field $\mathbb{F}$. The polynomial is said to be unbiased if the distribution of $f(x)$ for a uniform input $x \in \mathbb{F}^n$ is close to the uniform distribution over $\mathbb{F}$, and is called biased otherwise. The polynomial ... more >>>

ISSN 1433-8092 | Imprint