Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > LOCALLY CORRECTABLE CODES:
Reports tagged with Locally correctable codes:
TR11-054 | 13th April 2011
Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka

#### Tight lower bounds for 2-query LCCs over finite fields

A Locally Correctable Code (LCC) is an error correcting code that has a probabilistic
self-correcting algorithm that, with high probability, can correct any coordinate of the
codeword by looking at only a few other coordinates, even if a fraction $\delta$ of the
coordinates are corrupted. LCC's are a stronger form ... more >>>

TR12-148 | 7th November 2012
Eli Ben-Sasson, Ariel Gabizon, Yohay Kaplan, Swastik Kopparty, Shubhangi Saraf

#### A new family of locally correctable codes based on degree-lifted algebraic geometry codes

Revisions: 1

We describe new constructions of error correcting codes, obtained by "degree-lifting" a short algebraic geometry (AG) base-code of block-length $q$ to a lifted-code of block-length $q^m$, for arbitrary integer $m$. The construction generalizes the way degree-$d$, univariate polynomials evaluated over the $q$-element field (also known as Reed-Solomon codes) are "lifted" ... more >>>

TR15-068 | 21st April 2015
Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf

#### High rate locally-correctable and locally-testable codes with sub-polynomial query complexity

Revisions: 2

In this work, we construct the first locally-correctable codes (LCCs), and locally-testable codes (LTCs) with constant rate, constant relative distance, and sub-polynomial query complexity. Specifically, we show that there exist binary LCCs and LTCs with block length $n$, constant rate (which can even be taken arbitrarily close to 1), constant ... more >>>

TR15-110 | 8th July 2015
Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf

#### High-rate Locally-testable Codes with Quasi-polylogarithmic Query Complexity

Revisions: 1

An error correcting code is said to be \emph{locally testable} if
there is a test that checks whether a given string is a codeword,
or rather far from the code, by reading only a small number of symbols
of the string. Locally testable codes (LTCs) are both interesting
in their ... more >>>

TR17-143 | 26th September 2017
Tom Gur, Govind Ramnarayan, Ron Rothblum

#### Relaxed Locally Correctable Codes

Revisions: 1

Locally decodable codes (LDCs) and locally correctable codes (LCCs) are error-correcting codes in which individual bits of the message and codeword, respectively, can be recovered by querying only few bits from a noisy codeword. These codes have found numerous applications both in theory and in practice.

A natural relaxation of ... 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-113 | 27th July 2020
Alessandro Chiesa, Tom Gur, Igor Shinkar

#### Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity

Locally correctable codes (LCCs) are error correcting codes C : \Sigma^k \to \Sigma^n which admit local algorithms that correct any individual symbol of a corrupted codeword via a minuscule number of queries. This notion is stronger than that of locally decodable codes (LDCs), where the goal is to only recover ... more >>>

ISSN 1433-8092 | Imprint