Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with List Decoding Capacity:
TR05-133 | 17th November 2005
Venkatesan Guruswami, Atri Rudra

Explicit Capacity-Achieving List-Decodable Codes

Revisions: 1

For every $0 < R < 1$ and $\eps > 0$, we present an explicit
construction of error-correcting codes of rate $R$ that can be list
decoded in polynomial time up to a fraction $(1-R-\eps)$ of errors.
These codes achieve the ``capacity'' for decoding from {\em ... more >>>

TR07-109 | 7th October 2007
Venkatesan Guruswami, Atri Rudra

Better Binary List-Decodable Codes via Multilevel Concatenation

We give a polynomial time construction of binary codes with the best
currently known trade-off between rate and error-correction
radius. Specifically, we obtain linear codes over fixed alphabets
that can be list decoded in polynomial time up to the so called
Blokh-Zyablov bound. Our work ... more >>>

TR08-054 | 13th May 2008
Venkatesan Guruswami, Atri Rudra

Concatenated codes can achieve list-decoding capacity

We prove that binary linear concatenated codes with an outer algebraic code (specifically, a folded Reed-Solomon code) and independently and randomly chosen linear inner codes achieve the list-decoding capacity with high probability. In particular, for any $0 < \rho < 1/2$ and $\epsilon > 0$, there exist concatenated codes of ... more >>>

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

LDPC Codes Achieve List-Decoding Capacity

Revisions: 2

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