Optimal Rate List Decoding over Bounded Alphabets Using Algebraic-geometric Codes

DOI10.1145/3506668OpenAlexW3117811306MaRDI QIDQ5066947

Xing, Chaoping, Venkatesan Guruswami

Publication date: 31 March 2022

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1708.01070

zbMATH Keywords

Reed-Solomon codespseudorandomnessalgebraic geometric codeslist decoding capacitysubspace evasive sets

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Algebraic function fields and codes
• Cyclotomic function fields, Artin-Frobenius automorphisms, and list error correction with optimal rate
• On the asymptotic behaviour of some towers of function fields over finite fields
• Decoding of Reed Solomon codes beyond the error-correction bound
• A tower of Artin-Schreier extensions of function fields attaining the Drinfeld-Vladut bound
• Explicit subspace designs
• Pseudorandomness
• Some remarks on multiplicity codes
• Explicit List-Decodable Rank-Metric and Subspace Codes via Subspace Designs
• Combinatorial Limitations of Average-Radius List-Decoding
• Error-correcting codes for list decoding
• List decoding from erasures: bounds and code constructions
• Algebraic soft-decision decoding of reed-solomon codes
• Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy
• Divisibility of the Specialization Map for Families of Elliptic Curves
• A Justesen construction of binary concatenated codes that asymptotically meet the Zyablov bound for low rate
• Improved decoding of Reed-Solomon and algebraic-geometry codes
• A low-complexity algorithm for the construction of algebraic-geometric codes better than the Gilbert-Varshamov bound
• High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity
• Subspace designs based on algebraic function fields
• Better Binary List Decodable Codes Via Multilevel Concatenation
• Efficient List-Decoding With Constant Alphabet and List Sizes
• The asymptotic behavior of automorphism groups of function fields over finite fields
• Linear-Algebraic List Decoding for Variants of Reed–Solomon Codes
• Dimension Expanders via Rank Condensers
• Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets
• Folded codes from function field towers and improved optimal rate list decoding
• Subspace evasive sets
• List decoding reed-solomon, algebraic-geometric, and gabidulin subcodes up to the singleton bound

This page was built for publication: Optimal Rate List Decoding over Bounded Alphabets Using Algebraic-geometric Codes