research
∙
06/16/2022
Max-Margin Works while Large Margin Fails: Generalization without Uniform Convergence
A major challenge in modern machine learning is theoretically understand...
share
research
∙
01/30/2022
Efficient Near-Optimal Codes for General Repeat Channels
Given a probability distribution 𝒟 over the non-negative integers, a 𝒟-r...
research
∙
11/19/2021
On the Download Rate of Homomorphic Secret Sharing
A homomorphic secret sharing (HSS) scheme is a secret sharing scheme tha...
research
∙
08/17/2021
A Note on the Permuted Puzzles Toy Conjecture
In this note, we show that a "Toy Conjecture" made by (Boyle, Ishai, Pas...
research
∙
07/25/2021
Low-bandwidth recovery of linear functions of Reed-Solomon-encoded data
We study the problem of efficiently computing on encoded data. More spec...
research
∙
06/03/2021
Improved batch code lower bounds
Batch codes are a useful notion of locality for error correcting codes, ...
research
∙
02/03/2021
On Coding for an Abstracted Nanopore Channel for DNA Storage
In the emerging field of DNA storage, data is encoded as DNA sequences a...
research
∙
02/02/2021
On Greedy Approaches to Hierarchical Aggregation
We analyze greedy algorithms for the Hierarchical Aggregation (HAG) prob...
research
∙
11/24/2020
Wedge-Lifted Codes
We define wedge-lifted codes, a variant of lifted codes, and we study th...
research
∙
11/09/2020
Improved List-Decodability of Reed–Solomon Codes via Tree Packings
This paper shows that there exist Reed–Solomon (RS) codes, over large fi...
research
∙
09/22/2020
Asynchronous Distributed Optimization with Randomized Delays
In this work, we study asynchronous finite sum minimization in a distrib...
research
∙
09/09/2020
Sharp threshold rates for random codes
Suppose that 𝒫 is a property that may be satisfied by a random code C ⊂Σ...
research
∙
06/17/2020
Approximate Gradient Coding with Optimal Decoding
In distributed optimization problems, a technique called gradient coding...
research
∙
06/09/2020
Hermitian-Lifted Codes
In this paper, we construct codes for local recovery of erasures with hi...
research
∙
04/28/2020
Bounds for list-decoding and list-recovery of random linear codes
A family of error-correcting codes is list-decodable from error fraction...
research
∙
02/20/2020
Linear-time Erasure List-decoding of Expander Codes
We give a linear-time erasure list-decoding algorithm for expander codes...
research
∙
10/30/2019
Weighted matrix completion from non-random, non-uniform sampling patterns
We study the matrix completion problem when the observation pattern is d...
research
∙
09/13/2019
LDPC Codes Achieve List Decoding Capacity
We show that Gallager's ensemble of Low-Density Parity Check (LDPC) code...
research
∙
07/19/2019
Sparse Recovery for Orthogonal Polynomial Transforms
In this paper we consider the following sparse recovery problem. We have...
research
∙
05/14/2019
Stochastic Gradient Coding for Straggler Mitigation in Distributed Learning
We consider distributed gradient descent in the presence of stragglers. ...
research
∙
05/06/2019
Lifted multiplicity codes and the disjoint repair group property
Lifted Reed Solomon Codes (Guo, Kopparty, Sudan 2013) were introduced in...
research
∙
05/06/2019
Lifted Multiplicity Codes
Lifted Reed Solomon Codes (Guo, Kopparty, Sudan 2013) were introduced in...
research
∙
04/03/2019
Embedded Index Coding
Motivated by applications in distributed storage and distributed computa...
research
∙
09/25/2018
Noise Thresholds for Amplification: Quantum Foundations From Classical Fault-Tolerant Computation
It has long been known that certain superquantum nonlocal correlations c...
research
∙
09/25/2018
Noise Thresholds for Amplification: From Quantum Foundations to Classical Fault-Tolerant Computation
We revisit an old question--fault-tolerant computation by noisy circuits...
research
∙
09/10/2018
Unconstraining graph-constrained group testing
In network tomography, one goal is to identify a small set of failed lin...
research
∙
08/04/2018
On the Optimality of the Kautz-Singleton Construction in Probabilistic Group Testing
We consider the probabilistic group testing problem where d random defec...
research
∙
05/03/2018
Improved decoding of Folded Reed-Solomon and Multiplicity Codes
In this work, we show new and improved error-correcting properties of fo...
research
∙
02/03/2018
Blind Joint MIMO Channel Estimation and Decoding
We propose a method for MIMO decoding when channel state information (CS...
research
∙
02/02/2018
On taking advantage of multiple requests in error correcting codes
In most notions of locality in error correcting codes -- notably locally...
research
∙
02/02/2018
Load-Balanced Fractional Repetition Codes
We introduce load-balanced fractional repetition (LBFR) codes, which are...
research
∙
01/24/2018
Random linear binary codes have smaller list sizes than uniformly random binary codes
There has been a great deal of work establishing that random linear code...
research
∙
07/15/2014