research
∙
08/25/2023
AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets
A simple, recently observed generalization of the classical Singleton bo...
share
research
∙
04/19/2023
Randomly punctured Reed–Solomon codes achieve list-decoding capacity over linear-sized fields
Reed–Solomon codes are a classic family of error-correcting codes consis...
research
∙
12/12/2022
Binary Error-Correcting Codes with Minimal Noiseless Feedback
In the setting of error-correcting codes with feedback, Alice wishes to ...
research
∙
07/10/2022
Accelerating Polarization via Alphabet Extension
Polarization is an unprecedented coding technique in that it not only ac...
research
∙
12/18/2021
Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions
We consider the problem of designing low-redundancy codes in settings wh...
research
∙
09/24/2021
Punctured Large Distance Codes, and Many Reed-Solomon Codes, Achieve List-Decoding Capacity
We prove the existence of Reed-Solomon codes of any desired rate R ∈ (0,...
research
∙
09/09/2021
Algorithms and Certificates for Boolean CSP Refutation: "Smoothed is no harder than Random"
We present an algorithm for strongly refuting smoothed instances of all ...
research
∙
09/11/2020
Linear Shannon Capacity of Cayley Graphs
The Shannon capacity of a graph is a fundamental quantity in zero-error ...
research
∙
01/16/2019
An Exponential Lower Bound on the Sub-Packetization of MSR Codes
An (n,k,ℓ)-vector MDS code is a F-linear subspace of (F^ℓ)^n (for some f...
research
∙
08/09/2018
Secret Sharing with Binary Shares
Secret sharing is a fundamental cryptographic primitive. One of the main...
research
∙
05/10/2018
Beating Fredman-Komlós for perfect k-hashing
We say a subset C ⊆{1,2,...,k}^n is a k-hash code (also called k-separat...
research
∙
04/10/2018
Approximating Operator Norms via Generalized Krivine Rounding
We consider the (ℓ_p,ℓ_r)-Grothendieck problem, which seeks to maximize ...
research
∙
10/27/2017
On Maximally Recoverable Local Reconstruction Codes
In recent years the explosion in the volumes of data being stored online...
research
∙
08/03/2017
