Randomly punctured Reed–Solomon codes achieve list-decoding capacity over linear-sized fields
Reed–Solomon codes are a classic family of error-correcting codes consisting of
evaluations of low-degree polynomials over a finite field on some sequence of distinct field …
evaluations of low-degree polynomials over a finite field on some sequence of distinct field …
Generic reed-solomon codes achieve list-decoding capacity
In a recent paper, Brakensiek, Gopi and Makam introduced higher order MDS codes as a
generalization of MDS codes. An order-ℓ MDS code, denoted by MDS (ℓ), has the property …
generalization of MDS codes. An order-ℓ MDS code, denoted by MDS (ℓ), has the property …
Randomly punctured reed-solomon codes achieve the list decoding capacity over polynomial-size alphabets
This paper shows that, with high probability, randomly punctured Reed-Solomon codes over
fields of polynomial size achieve the list decoding capacity. More specifically, we prove that …
fields of polynomial size achieve the list decoding capacity. More specifically, we prove that …
List decoding of tanner and expander amplified codes from distance certificates
FG Jeronimo, S Srivastava… - 2023 IEEE 64th Annual …, 2023 - ieeexplore.ieee.org
We develop new list decoding algorithms for Tanner codes and distance-amplified codes
based on bipartite spectral expanders. We show that proofs exhibiting lower bounds on the …
based on bipartite spectral expanders. We show that proofs exhibiting lower bounds on the …
Punctured low-bias codes behave like random linear codes
V Guruswami, J Mosheiff - 2022 IEEE 63rd Annual Symposium …, 2022 - ieeexplore.ieee.org
Random linear codes are a workhorse in coding theory, and are used to show the existence
of codes with the best known or even near-optimal trade-offs in many noise models …
of codes with the best known or even near-optimal trade-offs in many noise models …
Optimization by decoded quantum interferometry
We introduce Decoded Quantum Interferometry (DQI), a quantum algorithm for reducing
classical optimization problems to classical decoding problems by exploiting structure in the …
classical optimization problems to classical decoding problems by exploiting structure in the …
Unique Decoding of Explicit -balanced Codes Near the Gilbert-Varshamov Bound
FG Jeronimo, D Quintana, S Srivastava… - 2020 IEEE 61st …, 2020 - ieeexplore.ieee.org
The Gilbert-Varshamov bound (non-constructively) establishes the existence of binary codes
of distance 1/2-ε and rate Ω(ε^2) (where an upper bound of O(ε^2\log(1/ε)) is known). Ta …
of distance 1/2-ε and rate Ω(ε^2) (where an upper bound of O(ε^2\log(1/ε)) is known). Ta …
Efficient list-decoding with constant alphabet and list sizes
Z Guo, N Ron-Zewi - Proceedings of the 53rd Annual ACM SIGACT …, 2021 - dl.acm.org
We present an explicit and efficient algebraic construction of capacity-achieving list
decodable codes with both constant alphabet and constant list sizes. More specifically, for …
decodable codes with both constant alphabet and constant list sizes. More specifically, for …
R\'enyi divergence guarantees for hashing with linear codes
M Pathegama, A Barg - arXiv preprint arXiv:2405.04406, 2024 - arxiv.org
We consider the problem of distilling uniform random bits from an unknown source with a
given $ p $-entropy using linear hashing. As our main result, we estimate the expected $ p …
given $ p $-entropy using linear hashing. As our main result, we estimate the expected $ p …
Pseudorandom linear codes are list decodable to capacity
AL Putterman, E Pyne - arXiv preprint arXiv:2303.17554, 2023 - arxiv.org
We introduce a novel family of expander-based error correcting codes. These codes can be
sampled with randomness linear in the block-length, and achieve list-decoding capacity …
sampled with randomness linear in the block-length, and achieve list-decoding capacity …