Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > LOCALLY DECODABLE CODE:
Reports tagged with locally decodable code:
TR13-053 | 4th April 2013
Alan Guo

High rate locally correctable codes via lifting

Revisions: 1

We present a general framework for constructing high rate error correcting codes that are locally correctable (and hence locally decodable if linear) with a sublinear number of queries, based on lifting codes with respect to functions on the coordinates. Our approach generalizes the lifting of affine-invariant codes of Guo, Kopparty, ... more >>>


TR16-189 | 21st November 2016
Arnab Bhattacharyya, Sivakanth Gopi

Lower bounds for 2-query LCCs over large alphabet

A locally correctable code (LCC) is an error correcting code that allows correction of any arbitrary coordinate of a corrupted codeword by querying only a few coordinates.
We show that any zero-error $2$-query locally correctable code $\mathcal{C}: \{0,1\}^k \to \Sigma^n$ that can correct a constant fraction of corrupted symbols must ... more >>>


TR18-091 | 4th May 2018
Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters

Improved decoding of Folded Reed-Solomon and Multiplicity Codes

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




ISSN 1433-8092 | Imprint