-
Wedge-Lifted Codes
We define wedge-lifted codes, a variant of lifted codes, and we study th...
11/24/2020 ∙ by Jabari Hastings, et al. ∙
0
∙
share
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...
11/09/2020 ∙ by Zeyu Guo, et al. ∙
0
∙
share
read it
-
Improved SETH-hardness of unweighted Diameter
We prove that, assuming the Strong Exponential Time Hypothesis, for any ...
08/12/2020 ∙ by Ray Li, et al. ∙
0
∙
share
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...
04/28/2020 ∙ by Venkatesan Guruswami, et al. ∙
0
∙
share
read it
-
Coded trace reconstruction in a constant number of traces
The coded trace reconstruction problem asks to construct a code C⊂{0,1}^...
08/12/2019 ∙ by Joshua Brakensiek, et al. ∙
0
∙
share
read it
-
Enumeration of Preferred Extensions in Almost Oriented Digraphs
In this paper, we present enumeration algorithms to list all preferred e...
07/01/2019 ∙ by Serge Gaspers, et al. ∙
0
∙
share
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...
06/26/2019 ∙ by Ray Li, et al. ∙
0
∙
share
read it
-
Max-Cut in Degenerate H-Free Graphs
We obtain several lower bounds on the Max-Cut of d-degenerate H-free gra...
05/08/2019 ∙ by Ray Li, et al. ∙
0
∙
share
read it
-
Lifted multiplicity codes and the disjoint repair group property
Lifted Reed Solomon Codes (Guo, Kopparty, Sudan 2013) were introduced in...
05/06/2019 ∙ by Ray Li, et al. ∙
0
∙
share
read it
-
Lifted Multiplicity Codes
Lifted Reed Solomon Codes (Guo, Kopparty, Sudan 2013) were introduced in...
05/06/2019 ∙ by Ray Li, et al. ∙
0
∙
share
read it
-
On Ramsey numbers of hedgehogs
The hedgehog H_t is a 3-uniform hypergraph on vertices 1,...,t+t2 such t...
02/26/2019 ∙ by Jacob Fox, et al. ∙
0
∙
share
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...
01/24/2018 ∙ by Ray Li, et al. ∙
0
∙
share
read it
