5 papers
Discrepancy for Random Linear Codes
Dean Doron, Tal Leonov, Jonathan Mosheiff +3
We prove that random linear codes have nearly optimal discrepancy properties in a broad range of regimes. Our main results are two general theorems: one controlling all translates…
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…
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 de…
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…
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…