Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR22-027 | 27th March 2022 10:37

New Near-Linear Time Decodable Codes Closer to the GV Bound

RSS-Feed




Revision #1
Authors: Guy Blanc, Dean Doron
Accepted on: 27th March 2022 10:37
Downloads: 447
Keywords: 


Abstract:

We construct a family of binary codes of relative distance $\frac{1}{2}-\varepsilon$ and rate $\varepsilon^{2} \cdot 2^{-\log^{\alpha}(1/\varepsilon)}$ for $\alpha \approx \frac{1}{2}$ that are decodable, probabilistically, in near linear time. This improves upon the rate of the state-of-the-art near-linear time decoding near the GV bound due to Jeronimo, Srivastava, and Tulsiani, who gave a randomized decoding of Ta-Shma codes with $\alpha \approx \frac{5}{6}$ [T17,JST21].
Each code in our family can be constructed in probabilistic polynomial time, or deterministic polynomial time given sufficiently good explicit $3$-uniform hypergraphs.

Our construction is based on a new graph-based bias amplification method. While previous works start with some base code of relative distance $\frac{1}{2} \varepsilon_0$ for $\varepsilon_0 \gg \varepsilon$ and amplify the distance to $\frac{1}{2}-\varepsilon$ by walking on an expander, or on a carefully tailored product of expanders, we walk over very sparse, highly mixing, hypergraphs.
Study of such hypergraphs further offers an avenue toward achieving rate $\widetilde{\Omega}(\varepsilon^2)$.
For our unique- and list-decoding algorithms, we employ the framework developed in [JST21].



Changes to previous version:

Fixed typos.


Paper:

TR22-027 | 22nd February 2022 01:53

New Near-Linear Time Decodable Codes Closer to the GV Bound





TR22-027
Authors: Guy Blanc, Dean Doron
Publication: 23rd February 2022 07:23
Downloads: 708
Keywords: 


Abstract:

We construct a family of binary codes of relative distance $\frac{1}{2}-\varepsilon$ and rate $\varepsilon^{2} \cdot 2^{-\log^{\alpha}(1/\varepsilon)}$ for $\alpha \approx \frac{1}{2}$ that are decodable, probabilistically, in near linear time. This improves upon the rate of the state-of-the-art near-linear time decoding near the GV bound due to Jeronimo, Srivastava, and Tulsiani, who gave a randomized decoding of Ta-Shma codes with $\alpha \approx \frac{5}{6}$ [T17,JST21].
Each code in our family can be constructed in probabilistic polynomial time, or deterministic polynomial time given sufficiently good explicit $3$-uniform hypergraphs.

Our construction is based on a new graph-based bias amplification method. While previous works start with some base code of relative distance $\frac{1}{2} \varepsilon_0$ for $\varepsilon_0 \gg \varepsilon$ and amplify the distance to $\frac{1}{2}-\varepsilon$ by walking on an expander, or on a carefully tailored product of expanders, we walk over very sparse, highly mixing, hypergraphs.
Study of such hypergraphs further offers an avenue toward achieving rate $\widetilde{\Omega}(\varepsilon^2)$.
For our unique- and list-decoding algorithms, we employ the framework developed in [JST21].



ISSN 1433-8092 | Imprint