Cover Image

Bounds for list-decoding and list-recovery of random linear codes

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Guruswami, Venkatesan, Li, Ray, Mosheiff, Jonathan, Resch, Nicolas, Silas, Shashwat, Wootters, Mary
Format:	Preprint
Published:	2020
Subjects:	Information Theory Probability
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Threshold rates for properties of random codes
by: Guruswami, Venkatesan, et al.
Published: (2020)

LDPC Codes Achieve List Decoding Capacity
by: Mosheiff, Jonathan, et al.
Published: (2019)

AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets
by: Alrabiah, Omar, et al.
Published: (2023)

Punctured Low-Bias Codes Behave Like Random Linear Codes
by: Guruswami, Venkatesan, et al.
Published: (2021)

When Do Low-Rate Concatenated Codes Approach The Gilbert-Varshamov Bound?
by: Doron, Dean, et al.
Published: (2024)

On the weight distribution of random binary linear codes
by: Linial, Nati, et al.
Published: (2018)

$\ell_p$-Spread and Restricted Isometry Properties of Sparse Random Matrices
by: Guruswami, Venkatesan, et al.
Published: (2021)

On the exact decoding error probability exponent of the random coding on BSC
by: Burnashev, Marat V.
Published: (2026)

Tight bounds for stream decodable error-correcting codes
by: Gupta, Meghal, et al.
Published: (2024)

Communication with Imperfectly Shared Randomness
by: Canonne, Clément L., et al.
Published: (2014)

Interactive Coding with Small Memory and Improved Rate
by: Fathollahi, Dorsa, et al.
Published: (2024)

Randomness-Efficient Constructions of Capacity-Achieving List-Decodable Codes
by: Mosheiff, Jonathan, et al.
Published: (2024)

List-Recovery of Random Linear Codes over Small Fields
by: Doron, Dean, et al.
Published: (2025)

Efficient List-decoding of Polynomial Ideal Codes with Optimal List Size
by: Ron-Zewi, Noga, et al.
Published: (2024)

Deterministic list decoding of Reed-Solomon codes
by: Chatterjee, Soham, et al.
Published: (2025)

Improved Bounds on Access-Redundancy Tradeoffs in Quantized Linear Computations
by: Li, Ching-Fang, et al.
Published: (2025)

Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles
by: Alrabiah, Omar, et al.
Published: (2024)

Linear time encodable binary code achieving GV bound with linear time encodable dual achieving GV bound
by: Brehm, Martijn, et al.
Published: (2025)

The correlated matching decoder for the 4.8.8 color code
by: Liu, Yantong, et al.
Published: (2025)

Fast list-decoding of univariate multiplicity and folded Reed-Solomon codes
by: Goyal, Rohan, et al.
Published: (2023)

Maximal Recoverability: A Nexus of Coding Theory
by: Brakensiek, Joshua, et al.
Published: (2026)

A Deterministic Construction of a Large Distance Code from the Wozencraft Ensemble
by: Guruswami, Venkatesan, et al.
Published: (2023)

Structure Theorems (and Fast Algorithms) for List Recovery of Subspace-Design Codes
by: Goyal, Rohan, et al.
Published: (2025)

Decoding Quasi-Cyclic Quantum LDPC Codes
by: Golowich, Louis, et al.
Published: (2024)

Quantum LDPC Codes of Almost Linear Distance via Homological Products
by: Golowich, Louis, et al.
Published: (2024)

Asymptotically Good Quantum Codes with Transversal Non-Clifford Gates
by: Golowich, Louis, et al.
Published: (2024)

Near-Asymptotically-Good Quantum Codes with Transversal CCZ Gates and Sublinear-Weight Parity-Checks
by: Golowich, Louis, et al.
Published: (2025)

Successive Cancellation Sampling Decoder: An Attempt to Analyze List Decoding Theoretically
by: Wang, Hsin-Po, et al.
Published: (2024)

Geno-Weaving: Low-Complexity Capacity-Achieving DNA Storage
by: Wang, Hsin-Po, et al.
Published: (2024)

How Many Matrices Should I Prepare To Polarize Channels Optimally Fast?
by: Wang, Hsin-Po, et al.
Published: (2024)

Isolate and then Identify: Rethinking Adaptive Group Testing
by: Wang, Hsin-Po, et al.
Published: (2024)

Limitations to Computing Quadratic Functions on Reed-Solomon Encoded Data
by: Blackwell, Keller, et al.
Published: (2025)

Improved Trade-offs Between Amortization and Download Bandwidth for Linear HSS
by: Blackwell, Keller, et al.
Published: (2024)

Improved Construction of Robust Gray Code
by: Fathollahi, Dorsa, et al.
Published: (2024)

Exact objectives of random linear programs and mean widths of random polyhedrons
by: Stojnic, Mihailo
Published: (2024)

Fast list recovery of univariate multiplicity and folded Reed-Solomon codes
by: Goyal, Rohan, et al.
Published: (2025)

Foundations of information theory for coding theory
by: Mouloua, El Mahdi, et al.
Published: (2025)

Let's Have Both! Optimal List-Recoverability via Alphabet Permutation Codes
by: Komech, Sergey, et al.
Published: (2025)

A New Bound on the Cumulant Generating Function of Dirichlet Processes
by: Perrault, Pierre, et al.
Published: (2024)

Density Frankl-Rödl on the Sphere
by: Guruswami, Venkatesan, et al.
Published: (2025)