Name
Title | ||
|---|---|---|
Unique Decoding of Explicit <tex>$\varepsilon$</tex>-balanced Codes Near the Gilbert-Varshamov Bound |
Abstract | ||
|---|---|---|
The Gilbert-Varshamov bound (non-constructively) establishes the existence of binary codes of distance 1/2-ε and rate Ω(ε
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>
) (where an upper bound of O(ε
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>
log(1/ε)) is known). Ta-Shma [STOC 2017] gave an explicit construction of ε-balanced binary codes, where any two distinct codewords are at a distance between 1/2-ε/2 and 1/2+ε/2, achieving a near optimal rate of Ω(ε
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2+β</sup>
), where β→ 0 as ε→ 0. We develop unique and list decoding algorithms for (a slight modification of) the family of codes constructed by Ta-Shma, in the adversarial error model. We prove the following results for ε-balanced codes with block length N and rate Ω(ε
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2+β</sup>
) in this family: -For all , there are explicit codes which can be uniquely decoded up to an error of half the minimum distance in time N
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Oε,β(1)</sup>
. -For any fixed constant β independent of ε, there is an explicit construction of codes which can be uniquely decoded up to an error of half the minimum distance in time (log(1/ε))
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(1)</sup>
·N
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Oβ(1)</sup>
. -For any , there are explicit ε-balanced codes with rate Ω(ε
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2+β</sup>
) which can be list decoded up to error 1/2-ε
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">'</sup>
in time N
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Oε,ε'</sup>
,β(1), where ε
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">'</sup>
,β→ 0 as ε→ 0. The starting point of our algorithms is the framework for list decoding direct-sum codes develop in Alev et al. [SODA 2020], which uses the Sum-of-Squares SDP hierarchy. The rates obtained there were quasipolynomial in ε. Here, we show how to overcome the far from optimal rates of this framework obtaining unique decoding algorithms for explicit binary codes of near optimal rate. These codes are based on simple modifications of Ta-Shma's construction. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1109/FOCS46700.2020.00048 | 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) |
Keywords | DocType | ISSN |
coding theory, sum of squares, sdp, decoding | Conference | 1523-8288 |
ISBN | Citations | PageRank |
978-1-7281-9622-0 | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Fernando Granha Jeronimo | 1 | 2 | 2.42 |
| Dylan Quintana | 2 | 0 | 0.68 |
| Shashank Srivastava | 3 | 3 | 2.40 |
| Madhur Tulsiani | 4 | 358 | 24.60 |