Publications (55)
The Restricted Isometry Property of Subsampled Fourier Matrices
Ishay Haviv, Oded Regev
A Note on Koldobsky's Lattice Slicing Inequality
Oded Regev
Impossibility of a Quantum Speed-up with a Faulty Oracle
Oded Regev, Liron Schiff
Simultaneous Communication Protocols with Quantum and Classical Messages
Dmitry Gavinsky, Oded Regev, Ronald de Wolf
Concentration of Markov chains with bounded moments
Assaf Naor, Shravas Rao, Oded Regev
A Lattice Problem in Quantum NP
Dorit Aharonov, Oded Regev
Chaos and complexity in astrophysics
Oded Regev
Entropy-based Bounds on Dimension Reduction in L_1
Oded Regev
Conditional Hardness for Approximate Coloring
Irit Dinur, Elchanan Mossel, Oded Regev
3-Local Hamiltonian is QMA-complete
Julia Kempe, Oded Regev
Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors
Ishay Haviv, Oded Regev
Quantum XOR Games
Oded Regev, Thomas Vidick
On Learning Mixtures of Well-Separated Gaussians
Oded Regev, Aravindan Vijayaraghavan
Quantum Computation and Lattice Problems
Oded Regev
Launching jets from the boundary layer of accretion disks in young stellar objects
Noam Soker, Oded Regev
Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing
Andris Ambainis, Aleksandrs Belovs, Oded Regev +1
Global transient dynamics of three-dimensional hydrodynamical disturbances in a thin viscous accretion disk
Paola Rebusco, Orkan M. Umurhan, Wlodek Kluzniak +1
Bell Violations through Independent Bases Games
Oded Regev
Better Gap-Hamming Lower Bounds via Better Round Elimination
Joshua Brody, Amit Chakrabarti, Oded Regev +2
The List-Decoding Size of Fourier-Sparse Boolean Functions
Ishay Haviv, Oded Regev
New Lattice Based Cryptographic Constructions
Oded Regev
A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space
Oded Regev
Locally decodable codes and the failure of cotype for projective tensor products
Jop Briet, Assaf Naor, Oded Regev
A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs
Avraham Ben-Aroya, Oded Regev, Ronald de Wolf
Elementary Proofs of Grothendieck Theorems for Completely Bounded Norms
Oded Regev, Thomas Vidick
Beating the random assignment on constraint satisfaction problems of bounded degree
Boaz Barak, Ankur Moitra, Ryan O'Donnell +7
Hydrodynamical activity in thin accretion disks
Oded Regev
An Elementary Proof of the Quantum Adiabatic Theorem
Andris Ambainis, Oded Regev
Solving the Shortest Vector Problem in $2^n$ Time via Discrete Gaussian Sampling
Divesh Aggarwal, Daniel Dadush, Oded Regev +1
A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
Irit Dinur, Venkatesan Guruswami, Subhash Khot +1
An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
Amit Chakrabarti, Oded Regev
A counterexample to a strong variant of the Polynomial Freiman-Ruzsa conjecture in Euclidean space
Shachar Lovett, Oded Regev
Krivine schemes are optimal
Assaf Naor, Oded Regev
Kneser graphs are like Swiss cheese
Ehud Friedgut, Oded Regev
An Inequality for Gaussians on Lattices
Oded Regev, Noah Stephens-Davidowitz
A Note on Discrete Gaussian Combinations of Lattice Vectors
Divesh Aggarwal, Oded Regev
Classical Hardness of Learning with Errors
Zvika Brakerski, Adeline Langlois, Chris Peikert +2
Towards Strong Reverse Minkowski-type Inequalities for Lattices
Daniel Dadush, Oded Regev
The Complexity of the Local Hamiltonian Problem
Julia Kempe, Alexei Kitaev, Oded Regev
On the Lattice Isomorphism Problem
Ishay Haviv, Oded Regev
The Minrank of Random Graphs
Alexander Golovnev, Oded Regev, Omri Weinstein
Quantum One-Way Communication is Exponentially Stronger Than Classical Communication
Bo'az Klartag, Oded Regev
A Counterexample to Monotonicity of Relative Mass in Random Walks
Oded Regev, Igor Shinkar
Counterexamples to a conjecture of Woods
Oded Regev, Uri Shapira, Barak Weiss
Bounds on Dimension Reduction in the Nuclear Norm
Oded Regev, Thomas Vidick
Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality
Elchanan Mossel, Ryan O'Donnell, Oded Regev +2
Upper Bounds on the Noise Threshold for Fault-tolerant Quantum Computing
Julia Kempe, Oded Regev, Falk Unger +1
On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy
Ishay Haviv, Oded Regev, Amnon Ta-Shma
Thermal Equilibria of Accretion Disks
Marek A. Abramowicz, Xingming Chen, Shoji Kato +2
On the Closest Vector Problem with a Distance Guarantee
Daniel Dadush, Oded Regev, Noah Stephens-Davidowitz
Simulating Quantum Correlations with Finite Communication
Oded Regev, Ben Toner
Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation
Dorit Aharonov, Wim van Dam, Julia Kempe +3
Unique Games with Entangled Provers are Easy
Julia Kempe, Oded Regev, Ben Toner
A Sharp Tail Bound for the Expander Random Sampler
Shravas Rao, Oded Regev
No Strong Parallel Repetition with Entangled and Non-signaling Provers
Julia Kempe, Oded Regev