Jonathan Mosheiff

activity

20192026

most cited

ℓ_{p}

-Spread and Restricted Isometry Properties of Sparse Random Matrices

27 citations · 46 across the 9 of their papers we have counts for

collaborators

Showing cs.CCShow all

4 papers · 1 filter

cs.CC2024

Low-Degree Polynomials Are Good Extractors

Omar Alrabiah, Jesse Goodman, Jonathan Mosheiff +1

We prove that random low-degree polynomials (over $F_{2}$ ) are unbiased, in an extremely general sense. That is, we show that random low-degree polynomials are good randomne…

cs.CC2022

Sparsity and $ℓ_{p}$ -Restricted Isometry

Venkatesan Guruswami, Peter Manohar, Jonathan Mosheiff

A matrix $A$ is said to have the $ℓ_{p}$ -Restricted Isometry Property ( $ℓ_{p}$ -RIP) if for all vectors $x$ of up to some sparsity $k$ , $∥ A x ∥_{p}$ is roughly proportional to $\|…

cs.CC2021

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,…

cs.CC2021★ 27 cited

$ℓ_{p}$ -Spread and Restricted Isometry Properties of Sparse Random Matrices

Venkatesan Guruswami, Peter Manohar, Jonathan Mosheiff

Random subspaces $X$ of $R^{n}$ of dimension proportional to $n$ are, with high probability, well-spread with respect to the $ℓ_{2}$ -norm. Namely, every nonzero $x \in X$ i…

Low-Degree Polynomials Are Good Extractors

Sparsity and ℓp​-Restricted Isometry

Punctured Low-Bias Codes Behave Like Random Linear Codes

ℓp​-Spread and Restricted Isometry Properties of Sparse Random Matrices

Sparsity and $ℓ_{p}$ -Restricted Isometry

$ℓ_{p}$ -Spread and Restricted Isometry Properties of Sparse Random Matrices