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