I. Haviv

activity

20112026

most citedTensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors

48 citations · 68 across the 25 of their papers we have counts for

collaborators

Showing 2015Show all

2 papers · 1 filter

cs.DS2015

The Restricted Isometry Property of Subsampled Fourier Matrices

Ishay Haviv, Oded Regev

A matrix $A \in C^{q \times N}$ satisfies the restricted isometry property of order $k$ with constant $ε$ if it preserves the $ℓ_{2}$ norm of all $k$ -sparse vec…

cs.DS2015

The List-Decoding Size of Fourier-Sparse Boolean Functions

Ishay Haviv, Oded Regev

A function defined on the Boolean hypercube is $k$ -Fourier-sparse if it has at most $k$ nonzero Fourier coefficients. For a function $f : F_{2}^{n} \to R$ and…