27 citations · 46 across the 9 of their papers we have counts for
12 papers
Discrepancy for Random Linear Codes
Dean Doron, Tal Leonov, Jonathan Mosheiff +3
We show that random linear codes (RLCs) possess nearly optimal discrepancy-type properties in a broad range of settings. Our main results are two general discrepancy theorems: one…
List-Recovery of Random Linear Codes over Small Fields
Dean Doron, Jonathan Mosheiff, Nicolas Resch +1
We study list-recoverability of random linear codes over small fields, both from errors and from erasures. We consider codes of rate -close to capacity, and aim to bound the dep…
Let's Have Both! Optimal List-Recoverability via Alphabet Permutation Codes
Sergey Komech, Jonathan Mosheiff
We introduce alphabet-permutation (AP) codes, a new family of error-correcting codes defined by iteratively applying random coordinate-wise permutations to a fixed initial word. A…
Random Reed-Solomon Codes and Random Linear Codes are Locally Equivalent
Matan Levi, Jonathan Mosheiff, Nikhil Shagrithaya
We establish an equivalence between two important random ensembles of linear codes: random linear codes (RLCs) and random Reed-Solomon (RS) codes. Specifically, we show that these…
Low-Degree Polynomials Are Good Extractors
Omar Alrabiah, Jesse Goodman, Jonathan Mosheiff +1
We prove that random low-degree polynomials (over ) are unbiased, in an extremely general sense. That is, we show that random low-degree polynomials are good randomne…
When Do Low-Rate Concatenated Codes Approach The Gilbert-Varshamov Bound?
Dean Doron, Jonathan Mosheiff, Mary Wootters
The Gilbert--Varshamov (GV) bound is a classical existential result in coding theory. It implies that a random linear binary code of rate has relative distance at least $\fra…
Randomness-Efficient Constructions of Capacity-Achieving List-Decodable Codes
Jonathan Mosheiff, Nicolas Resch, Kuo Shang +1
We wish to generate list-decodable codes over small alphabets using as little randomness as possible. Specifically, we hope to generate codes achieving what we term the Elias bound…
Sparsity and -Restricted Isometry
Venkatesan Guruswami, Peter Manohar, Jonathan Mosheiff
A matrix is said to have the -Restricted Isometry Property (-RIP) if for all vectors of up to some sparsity , is roughly proportional to $\|…
Punctured Low-Bias Codes Behave Like Random Linear Codes
Venkatesan Guruswami, Jonathan Mosheiff
Random linear codes are a workhorse in coding theory, and are used to show the existence of codes with the best known or even near-optimal trade-offs in many noise models. However,…
-Spread and Restricted Isometry Properties of Sparse Random Matrices
Venkatesan Guruswami, Peter Manohar, Jonathan Mosheiff
Random subspaces of of dimension proportional to are, with high probability, well-spread with respect to the -norm. Namely, every nonzero i…
Bounds for list-decoding and list-recovery of random linear codes
Venkatesan Guruswami, Ray Li, Jonathan Mosheiff +3
A family of error-correcting codes is list-decodable from error fraction if, for every code in the family, the number of codewords in any Hamming ball of fractional radius …
LDPC Codes Achieve List Decoding Capacity
Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi +2
We show that Gallager's ensemble of Low-Density Parity Check (LDPC) codes achieves list-decoding capacity with high probability. These are the first graph-based codes shown to have…