603 citations · 1.6k across the 72 of their papers we have counts for
7 papers · 1 filter
On Learning Mixtures of Well-Separated Gaussians
Oded Regev, Aravindan Vijayaraghavan
We consider the problem of efficiently learning mixtures of a large number of spherical Gaussians, when the components of the mixture are well separated. In the most basic form of…
The Restricted Isometry Property of Subsampled Fourier Matrices
Ishay Haviv, Oded Regev
A matrix satisfies the restricted isometry property of order with constant if it preserves the norm of all -sparse vec…
The List-Decoding Size of Fourier-Sparse Boolean Functions
Ishay Haviv, Oded Regev
A function defined on the Boolean hypercube is -Fourier-sparse if it has at most nonzero Fourier coefficients. For a function and…
On the Closest Vector Problem with a Distance Guarantee
Daniel Dadush, Oded Regev, Noah Stephens-Davidowitz
We present a substantially more efficient variant, both in terms of running time and size of preprocessing advice, of the algorithm by Liu, Lyubashevsky, and Micciancio for solving…
On the Lattice Isomorphism Problem
Ishay Haviv, Oded Regev
We study the Lattice Isomorphism Problem (LIP), in which given two lattices L_1 and L_2 the goal is to decide whether there exists an orthogonal linear transformation mapping L_1 t…
Efficient Rounding for the Noncommutative Grothendieck Inequality
Assaf Naor, Oded Regev, Thomas Vidick
The classical Grothendieck inequality has applications to the design of approximation algorithms for $\cclass{NP}$-hard optimization problem…
Quantum Computation and Lattice Problems
Oded Regev
We present the first explicit connection between quantum computation and lattice problems. Namely, we show a solution to the Unique Shortest Vector Problem (SVP) under the assumpti…