Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > EXPANDER CODES:
Reports tagged with expander codes:
TR10-171 | 11th November 2010
Michael Viderman

A Note on high-rate Locally Testable Codes with sublinear query complexity

Inspired by recent construction of high-rate locally correctable codes with sublinear query complexity due to
Kopparty, Saraf and Yekhanin (2010) we address the similar question for locally testable codes (LTCs).

In this note we show a construction of high-rate LTCs with sublinear query complexity.
More formally, we show that for ... more >>>


TR11-058 | 15th April 2011
Michael Viderman

Linear time decoding of regular expander codes

Revisions: 1

Sipser and Spielman (IEEE IT, 1996) showed that any $(c,d)$-regular expander code with expansion parameter $> \frac{3}{4}$ is decodable in \emph{linear time} from a constant fraction of errors. Feldman et al. (IEEE IT, 2007)
proved that expansion parameter $> \frac{2}{3} + \frac{1}{3c}$ is sufficient to correct a constant fraction of ... more >>>


TR19-122 | 13th September 2019
Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas, Mary Wootters

LDPC Codes Achieve List-Decoding Capacity

We show that Gallager's ensemble of Low-Density Parity Check (LDPC) codes achieve list-decoding capacity. These are the first graph-based codes shown to have this property. Previously, the only codes known to achieve list-decoding capacity were completely random codes, random linear codes, and codes constructed by algebraic (rather than combinatorial) techniques. ... more >>>




ISSN 1433-8092 | Imprint