Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > LIST DECODABLE CODES:
Reports tagged with List Decodable Codes:
TR10-047 | 23rd March 2010
Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma

#### Local list decoding with a constant number of queries

Revisions: 1

Recently Efremenko showed locally-decodable codes of sub-exponential
length. That result showed that these codes can handle up to
$\frac{1}{3}$ fraction of errors. In this paper we show that the
same codes can be locally unique-decoded from error rate
$\half-\alpha$ for any $\alpha>0$ and locally list-decoded from
error rate $1-\alpha$ ... more >>>

TR10-134 | 23rd August 2010
Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma

#### A Note on Amplifying the Error-Tolerance of Locally Decodable Codes

Revisions: 2

We show a generic, simple way to amplify the error-tolerance of locally decodable codes.
Specifically, we show how to transform a locally decodable code that can tolerate a constant fraction of errors
to a locally decodable code that can recover from a much higher error-rate. We also show how to ... more >>>

TR14-007 | 17th January 2014
Mark Braverman, Klim Efremenko

#### List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise

In this paper we extend the notion of list decoding to the setting of interactive communication and study its limits. In particular, we show that any protocol can be encoded, with a constant rate, into a list-decodable protocol which is resilient
to a noise rate of up to $1/2-\varepsilon$, ... more >>>

TR16-134 | 29th August 2016
Ronen Shaltiel, Jad Silbak

Revisions: 1

A stochastic code is a pair of encoding and decoding procedures $(Enc,Dec)$ where $Enc:\{0,1\}^k \times \{0,1\}^d \to \{0,1\}^n$, and a message $m \in \{0,1\}^k$ is encoded by $Enc(m,S)$ where $S \from \{0,1\}^d$ is chosen uniformly by the encoder. The code is $(p,L)$-list-decodable against a class $\mathcal{C}$ of channel functions'' $C:\{0,1\}^n ... more >>> TR18-091 | 4th May 2018 Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters #### Improved decoding of Folded Reed-Solomon and Multiplicity Codes Revisions: 1 In this work, we show new and improved error-correcting properties of folded Reed-Solomon codes and multiplicity codes. Both of these families of codes are based on polynomials over finite fields, and both have been the sources of recent advances in coding theory. Folded Reed-Solomon codes were the first explicit constructions ... more >>> TR19-080 | 1st June 2019 Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, Shashwat Silas #### On List Recovery of High-Rate Tensor Codes We continue the study of list recovery properties of high-rate tensor codes, initiated by Hemenway, Ron-Zewi, and Wootters (FOCS'17). In that work it was shown that the tensor product of an efficient (poly-time) high-rate globally list recoverable code is {\em approximately} locally list recoverable, as well as globally list recoverable ... more >>> TR20-013 | 17th February 2020 Noga Ron-Zewi, Mary Wootters, Gilles Z\'{e}mor #### Linear-time Erasure List-decoding of Expander Codes Revisions: 1 We give a linear-time erasure list-decoding algorithm for expander codes. More precisely, let$r > 0$be any integer. Given an inner code$\cC_0$of length$d$, and a$d$-regular bipartite expander graph$G$with$n$vertices on each side, we give an algorithm to list-decode the expander code$\cC ... more >>>

TR20-179 | 2nd December 2020
Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan

#### Decoding Multivariate Multiplicity Codes on Product Sets

The multiplicity Schwartz-Zippel lemma bounds the total multiplicity of zeroes of a multivariate polynomial on a product set. This lemma motivates the multiplicity codes of Kopparty, Saraf and Yekhanin [J. ACM, 2014], who showed how to use this lemma to construct high-rate locally-decodable codes. However, the algorithmic results about these ... more >>>

TR21-106 | 22nd July 2021
Eshan Chattopadhyay, Jesse Goodman, David Zuckerman

#### The Space Complexity of Sampling

Revisions: 1

Recently, there has been exciting progress in understanding the complexity of distributions. Here, the goal is to quantify the resources required to generate (or sample) a distribution. Proving lower bounds in this new setting is more challenging than in the classical setting, and has yielded interesting new techniques and surprising ... more >>>

TR22-027 | 22nd February 2022
Guy Blanc, Dean Doron

#### New Near-Linear Time Decodable Codes Closer to the GV Bound

Revisions: 1

We construct a family of binary codes of relative distance $\frac{1}{2}-\varepsilon$ and rate $\varepsilon^{2} \cdot 2^{-\log^{\alpha}(1/\varepsilon)}$ for $\alpha \approx \frac{1}{2}$ that are decodable, probabilistically, in near linear time. This improves upon the rate of the state-of-the-art near-linear time decoding near the GV bound due to Jeronimo, Srivastava, and Tulsiani, who ... 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 >>>

ISSN 1433-8092 | Imprint