Oded Regev

According to our database, Oded Regev authored at least 96 papers between 1998 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Polynomial Data Structure Lower Bounds in the Group Model.

Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein

SIAM J. Comput., 2024

2023

Bounds on the density of smooth lattice coverings.

Or Ordentlich, Oded Regev, Barak Weiss

CoRR, 2023

An Efficient Quantum Factoring Algorithm.

Oded Regev

CoRR, 2023

2021

On the Gaussian surface area of spectrahedra.

Srinivasan Arunachalam, Oded Regev, Penghui Yao

Electron. Colloquium Comput. Complex., 2021

2020

Continuous LWE.

Joan Bruna, Oded Regev, Min Jae Song, Yi Tang

Electron. Colloquium Comput. Complex., 2020

New bounds on the density of lattice coverings.

Or Ordentlich, Oded Regev, Barak Weiss

CoRR, 2020

Nearly Optimal Embeddings of Flat Tori.

Ishan Agarwal, Oded Regev, Yi Tang

Proceedings of the Approximation, 2020

2017

Tight Hardness of the Non-Commutative Grothendieck Problem.

Jop Briët, Oded Regev, Rishi Saket

Theory Comput., 2017

An Inequality for Gaussians on Lattices.

Oded Regev, Noah Stephens-Davidowitz

SIAM J. Discret. Math., 2017

Pseudorandomness of Ring-LWE for Any Ring and Modulus.

Chris Peikert, Oded Regev, Noah Stephens-Davidowitz

IACR Cryptol. ePrint Arch., 2017

Computational Complexity of Discrete Problems (Dagstuhl Seminar 17121).

Anna Gál, Michal Koucký, Oded Regev, Till Tantau

Dagstuhl Reports, 2017

A Sharp Tail Bound for the Expander Random Sampler.

Shravas Rao, Oded Regev

CoRR, 2017

A reverse Minkowski theorem.

Oded Regev, Noah Stephens-Davidowitz

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

On Learning Mixtures of Well-Separated Gaussians.

Oded Regev, Aravindan Vijayaraghavan

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016

The List-Decoding Size of Fourier-Sparse Boolean Functions.

Ishay Haviv, Oded Regev

ACM Trans. Comput. Theory, 2016

The Minrank of Random Graphs.

Alexander Golovnev, Oded Regev, Omri Weinstein

Electron. Colloquium Comput. Complex., 2016

A Note on Discrete Gaussian Combinations of Lattice Vectors.

Divesh Aggarwal, Oded Regev

Chic. J. Theor. Comput. Sci., 2016

The Restricted Isometry Property of Subsampled Fourier Matrices.

Ishay Haviv, Oded Regev

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing.

Andris Ambainis, Aleksandrs Belovs, Oded Regev, Ronald de Wolf

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

On the Space Complexity of Linear Programming with Preprocessing.

Yael Tauman Kalai, Ran Raz, Oded Regev

Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

Towards Strong Reverse Minkowski-Type Inequalities for Lattices.

Daniel Dadush, Oded Regev

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Quantum XOR Games.

Oded Regev, Thomas Vidick

ACM Trans. Comput. Theory, 2015

Recovering Short Generators of Principal Ideals in Cyclotomic Rings.

Ronald Cramer, Léo Ducas, Chris Peikert, Oded Regev

IACR Cryptol. ePrint Arch., 2015

Beating the random assignment on constraint satisfaction problems of bounded degree.

Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright

Electron. Colloquium Comput. Complex., 2015

Solving the Shortest Vector Problem in 2ⁿ Time Using Discrete Gaussian Sampling: Extended Abstract.

Divesh Aggarwal, Daniel Dadush, Oded Regev, Noah Stephens-Davidowitz

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

2014

Efficient Rounding for the Noncommutative Grothendieck Inequality.

Assaf Naor, Oded Regev, Thomas Vidick

Theory Comput., 2014

Computational Complexity of Discrete Problems (Dagstuhl Seminar 14121).

Anna Gál, Michal Koucký, Oded Regev, Rüdiger Reischuk

Dagstuhl Reports, 2014

Tight Hardness of the Non-commutative Grothendieck Problem.

Jop Briët, Oded Regev

CoRR, 2014

Solving the Shortest Vector Problem in $2^n$ Time via Discrete Gaussian Sampling.

Divesh Aggarwal, Daniel Dadush, Oded Regev, Noah Stephens-Davidowitz

CoRR, 2014

