Fetching the paper…

Reading the bibliography…

Locally testable codes via high-dimensional expanders · Around

2020

Locally testable codes via high-dimensional expanders

Dikstein, Yotam, Dinur, Irit, Harsha, Prahladh et al.

Original
PDF
Post on X

Understand

Locally testable codes (LTC) are error-correcting codes that have a local tester which can distinguish valid codewords from words that are "far" from all codewords by probing a given word only at a very few (sublinear, typically constant) number of locations.

Such codes form the combinatorial backbone of PCPs.
A major open problem is whether there exist LTCs with positive rate, constant relative distance and testable with a constant number of queries.
In this paper, we present a new approach towards constructing such LTCs using the machinery of high-dimensional expanders.

Built on

Low Density Parity Check Codes
1960
Earlier work this paper cites.
A recursive approach to low complexity codes
1981
Earlier work this paper cites.
Self-testing/correcting with applications to numerical problems
1993
Earlier work this paper cites.
Probabilistic checking of proofs and the hardness of approximation problems
1994
Earlier work this paper cites.
Computationally Efficient Error-Correcting Codes and Holographic Proofs
1995
Earlier work this paper cites.
Robust characterizations of polynomials with applications to program testing
1996
Earlier work this paper cites.

Similar

Expander codes
1996
Cited alongside, same era.
Improved low-degree testing and its applications
2003
Cited alongside, same era.
Some applications of coding theory in computational complexity
2004
Cited alongside, same era.
Some 3CNF properties are hard to test
2005
Cited alongside, same era.
The PCP theorem by gap amplification
2005
Cited alongside, same era.
Locally testable codes and PCPs of almost linear length
2006
Cited alongside, same era.
Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
Cited in the paper.

Then

Homological connectivity of random 2-complexes
2006
Later among the works it cites.
Short PCPs with polylog query complexity
2008
Later among the works it cites.
Singularities, expanders and topology of maps. Part 2: from combinatorics to topology via algebraic isoperimetry
2010
Later among the works it cites.
Absolutely sound testing of lifted codes
2015
Later among the works it cites.
On expansion and topological overlap
Original
2018
Later among the works it cites.
Local spectral expansion approach to high dimensional expanders part I: Descent of spectral gaps
Original
2018

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Checking computations in polylogarithmic time

Cited in the paper.

Robust PCPs of proximity, shorter PCPs and applications to coding

Cited in the paper.

Symmetric LDPC codes are not necessarily locally testable

Cited in the paper.

Agreement testing theorems on layered set systems

Cited in the paper.

Boolean function analysis on high-dimensional expanders

Cited in the paper.

Later among the works it cites.