2 citations · 3 across the 5 of their papers we have counts for
9 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…
Random Gabidulin Codes Achieve List Decoding Capacity in the Rank Metric
Zeyu Guo, Chaoping Xing, Chen Yuan +1
Gabidulin codes, serving as the rank-metric counterpart of Reed-Solomon codes, constitute an important class of maximum rank distance (MRD) codes. However, unlike the fruitful posi…
AG Codes Achieve List-decoding Capacity over Constant-sized Fields
Joshua Brakensiek, Manik Dhar, Sivakanth Gopi +1
The recently-emerging field of higher order MDS codes has sought to unify a number of concepts in coding theory. Such areas captured by higher order MDS codes include maximally rec…
Random Reed-Solomon Codes Achieve List-Decoding Capacity With Linear-Sized Alphabets
Omar Alrabiah, Zeyu Guo, Venkatesan Guruswami +2
Reed-Solomon codes are a classic family of error-correcting codes consisting of evaluations of low-degree polynomials over a finite field on some sequence of distinct field element…
Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets
Zeyu Guo, Zihan Zhang
This paper shows that, with high probability, randomly punctured Reed-Solomon codes over fields of polynomial size achieve the list decoding capacity. More specifically, we prove t…