On the Lattice Isomorphism Problem.

Ishay Haviv, Oded Regev

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

On the Closest Vector Problem with a Distance Guarantee.

Daniel Dadush, Oded Regev, Noah Stephens-Davidowitz

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013

On Ideal Lattices and Learning with Errors over Rings.

Vadim Lyubashevsky, Chris Peikert, Oded Regev

J. ACM, 2013

A Toolkit for Ring-LWE Cryptography.

Vadim Lyubashevsky, Chris Peikert, Oded Regev

IACR Cryptol. ePrint Arch., 2013

Classical hardness of learning with errors.

Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, Damien Stehlé

Proceedings of the Symposium on Theory of Computing Conference, 2013

2012

Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors.

Ishay Haviv, Oded Regev

Theory Comput., 2012

Near-Optimal and Explicit Bell Inequality Violations.

Harry Buhrman, Oded Regev, Giannicola Scarpa, Ronald de Wolf

Theory Comput., 2012

An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance.

Amit Chakrabarti, Oded Regev

SIAM J. Comput., 2012

Bell violations through independent bases games.

Oded Regev

Quantum Inf. Comput., 2012

Locally decodable codes and the failure of cotype for projective tensor products

Jop Briët, Assaf Naor, Oded Regev

CoRR, 2012

Hardness of the Covering Radius Problem on Lattices.

Ishay Haviv, Oded Regev

Chic. J. Theor. Comput. Sci., 2012

2011

Quantum one-way communication can be exponentially stronger than classical communication.

Oded Regev, Bo'az Klartag

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

2010

On the Complexity of Lattice Problems with Polynomial Approximation Factors.

Oded Regev

Proceedings of the LLL Algorithm - Survey and Applications, 2010

Unique Games with Entangled Provers Are Easy.

Julia Kempe, Oded Regev, Ben Toner

SIAM J. Comput., 2010

An Optimal Randomized Cell Probe Lower Bound for Approximate Nearest Neighbor Searching.

Amit Chakrabarti, Oded Regev

SIAM J. Comput., 2010

Upper bounds on the noise threshold for fault-tolerant quantum computing.

Julia Kempe, Oded Regev, Falk Unger, Ronald de Wolf

Quantum Inf. Comput., 2010

Quantum One-Way Communication is Exponentially Stronger Than Classical Communication.

Bo'az Klartag, Oded Regev

Electron. Colloquium Comput. Complex., 2010

Lattice Enumeration Using Extreme Pruning.

Nicolas Gama, Phong Q. Nguyen, Oded Regev

Proceedings of the Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco / French Riviera, May 30, 2010

The Learning with Errors Problem (Invited Survey).

Oded Regev

Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

No Strong Parallel Repetition with Entangled and Non-signaling Provers.

Julia Kempe, Oded Regev

Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

The Euclidean Distortion of Flat Tori.

Ishay Haviv, Oded Regev

Proceedings of the Approximation, 2010

Better Gap-Hamming Lower Bounds via Better Round Elimination.

Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick, Ronald de Wolf

Proceedings of the Approximation, 2010

Learning with Errors over Rings.

Oded Regev

Proceedings of the Algorithmic Number Theory, 9th International Symposium, 2010

2009

Simulating Quantum Correlations with Finite Communication.

Oded Regev, Ben Toner

SIAM J. Comput., 2009

Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity.

Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf

SIAM J. Comput., 2009

Conditional Hardness for Approximate Coloring.

Irit Dinur, Elchanan Mossel, Oded Regev

SIAM J. Comput., 2009

Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures.

Phong Q. Nguyen, Oded Regev

J. Cryptol., 2009

On lattices, learning with errors, random linear codes, and cryptography.

Oded Regev

J. ACM, 2009

A Note on the Distribution of the Distance from a Lattice.

Ishay Haviv, Vadim Lyubashevsky, Oded Regev

Discret. Comput. Geom., 2009

2008

Vertex cover might be hard to approximate to within 2-epsilon.

Subhash Khot, Oded Regev

J. Comput. Syst. Sci., 2008

Simultaneous Communication Protocols with Quantum and Classical Messages.

Dmitry Gavinsky, Oded Regev, Ronald de Wolf

Chic. J. Theor. Comput. Sci., 2008

Impossibility of a Quantum Speed-Up with a Faulty Oracle.

Oded Regev, Liron Schiff

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Quantum SAT for a Qutrit-Cinquit Pair Is QMA1-Complete.

