Buchumschlag

Random Reed-Solomon Codes Achieve List-Decoding Capacity With Linear-Sized Alphabets

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Alrabiah, Omar, Guo, Zeyu, Guruswami, Venkatesan, Li, Ray, Zhang, Zihan
Format:	Preprint
Veröffentlicht:	2023
Schlagworte:	Information Theory Data Structures and Algorithms Combinatorics
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets
von: Guo, Zeyu, et al.
Veröffentlicht: (2023)

Random Reed-Solomon Codes Achieve the Half-Singleton Bound for Insertions and Deletions over Linear-Sized Alphabets
von: Con, Roni, et al.
Veröffentlicht: (2024)

Capacity-Achieving Gray Codes
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2024)

Algorithmic Improvements to List Decoding of Folded Reed-Solomon Codes
von: Ashvinkumar, Vikrant, et al.
Veröffentlicht: (2025)

List Decoding Reed--Solomon Codes in the Lee, Euclidean, and Other Metrics
von: Peikert, Chris, et al.
Veröffentlicht: (2025)

Unique Decoding of Reed-Solomon and Related Codes for Semi-Adversarial Errors
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2025)

Nonadaptive Noise-Resilient Group Testing with Order-Optimal Tests and Fast-and-Reliable Decoding
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2023)

Redundancy Is All You Need (for CSP Sparsification)
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2024)

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

Tight bounds for stream decodable error-correcting codes
von: Gupta, Meghal, et al.
Veröffentlicht: (2024)

Tight Bounds for Sparsifying Random CSPs
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2025)

List Decoding Expander-Based Codes up to Capacity in Near-Linear Time
von: Srivastava, Shashank, et al.
Veröffentlicht: (2025)

Old and New Results on Alphabetic Codes
von: Bruno, Roberto, et al.
Veröffentlicht: (2025)

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

Unbounded Error Correcting Codes
von: Efremenko, Klim, et al.
Veröffentlicht: (2024)

Improved Decoding of Tanner Codes
von: Zhou, Zhaienhe, et al.
Veröffentlicht: (2025)

Improved Explicit Near-Optimal Codes in the High-Noise Regimes
von: Li, Xin, et al.
Veröffentlicht: (2024)

Source Coding with Free Bits and the Multi-Way Number Partitioning Problem
von: Ahmadypour, Niloufar, et al.
Veröffentlicht: (2020)

Bounds and Algorithms for Alphabetic Codes and Binary Search Trees
von: Bruno, Roberto, et al.
Veröffentlicht: (2024)

Random Gabidulin Codes Achieve List Decoding Capacity in the Rank Metric
von: Guo, Zeyu, et al.
Veröffentlicht: (2024)

List Decoding Expander-Based Codes via Fast Approximation of Expanding CSPs: I
von: Jeronimo, Fernando Granha, et al.
Veröffentlicht: (2025)

Perturbation-Resilient Trades for Dynamic Service Balancing
von: Sima, Jin, et al.
Veröffentlicht: (2024)

Trellis codes with a good distance profile constructed from expander graphs
von: Zhu, Yubin, et al.
Veröffentlicht: (2026)

Generic Reed-Solomon Codes Achieve List-decoding Capacity
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2022)

Explicit Good Codes Approaching Distance 1 in Ulam Metric
von: Goldenberg, Elazar, et al.
Veröffentlicht: (2024)

Kernels for Storage Capacity and Dual Index Coding
von: Haviv, Ishay
Veröffentlicht: (2025)

Universal Maximum Likelihood (List) Decoding via Fast Vector-Matrix Multiplication
von: Ly, Hoang, et al.
Veröffentlicht: (2025)

Random Reed-Solomon Codes are List Recoverable with Optimal List Size
von: Doron, Dean, et al.
Veröffentlicht: (2024)

A Method for Generating Connected Erdos-Renyi Random Graphs
von: Chinyaev, Boris
Veröffentlicht: (2025)

Punctured Low-Bias Codes Behave Like Random Linear Codes
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2021)

The Lovász Theta Function for Recovering Planted Clique Covers and Graph Colorings
von: Hou, Jiaxin, et al.
Veröffentlicht: (2023)

On constrained intersection representations of graphs and digraphs
von: Cicalese, Ferdinando, et al.
Veröffentlicht: (2025)

Construction of orientable sequences in $O(1)$-amortized time per bit
von: Gabric, Daniel, et al.
Veröffentlicht: (2024)

Sampling List Packings
von: Camrud, Evan, et al.
Veröffentlicht: (2024)

Unclustered BWTs of any Length over Non-Binary Alphabets
von: Fici, Gabriele, et al.
Veröffentlicht: (2025)

Semirandom Planted Clique via 1-norm Isometry Property
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2025)

Continuous Optimization for Decoding Errors
von: Srivastava, Shashank
Veröffentlicht: (2024)

Exponential Time Approximation for Coloring 3-Colorable Graphs
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2024)

Explicit Folded Reed-Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton Bounds
von: Chen, Yeyuan, et al.
Veröffentlicht: (2024)

The Metric Dimension of Sparse Random Graphs
von: Díaz, Josep, et al.
Veröffentlicht: (2025)