Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > MARY WOOTTERS:
All reports by Author Mary Wootters:

TR24-091 | 14th May 2024
Dean Doron, Jonathan Mosheiff, Mary Wootters

When Do Low-Rate Concatenated Codes Approach The Gilbert--Varshamov Bound?

Revisions: 1

The Gilbert--Varshamov (GV) bound is a classical existential result in coding theory. It implies that a random linear binary code of rate $\varepsilon^2$ has relative distance at least $\frac{1}{2} - O(\varepsilon)$ with high probability. However, it is a major challenge to construct explicit codes with similar parameters.

One hope to ... more >>>


TR20-168 | 11th November 2020
Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo, Mary Wootters

Improved List-Decodability of Reed–Solomon Codes via Tree Packings

This paper shows that there exist Reed--Solomon (RS) codes, over large finite fields, that are combinatorially list-decodable well beyond the Johnson radius, in fact almost achieving list-decoding capacity. In particular, we show that for any $\epsilon\in (0,1]$ there exist RS codes with rate $\Omega(\frac{\epsilon}{\log(1/\epsilon)+1})$ that are list-decodable from radius of ... more >>>




ISSN 1433-8092 | Imprint