Oded Regev

ORCID

Publication Activity (10 Years)

Years Active: 1998-2024
Publications (10 Years): 34

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

STOC

FOCS

Publications

Oded Regev
On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. CoRR (2024)
Or Ordentlich, Oded Regev, Barak Weiss
Bounds on the density of smooth lattice coverings. CoRR (2023)
Oded Regev
An Efficient Quantum Factoring Algorithm. CoRR (2023)
Joan Bruna, Oded Regev, Min Jae Song, Yi Tang
Continuous LWE. STOC (2021)
Srinivasan Arunachalam, Oded Regev, Penghui Yao
On the Gaussian surface area of spectrahedra. Electron. Colloquium Comput. Complex. 28 (2021)
Ishan Agarwal, Oded Regev, Yi Tang
Nearly Optimal Embeddings of Flat Tori. APPROX-RANDOM (2020)
Joan Bruna, Oded Regev, Min Jae Song, Yi Tang
Continuous LWE. CoRR (2020)
Joan Bruna, Oded Regev, Min Jae Song, Yi Tang
Continuous LWE. Electron. Colloquium Comput. Complex. 27 (2020)
Or Ordentlich, Oded Regev, Barak Weiss
New bounds on the density of lattice coverings. CoRR (2020)
Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein
Polynomial Data Structure Lower Bounds in the Group Model. Electron. Colloquium Comput. Complex. 27 (2020)
Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein
Polynomial Data Structure Lower Bounds in the Group Model. FOCS (2020)
Ishay Haviv, Oded Regev, Amnon Ta-Shma
On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy. CoRR (2018)
Ishay Haviv, Oded Regev
Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors. CoRR (2018)
Alexander Golovnev, Oded Regev, Omri Weinstein
The Minrank of Random Graphs. IEEE Trans. Inf. Theory 64 (11) (2018)
Chris Peikert, Oded Regev, Noah Stephens-Davidowitz
Pseudorandomness of Ring-LWE for Any Ring and Modulus. IACR Cryptol. ePrint Arch. 2017 (2017)
Anna Gál, Michal Koucký, Oded Regev, Till Tantau
Computational Complexity of Discrete Problems (Dagstuhl Seminar 17121). Dagstuhl Reports 7 (3) (2017)
Chris Peikert, Oded Regev, Noah Stephens-Davidowitz
Pseudorandomness of ring-LWE for any ring and modulus. STOC (2017)
Oded Regev, Noah Stephens-Davidowitz
A reverse Minkowski theorem. STOC (2017)
Shravas Rao, Oded Regev
A Sharp Tail Bound for the Expander Random Sampler. CoRR (2017)
Oded Regev, Aravindan Vijayaraghavan
On Learning Mixtures of Well-Separated Gaussians. FOCS (2017)
Oded Regev, Noah Stephens-Davidowitz
An Inequality for Gaussians on Lattices. SIAM J. Discret. Math. 31 (2) (2017)
Oded Regev, Aravindan Vijayaraghavan
On Learning Mixtures of Well-Separated Gaussians. CoRR (2017)
Alexander Golovnev, Oded Regev, Omri Weinstein
The Minrank of Random Graphs. APPROX-RANDOM (2017)
Jop Briët, Oded Regev, Rishi Saket
Tight Hardness of the Non-Commutative Grothendieck Problem. Theory Comput. 13 (1) (2017)
Alexander Golovnev, Oded Regev, Omri Weinstein
The Minrank of Random Graphs. CoRR (2016)
Ishay Haviv, Oded Regev
The Restricted Isometry Property of Subsampled Fourier Matrices. SODA (2016)
Daniel Dadush, Oded Regev
Towards Strong Reverse Minkowski-Type Inequalities for Lattices. FOCS (2016)
Andris Ambainis, Aleksandrs Belovs, Oded Regev, Ronald de Wolf
Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing. SODA (2016)
Daniel Dadush, Oded Regev
Towards Strong Reverse Minkowski-type Inequalities for Lattices. CoRR (2016)
Yael Tauman Kalai, Ran Raz, Oded Regev
On the Space Complexity of Linear Programming with Preprocessing. ITCS (2016)
Ishay Haviv, Oded Regev
The List-Decoding Size of Fourier-Sparse Boolean Functions. ACM Trans. Comput. Theory 8 (3) (2016)
Divesh Aggarwal, Oded Regev
A Note on Discrete Gaussian Combinations of Lattice Vectors. Chic. J. Theor. Comput. Sci. 2016 (2016)
Alexander Golovnev, Oded Regev, Omri Weinstein
The Minrank of Random Graphs. Electron. Colloquium Comput. Complex. 23 (2016)
Ronald Cramer, Léo Ducas, Chris Peikert, Oded Regev
Recovering Short Generators of Principal Ideals in Cyclotomic Rings. EUROCRYPT (2) (2016)
Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
Beating the random assignment on constraint satisfaction problems of bounded degree. CoRR (2015)
Jop Briët, Oded Regev, Rishi Saket
Tight Hardness of the Non-commutative Grothendieck Problem. FOCS (2015)
Ishay Haviv, Oded Regev
The List-Decoding Size of Fourier-Sparse Boolean Functions. CoRR (2015)
Oded Regev, Thomas Vidick
Quantum XOR Games. ACM Trans. Comput. Theory 7 (4) (2015)
Ronald Cramer, Léo Ducas, Chris Peikert, Oded Regev
Recovering Short Generators of Principal Ideals in Cyclotomic Rings. IACR Cryptol. ePrint Arch. 2015 (2015)
Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree. APPROX-RANDOM (2015)
Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
Beating the random assignment on constraint satisfaction problems of bounded degree. Electron. Colloquium Comput. Complex. 22 (2015)
Ishay Haviv, Oded Regev
The List-Decoding Size of Fourier-Sparse Boolean Functions. Computational Complexity Conference (2015)
Divesh Aggarwal, Daniel Dadush, Oded Regev, Noah Stephens-Davidowitz
Time Using Discrete Gaussian Sampling: Extended Abstract. STOC (2015)
Ishay Haviv, Oded Regev
The Restricted Isometry Property of Subsampled Fourier Matrices. CoRR (2015)
Andris Ambainis, Aleksandrs Belovs, Oded Regev, Ronald de Wolf
Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing. CoRR (2015)
Jop Briët, Oded Regev
Tight Hardness of the Non-commutative Grothendieck Problem. CoRR (2014)
Divesh Aggarwal, Daniel Dadush, Oded Regev, Noah Stephens-Davidowitz
Solving the Shortest Vector Problem in $2^n$ Time via Discrete Gaussian Sampling. CoRR (2014)
Daniel Dadush, Oded Regev, Noah Stephens-Davidowitz
On the Closest Vector Problem with a Distance Guarantee. CoRR (2014)
Ishay Haviv, Oded Regev
On the Lattice Isomorphism Problem. SODA (2014)
Anna Gál, Michal Koucký, Oded Regev, Rüdiger Reischuk
Computational Complexity of Discrete Problems (Dagstuhl Seminar 14121). Dagstuhl Reports 4 (3) (2014)
Daniel Dadush, Oded Regev, Noah Stephens-Davidowitz
On the Closest Vector Problem with a Distance Guarantee. Computational Complexity Conference (2014)
Assaf Naor, Oded Regev, Thomas Vidick
Efficient Rounding for the Noncommutative Grothendieck Inequality. Theory Comput. 10 (2014)
Assaf Naor, Oded Regev, Thomas Vidick
Efficient rounding for the noncommutative grothendieck inequality. STOC (2013)
Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, Damien Stehlé
Classical Hardness of Learning with Errors. CoRR (2013)
Vadim Lyubashevsky, Chris Peikert, Oded Regev
On Ideal Lattices and Learning with Errors over Rings. J. ACM 60 (6) (2013)
Oded Regev, Thomas Vidick
Quantum XOR Games. Computational Complexity Conference (2013)
Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, Damien Stehlé
Classical hardness of learning with errors. STOC (2013)
Divesh Aggarwal, Oded Regev
A Note on Discrete Gaussian Combinations of Lattice Vectors. CoRR (2013)
Vadim Lyubashevsky, Chris Peikert, Oded Regev
A Toolkit for Ring-LWE Cryptography. IACR Cryptol. ePrint Arch. 2013 (2013)
Vadim Lyubashevsky, Chris Peikert, Oded Regev
A Toolkit for Ring-LWE Cryptography. EUROCRYPT (2013)
Ishay Haviv, Oded Regev
On the Lattice Isomorphism Problem. CoRR (2013)
Jop Briët, Assaf Naor, Oded Regev
Locally decodable codes and the failure of cotype for projective tensor products CoRR (2012)
Ishay Haviv, Oded Regev
Hardness of the Covering Radius Problem on Lattices. Chic. J. Theor. Comput. Sci. 2012 (2012)
Oded Regev
Bell violations through independent bases games. Quantum Inf. Comput. 12 (1-2) (2012)
Assaf Naor, Oded Regev, Thomas Vidick
Efficient rounding for the noncommutative Grothendieck inequality CoRR (2012)
Harry Buhrman, Oded Regev, Giannicola Scarpa, Ronald de Wolf
Near-Optimal and Explicit Bell Inequality Violations. Theory Comput. 8 (1) (2012)
Amit Chakrabarti, Oded Regev
An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance. SIAM J. Comput. 41 (5) (2012)
Ishay Haviv, Oded Regev
Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors. Theory Comput. 8 (1) (2012)
Vadim Lyubashevsky, Chris Peikert, Oded Regev
On Ideal Lattices and Learning with Errors Over Rings. IACR Cryptol. ePrint Arch. 2012 (2012)
Harry Buhrman, Oded Regev, Giannicola Scarpa, Ronald de Wolf
Near-Optimal and Explicit Bell Inequality Violations. Computational Complexity Conference (2011)
Amit Chakrabarti, Oded Regev
An optimal lower bound on the communication complexity of gap-hamming-distance. STOC (2011)
Oded Regev, Bo'az Klartag
Quantum one-way communication can be exponentially stronger than classical communication. STOC (2011)
Julia Kempe, Oded Regev
No Strong Parallel Repetition with Entangled and Non-signaling Provers. Computational Complexity Conference (2010)
Ishay Haviv, Oded Regev
The Euclidean Distortion of Flat Tori. APPROX-RANDOM (2010)
Julia Kempe, Oded Regev, Falk Unger, Ronald de Wolf
Upper bounds on the noise threshold for fault-tolerant quantum computing. Quantum Inf. Comput. 10 (5&6) (2010)
Bo'az Klartag, Oded Regev
Quantum One-Way Communication is Exponentially Stronger Than Classical Communication. Electron. Colloquium Comput. Complex. 17 (2010)
Bo'az Klartag, Oded Regev
Quantum One-Way Communication is Exponentially Stronger Than Classical Communication CoRR (2010)
Nicolas Gama, Phong Q. Nguyen, Oded Regev
Lattice Enumeration Using Extreme Pruning. EUROCRYPT (2010)
Amit Chakrabarti, Oded Regev
An Optimal Randomized Cell Probe Lower Bound for Approximate Nearest Neighbor Searching. SIAM J. Comput. 39 (5) (2010)
Vadim Lyubashevsky, Chris Peikert, Oded Regev
On Ideal Lattices and Learning with Errors over Rings. EUROCRYPT (2010)
Julia Kempe, Oded Regev, Ben Toner
Unique Games with Entangled Provers Are Easy. SIAM J. Comput. 39 (7) (2010)
Oded Regev
The Learning with Errors Problem (Invited Survey). Computational Complexity Conference (2010)
Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick, Ronald de Wolf
Better Gap-Hamming Lower Bounds via Better Round Elimination. APPROX-RANDOM (2010)
Amit Chakrabarti, Oded Regev
An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance. Electron. Colloquium Comput. Complex. 17 (2010)
Amit Chakrabarti, Oded Regev
An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance CoRR (2010)
Oded Regev
Learning with Errors over Rings. ANTS (2010)
Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf
Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity. SIAM J. Comput. 39 (1) (2009)
Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick, Ronald de Wolf
Better Gap-Hamming Lower Bounds via Better Round Elimination CoRR (2009)
Oded Regev, Ben Toner
Simulating Quantum Correlations with Finite Communication. SIAM J. Comput. 39 (4) (2009)
Julia Kempe, Oded Regev
No Strong Parallel Repetition with Entangled and Non-signaling Provers CoRR (2009)
Irit Dinur, Elchanan Mossel, Oded Regev
Conditional Hardness for Approximate Coloring. SIAM J. Comput. 39 (3) (2009)
Phong Q. Nguyen, Oded Regev
Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures. J. Cryptol. 22 (2) (2009)
Oded Regev
On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56 (6) (2009)
Ishay Haviv, Vadim Lyubashevsky, Oded Regev
A Note on the Distribution of the Distance from a Lattice. Discret. Comput. Geom. 41 (1) (2009)
Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev, David Steurer
Rounding Parallel Repetitions of Unique Games. FOCS (2008)
Dmitry Gavinsky, Oded Regev, Ronald de Wolf
Simultaneous Communication Protocols with Quantum and Classical Messages. Chic. J. Theor. Comput. Sci. 2008 (2008)
Avraham Ben-Aroya, Oded Regev, Ronald de Wolf
A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs. FOCS (2008)
Lior Eldar, Oded Regev
Quantum SAT for a Qutrit-Cinquit Pair Is QMA1-Complete. ICALP (1) (2008)
Oded Regev, Liron Schiff
Impossibility of a Quantum Speed-Up with a Faulty Oracle. ICALP (1) (2008)
Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev
Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation. SIAM Rev. 50 (4) (2008)

Oded Regev.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Oded Regev