AI & ML
Unique Decoding of Reed-Solomon and Related Codes for Semi-Adversarial Errors
arXiv math.IT0 views
arXiv:2504.10399v4 Announce Type: replace Abstract: Motivated by recent developments in coding theory, particular in list-decoding, we introduce a new error model which we call semi-adversarial errors. This error model bridges between fully random errors and fully adversarial errors by allowing some symbols of a message to be corrupted by an adversary while others are replaced with uniformly random symbols. We seek to understand optimal efficient unique decoding algorithms in the semi-adversarial model. For interleaved Reed--Solomon (IRS), folded Reed--Solomon (FRS) and univariate multiplicity codes, we design decoding algorithms running in near-linear time for most mixtures of random and adversarial errors. Our analysis matches the information-theoretic optimum for semi-adversarial errors. Our algorithm for interleaved Reed--Solomon codes is an improved implementation of the decoding algorithm by Bleichenbacher--Kiayias--Yung (BKY) for fully random errors. We use a monomial-tracking technique to analyze its performance in this new semi-adversarial errors. Inspired by the BKY algorithm, we use interpolations to extend our approach to the settings of folded Reed--Solomon and multiplicity codes, resulting in fast algorithms for unique decoding against semi-adversarial errors. Our new decoders for FRS and multiplicity codes replace the sophisticated root-finding step in traditional algorithms, such as the Guruswami--Wang algorithm, with a straightforward polynomial long division. Analysis of these algorithms requires more robust monomial-tracking arguments than IRS codes.
Source:https://arxiv.org/abs/2504.10399PreviousLearning Integer Winding Evolution Times in Quantum Phase EstimationNextExponential Lower Bounds for 2-query Relaxed Locally Decodable Codes
Related posts
Best time trackers for developers, for code and for AI
0dev.to

Serving Qwen3.5-0.8B with a 0.016% weight edit: measure the loops, pin the sampling on the server
0dev.to
Design Tokens for AI: Extract a Website's Real Colours, Fonts, Shadows and Icons So an LLM Builds On Brand
0dev.to
Trying to get our Arms around AI efficiency
0Stack Overflow Blog
Why an Embedded Game Fails on Some Phones, and How to Debug It
0dev.to
Microsoft 365 vs Office 2024: The Break-Even Math
0dev.to