48 citations · 103 across the 33 of their papers we have counts for
14 papers · 1 filter
Algorithmic List Decoding of Reed-Solomon Codes up to Capacity
Joshua Brakensiek, Yeyuan Chen, Aaron Putterman +2
We give a deterministic polynomial-time list-decoding algorithm for Reed-Solomon codes over prime fields that approaches list-decoding capacity for every evaluation set and every c…
Bounds and Limitations on Codes Achieving List Recovery Capacity
Joshua Brakensiek, Yeyuan Chen, Aaron Putterman +1
In coding theory, list recoverability is a fundamental concept which robustly captures how ``spread-out'' codewords are in a code. More formally, given a code and…
Maximal Recoverability: A Nexus of Coding Theory
Joshua Brakensiek, Venkatesan Guruswami
In the modern era of large-scale computing systems, a crucial use of error correcting codes is to judiciously introduce redundancy to ensure recoverability from failure. To get the…
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…
Improved Constructions and Lower Bounds for Maximally Recoverable Grid Codes
Joshua Brakensiek, Manik Dhar, Sivakanth Gopi
In this paper, we continue the study of Maximally Recoverable (MR) Grid Codes initiated by Gopalan et al. [SODA 2017]. More precisely, we study codes over an grid topo…
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…
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…
Generalized GM-MDS: Polynomial Codes are Higher Order MDS
Joshua Brakensiek, Manik Dhar, Sivakanth Gopi
The GM-MDS theorem, conjectured by Dau-Song-Dong-Yuen and proved by Lovett and Yildiz-Hassibi, shows that the generator matrices of Reed-Solomon codes can attain every possible con…
Improved Field Size Bounds for Higher Order MDS Codes
Joshua Brakensiek, Manik Dhar, Sivakanth Gopi
Higher order MDS codes are an interesting generalization of MDS codes recently introduced by Brakensiek, Gopi and Makam (IEEE Trans. Inf. Theory 2022). In later works, they were sh…
Generic Reed-Solomon Codes Achieve List-decoding Capacity
Joshua Brakensiek, Sivakanth Gopi, Visu Makam
In a recent paper, Brakensiek, Gopi and Makam introduced higher order MDS codes as a generalization of MDS codes. An order- MDS code, denoted by , h…
Lower Bounds for Maximally Recoverable Tensor Code and Higher Order MDS Codes
Joshua Brakensiek, Sivakanth Gopi, Visu Makam
An -tensor code consists of matrices whose columns satisfy `' parity checks and rows satisfy `' parity checks (i.e., a tensor code is the tensor produc…
Coded trace reconstruction in a constant number of traces
Joshua Brakensiek, Ray Li, Bruce Spang
The coded trace reconstruction problem asks to construct a code such that any is recoverable from independent outputs ("traces") of from a binary…
Efficient Low-Redundancy Codes for Correcting Multiple Deletions
Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky
We consider the problem of constructing binary codes to recover from -bit deletions with efficient encoding/decoding, for a fixed . The single deletion case is well understoo…