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

Venkatesan Guruswami

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

Venkatesan Guruswami, Atri Rudra

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

Venkatesan Guruswami

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

mohammad iftekhar husain, steve ko, Atri Rudra, steve uurtamo

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

Venkatesan Guruswami, Chaoping Xing

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

Venkatesan Guruswami, Swastik Kopparty

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

Atri Rudra, Mary Wootters

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

Boris Bukh, Venkatesan Guruswami

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

Venkata Gandikota, Badih Ghazi, Elena Grigorescu

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

Ben Lund, Aditya Potukuchi

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

Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf

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