2026-07-19T18:56:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26432 2026-07-01T07:16:10Z ddc:004 open_access

Unique Decoding of Reed–Solomon and Related Codes for Semi-Adversarial Errors Brakensiek, Joshua Chen, Yeyuan Dhar, Manik Zhang, Zihan coding theory interleaved codes Reed-Solomon codes semi-random models unique decoding 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. As our main quest, 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 novel monomial-tracking technique to analyze its performance in this new semi-adversarial errors. Inspired by the BKY algorithm, we use novel 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joshua Brakensiek and Yeyuan Chen and Manik Dhar and Zihan Zhang 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.43 urn:nbn:de:0030-drops-264326 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.43 eng https://creativecommons.org/licenses/by/4.0/legalcode