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

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

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

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

ISSN 1433-8092 | Imprint