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
∙
07/14/2023
On Diameter Approximation in Directed Graphs
Computing the diameter of a graph, i.e. the largest distance, is a funda...
research
∙
07/06/2023
Improved rate-distance trade-offs for quantum codes with restricted connectivity
For quantum error-correcting codes to be realizable, it is important tha...
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
∙
11/30/2022
Approximating binary longest common subsequence in almost-linear time
The Longest Common Subsequence (LCS) is a fundamental string similarity ...
research
∙
06/27/2022
CopyCat2: A Single Model for Multi-Speaker TTS and Many-to-Many Fine-Grained Prosody Transfer
In this paper, we present CopyCat2 (CC2), a novel model capable of: a) s...
research
∙
01/30/2022
Efficient Near-Optimal Codes for General Repeat Channels
Given a probability distribution 𝒟 over the non-negative integers, a 𝒟-r...
research
∙
06/10/2021
Hardness of Approximate Diameter: Now for Undirected Graphs
Approximating the graph diameter is a basic task of both theoretical and...
research
∙
06/09/2021
The zero-rate threshold for adversarial bit-deletions is less than 1/2
We prove that there exists an absolute constant δ>0 such any binary code...
research
∙
06/03/2021
Improved batch code lower bounds
Batch codes are a useful notion of locality for error correcting codes, ...
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
∙
08/12/2020
Improved SETH-hardness of unweighted Diameter
We prove that, assuming the Strong Exponential Time Hypothesis, for any ...
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
∙
08/12/2019
Coded trace reconstruction in a constant number of traces
The coded trace reconstruction problem asks to construct a code C⊂{0,1}^...
research
∙
07/01/2019
Enumeration of Preferred Extensions in Almost Oriented Digraphs
In this paper, we present enumeration algorithms to list all preferred e...
research
∙
06/26/2019
A Tight Analysis of Greedy Yields Subexponential Time Approximation for Uniform Decision Tree
Decision Tree is a classic formulation of active learning: given n hypot...
research
∙
05/08/2019
Max-Cut in Degenerate H-Free Graphs
We obtain several lower bounds on the Max-Cut of d-degenerate H-free gra...
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
∙
02/26/2019
On Ramsey numbers of hedgehogs
The hedgehog H_t is a 3-uniform hypergraph on vertices 1,...,t+t2 such t...
research
∙
01/24/2018