5 papers
From Random to Explicit via Subspace Designs With Applications to Local Properties and Matroids
Joshua Brakensiek, Yeyuan Chen, Manik Dhar +1
In coding theory, a common question is to understand the threshold rates of various local properties of codes, such as their list decodability and list recoverability. A recent wor…
Combinatorial Bounds for List Recovery via Discrete Brascamp--Lieb Inequalities
Joshua Brakensiek, Yeyuan Chen, Manik Dhar +1
In coding theory, the problem of list recovery asks one to find all codewords of a given code which such that at least fraction of the symbols of lie in some pred…
Unique Decoding of Reed-Solomon and Related Codes for Semi-Adversarial Errors
Joshua Brakensiek, Yeyuan Chen, Manik Dhar +1
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 betwe…
Explicit Folded Reed-Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton Bounds
Yeyuan Chen, Zihan Zhang
In this paper, we prove that explicit FRS codes and multiplicity codes achieve relaxed generalized Singleton bounds for list size Specifically, we show the following: (1)…
Random Reed-Solomon Codes Achieve the Half-Singleton Bound for Insertions and Deletions over Linear-Sized Alphabets
Roni Con, Zeyu Guo, Ray Li +1
In this paper, we prove that with high probability, random Reed-Solomon codes approach the half-Singleton bound - the optimal rate versus error tradeoff for linear insdel codes - w…