Lior Eldar, Oded Regev

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs.

Avraham Ben-Aroya, Oded Regev, Ronald de Wolf

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Rounding Parallel Repetitions of Unique Games.

Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev, David Steurer

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy.

Ishay Haviv, Oded Regev, Amnon Ta-Shma

Theory Comput., 2007

Worst-Case to Average-Case Reductions Based on Gaussian Measures.

Daniele Micciancio, Oded Regev

SIAM J. Comput., 2007

Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation.

Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev

SIAM J. Comput., 2007

The Unique Games Conjecture with Entangled Provers is False.

Julia Kempe, Oded Regev, Ben Toner

Proceedings of the Algebraic Methods in Computational Complexity, 07.10. - 12.10.2007, 2007

2006

The Complexity of the Local Hamiltonian Problem.

Julia Kempe, Alexei Y. Kitaev, Oded Regev

SIAM J. Comput., 2006

Combinatorial Algorithms for the Unsplittable Flow Problem.

Yossi Azar, Oded Regev

Algorithmica, 2006

Lattice problems and norm embeddings.

Oded Regev, Ricky Rosen

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Lattice-Based Cryptography.

Oded Regev

Proceedings of the Advances in Cryptology, 2006

2005

A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover.

Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev

SIAM J. Comput., 2005

Lattice problems in NP cap coNP.

Dorit Aharonov, Oded Regev

J. ACM, 2005

The Hardness of 3-Uniform Hypergraph Coloring.

Irit Dinur, Oded Regev, Clifford D. Smyth

Comb., 2005

The complexity of the covering radius problem.

Venkatesan Guruswami, Daniele Micciancio, Oded Regev

Comput. Complex., 2005

2004

Improved Inapproximability of Lattice and Coding Problems With Preprocessing.

Oded Regev

IEEE Trans. Inf. Theory, 2004

Quantum Computation and Lattice Problems.

Oded Regev

SIAM J. Comput., 2004

New lattice-based cryptographic constructions.

Oded Regev

J. ACM, 2004

Long Monotone Paths in Line Arrangements.

József Balogh, Oded Regev, Clifford D. Smyth, William L. Steiger, Mario Szegedy

Discret. Comput. Geom., 2004

The Complexity of the Covering Radius Problem on Lattices and Codes.

Venkatesan Guruswami, Daniele Micciancio, Oded Regev

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

2003

3-local Hamiltonian is QMA-complete.

Julia Kempe, Oded Regev

Quantum Inf. Comput., 2003

On-line restricted assignment of temporary tasks with unknown durations.

Amitai Armon, Yossi Azar, Leah Epstein, Oded Regev

Inf. Process. Lett., 2003

An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching

Amit Chakrabarti, Oded Regev

Electron. Colloquium Comput. Complex., 2003

A Lattice Problem in Quantum NP.

Dorit Aharonov, Oded Regev

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

Vertex Cover Might be Hard to Approximate to within 2-\varepsilon.

Subhash Khot, Oded Regev

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

Off-line temporary tasks assignment.

Yossi Azar, Oded Regev, Jirí Sgall, Gerhard J. Woeginger

Theor. Comput. Sci., 2002

Minimizing the Flow Time Without Migration.

Baruch Awerbuch, Yossi Azar, Stefano Leonardi, Oded Regev

SIAM J. Comput., 2002

Priority algorithms for makespan minimization in the subset model.

Oded Regev

Inf. Process. Lett., 2002

Temporary tasks assignment resolved.

Amitai Armon, Yossi Azar, Leah Epstein, Oded Regev

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

2001

Scheduling and load balancing

Oded Regev

PhD thesis, 2001

On-line bin-stretching.

Yossi Azar, Oded Regev

Theor. Comput. Sci., 2001

Strongly Polynomial Algorithms for the Unsplittable Flow Problem.

Yossi Azar, Oded Regev

Proceedings of the Integer Programming and Combinatorial Optimization, 2001

2000

Maximizing job benefits on-line.

Baruch Awerbuch, Yossi Azar, Oded Regev

Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2000

1999

Off-Line Temporary Tasks Assignment.

Yossi Azar, Oded Regev

Proceedings of the Algorithms, 1999

1998

Globally Distributed Computation over the Internet - The POPCORN Project.

Noam Nisan, Shmulik London, Oded Regev, Noam Camiel

Proceedings of the 18th International Conference on Distributed Computing Systems, 1998