Cover Image

Quasi-linear time decoding of RS and AG codes for burst errors up to the Singleton bound

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Li, Songsong, Liu, Shu, Ma, Liming, Wan, Yunqi, Xing, Chaoping
Format:	Preprint
Published:	2025
Subjects:	Information Theory Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Encoding of algebraic geometry codes with quasi-linear complexity $O(N\log N)$
by: Li, Songsong, et al.
Published: (2024)

Asymptotic construction of locally repairable codes with multiple recovering sets
by: Li, Singsong, et al.
Published: (2024)

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

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

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

Explicit Codes approaching Generalized Singleton Bound using Expanders
by: Jeronimo, Fernando Granha, et al.
Published: (2025)

New families of non-Reed-Solomon MDS codes
by: Jin, Lingfei, et al.
Published: (2024)

Algebraic Geometry Codes for Distributed Matrix Multiplication Using Local Expansions
by: Li, Jiang, et al.
Published: (2024)

Decoding Balanced Linear Codes With Preprocessing
by: Bogdanov, Andrej, et al.
Published: (2025)

A lower bound on the field size of convolutional codes with a maximum distance profile and an improved construction
by: Chen, Zitan
Published: (2023)

Generic Reed-Solomon Codes Achieve List-decoding Capacity
by: Brakensiek, Joshua, et al.
Published: (2022)

Coded Distributed (Batch) Matrix Multiplication over Galois Ring via RMFE
by: Kuang, Yi, et al.
Published: (2024)

Space-bounded online Kolmogorov complexity is additive
by: Bauwens, Bruno, et al.
Published: (2025)

A new family of binary sequences with a low correlation via elliptic curves
by: Jin, Lingfei, et al.
Published: (2024)

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

PAC codes with Bounded-Complexity Sequential Decoding: Pareto Distribution and Code Design
by: Moradi, Mohsen, et al.
Published: (2024)

On SAT information content, its polynomial-time solvability and fixed code algorithms
by: Drozdowski, Maciej
Published: (2024)

Computational hardness of estimating quantum entropies via binary entropy bounds
by: Liu, Yupan
Published: (2026)

On the error correction of iterative bounded distance decoding of generalized LDPC codes
by: Burshtein, David
Published: (2025)

A proof of P != NP (New symmetric encryption algorithm against any linear attacks and differential attacks)
by: Ming, Gao
Published: (2022)

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

An exposition of recent list-size bounds of FRS Codes
by: Garg, Abhibhav, et al.
Published: (2025)

A slightly improved upper bound for quantum statistical zero-knowledge
by: Gall, François Le, et al.
Published: (2025)

Explicit optimal-length locally repairable codes of distance 5
by: Beemer, Allison, et al.
Published: (2018)

Transversal non-Clifford gates for quantum LDPC codes on sheaves
by: Lin, Ting-Chun
Published: (2024)

Expansion of higher-dimensional cubical complexes with application to quantum locally testable codes
by: Dinur, Irit, et al.
Published: (2024)

Oblivious Deletion Codes
by: Con, Roni, et al.
Published: (2025)

On the Minimum Depth of Circuits with Linear Number of Wires Encoding Good Codes
by: Drucker, Andrew, et al.
Published: (2024)

Optimal Proximity Gap for Folded Reed--Solomon Codes via Subspace Designs
by: Jeronimo, Fernando Granha, et al.
Published: (2026)

Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions
by: Blocki, Jeremiah, et al.
Published: (2021)

Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes
by: Block, Alexander R., et al.
Published: (2026)

List Decoding Expander-Based Codes up to Capacity in Near-Linear Time
by: Srivastava, Shashank, et al.
Published: (2025)

Quasi-twisted codes: decoding and applications in code-based cryptography
by: S, Bhagyalekshmy, et al.
Published: (2025)

A Pair of Bayesian Network Structures has Undecidable Conditional Independencies
by: Li, Cheuk Ting
Published: (2024)

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

Relaxed Local Correctability from Local Testing
by: Kumar, Vinayak M., et al.
Published: (2023)

Broadcast Channel Coding: Algorithmic Aspects and Non-Signaling Assistance
by: Fawzi, Omar, et al.
Published: (2023)

Improved PIR Schemes using Matching Vectors and Derivatives
by: Ghasemi, Fatemeh, et al.
Published: (2024)

Explicit Constant-Alphabet Subspace Design Codes
by: Goyal, Rohan, et al.
Published: (2026)

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