Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > REED-SOLOMON CODES:
Reports tagged with Reed-Solomon codes:
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 >>>

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

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

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

TR12-036 | 12th April 2012
Venkatesan Guruswami, Chaoping Xing

#### Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding

We give a new construction of algebraic codes which are efficiently list decodable from a fraction $1-R-\epsilon$ of adversarial errors where $R$ is the rate of the code, for any desired positive constant $\epsilon$. The worst-case list size output by the algorithm is $O(1/\epsilon)$, matching the existential bound for random ... more >>>

TR13-060 | 10th April 2013
Venkatesan Guruswami, Swastik Kopparty

#### Explicit Subspace Designs

A subspace design is a collection $\{H_1,H_2,\dots,H_M\}$ of subspaces of ${\mathbf F}_q^m$ with the property that no low-dimensional subspace $W$ of ${\mathbf F}_q^m$ intersects too many subspaces of the collection. Subspace designs were introduced by Guruswami and Xing (STOC 2013) who used them to give a randomized construction of optimal ... more >>>

TR13-140 | 8th October 2013
Atri Rudra, Mary Wootters

#### Every list-decodable code for high noise has abundant near-optimal rate puncturings

We show that any $q$-ary code with sufficiently good distance can be randomly punctured to obtain, with high probability, a code that is list decodable up to radius $1 - 1/q - \epsilon$ with near-optimal rate and list sizes.

Our results imply that most" Reed-Solomon codes are list decodable ... more >>>

TR15-117 | 21st July 2015
Boris Bukh, Venkatesan Guruswami

#### An improved bound on the fraction of correctable deletions

Revisions: 1

We consider codes over fixed alphabets against worst-case symbol deletions. For any fixed $k \ge 2$, we construct a family of codes over alphabet of size $k$ with positive rate, which allow efficient recovery from a worst-case deletion fraction approaching $1-\frac{2}{k+1}$. In particular, for binary codes, we are able to ... more >>>

TR16-176 | 9th November 2016
Venkata Gandikota, Badih Ghazi, Elena Grigorescu

#### NP-Hardness of Reed-Solomon Decoding, and the Prouhet-Tarry-Escott Problem

Establishing the complexity of {\em Bounded Distance Decoding} for Reed-Solomon codes is a fundamental open problem in coding theory, explicitly asked by Guruswami and Vardy (IEEE Trans. Inf. Theory, 2005). The problem is motivated by the large current gap between the regime when it is NP-hard, and the regime when ... more >>>

TR20-070 | 4th May 2020

#### On the list recoverability of randomly punctured codes

Revisions: 1

We show that a random puncturing of a code with good distance is list recoverable beyond the Johnson bound.
In particular, this implies that there are Reed-Solomon codes that are list recoverable beyond the Johnson bound.
It was previously known that there are Reed-Solomon codes that do not have this ... more >>>

TR20-083 | 30th May 2020
Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf

#### Proximity Gaps for Reed-Solomon Codes

Revisions: 3

A collection of sets displays a proximity gap with respect to some property if for every set in the collection, either (i) all members are $\delta$-close to the property in relative Hamming distance or (ii) only a tiny fraction of members are $\delta$-close to the property. In particular, no set ... more >>>

TR20-172 | 13th November 2020
Venkatesan Guruswami, Chaoping Xing

#### Optimal rate list decoding over bounded alphabets using algebraic-geometric codes

We construct two classes of algebraic code families which are efficiently list decodable with small output list size from a fraction $1-R-\epsilon$ of adversarial errors where $R$ is the rate of the code, for any desired positive constant $\epsilon$. The alphabet size depends only on $\epsilon$ and is nearly-optimal.

The ... more >>>

TR21-139 | 24th September 2021
Venkatesan Guruswami, Jonathan Mosheiff

#### Punctured Large Distance Codes, and Many Reed-Solomon Codes, Achieve List-Decoding Capacity

Revisions: 2

We prove the existence of Reed-Solomon codes of any desired rate $R \in (0,1)$ that are combinatorially list-decodable up to a radius approaching $1-R$, which is the information-theoretic limit. This is established by starting with the full-length $[q,k]_q$ Reed-Solomon code over a field $\mathbb{F}_q$ that is polynomially larger than the ... more >>>

ISSN 1433-8092 | Imprint