
-
Wedge-Lifted Codes
We define wedge-lifted codes, a variant of lifted codes, and we study th...
read it
-
Improved List-Decodability of Reed–Solomon Codes via Tree Packings
This paper shows that there exist Reed–Solomon (RS) codes, over large fi...
read it
-
Improved SETH-hardness of unweighted Diameter
We prove that, assuming the Strong Exponential Time Hypothesis, for any ...
read it
-
Bounds for list-decoding and list-recovery of random linear codes
A family of error-correcting codes is list-decodable from error fraction...
read it
-
Coded trace reconstruction in a constant number of traces
The coded trace reconstruction problem asks to construct a code C⊂{0,1}^...
read it
-
Enumeration of Preferred Extensions in Almost Oriented Digraphs
In this paper, we present enumeration algorithms to list all preferred e...
read it
-
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...
read it
-
Max-Cut in Degenerate H-Free Graphs
We obtain several lower bounds on the Max-Cut of d-degenerate H-free gra...
read it
-
Lifted multiplicity codes and the disjoint repair group property
Lifted Reed Solomon Codes (Guo, Kopparty, Sudan 2013) were introduced in...
read it
-
Lifted Multiplicity Codes
Lifted Reed Solomon Codes (Guo, Kopparty, Sudan 2013) were introduced in...
read it
-
On Ramsey numbers of hedgehogs
The hedgehog H_t is a 3-uniform hypergraph on vertices 1,...,t+t2 such t...
read it
-
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...
read it