All Publications

  • An Efficient Quantum Factoring Algorithm (link)
    Oded Regev
    Submitted, 2024. Quanta Magazine article. Science news.
  • Deciphering RNA splicing logic with interpretable machine learning (link)
    Susan E. Liao, Mukund Sudarshan, Oded Regev
    PNAS 2023.
  • Uncovering Distinct Peptide Charging Behaviors in Electrospray Ionization Mass (link)
    Allyn Muzhi Xu, Lauren Clarissa Tang, Marko Jovanovic, and Oded Regev
    Journal of the American Society for Mass Spectrometry, 2023
  • Splicing at the phase-separated nuclear speckle interface: a model (link)
    Susan E. Liao, Oded Regev
    Nucleic Acids Research, 2021
  • On the Gaussian surface area of spectrahedra (link)
    Srinivasan Arunachalam, Oded Regev, and Penghui Yao
    GAFA Seminar Notes
  • Polynomial Data Structure Lower Bounds in the Group Model (link)
    Alexander Golovnev, Gleb Posobin, Oded Regev, and Omri Weinstein
    FOCS 2020. SIAM J. Computation, 2021.
  • New bounds on the density of lattice coverings (link)
    Or Ordentlich, Oded Regev, and Barak Weiss
    Journal of the AMS.
  • Continuous LWE (link)
    Joan Bruna, Oded Regev, Min Jae Song, and Yi Tang
    STOC 2021
  • Nearly Optimal Embeddings of Flat Tori (link)
    Ishan Agarwal, Oded Regev, and Yi Tang
    APPROX 2020
  • Concentration of Markov chains with bounded moments (link)
    Assaf Naor, Shravas Rao, and Oded Regev
    Submitted
  • Bounds on Dimension Reduction in the Nuclear Norm (link)
    Oded Regev, and Thomas Vidick
    GAFA Seminar Notes
  • On Learning Mixtures of Well-Separated Gaussians (link)
    Oded Regev, Aravindan Vijayaraghavan
    FOCS 2017
  • A Sharp Tail Bound for the Expander Random Sampler (link)
    Shravas Rao, Oded Regev
    Submitted
  • Kneser graphs are like Swiss cheese (link)
    Ehud Friedgut, Oded Regev
    Discrete Analysis
  • A counterexample to a strong variant of the Polynomial Freiman-Ruzsa conjecture in Euclidean space (link)
    Shachar Lovett, Oded Regev
    Discrete Analysis
  • Pseudorandomness of Ring-LWE for Any Ring and Modulus (link)
    Chris Peikert, Oded Regev, Noah Stephens-Davidowitz
    STOC 2017
  • A Reverse Minkowski Theorem (link)
    Oded Regev, Noah Stephens-Davidowitz
    STOC 2017. Annals of Math.
  • A Note on Koldobsky's Lattice Slicing Inequality (link)
    Oded Regev
    Preprint
  • The Minrank of Random Graphs (link)
    Alexander Golovnev, Oded Regev, Omri Weinstein
    RANDOM 2017
  • Towards Strong Reverse Minkowski-type Inequalities for Lattices (link)
    Daniel Dadush, Oded Regev
    FOCS 2016
  • Counterexamples to a conjecture of Woods (link)
    Oded Regev, Uri Shapira, Barak Weiss
    Duke J Math
  • On the Space Complexity of Linear Programming with Preprocessing (link)
    Yael Tauman Kalai, Ran Raz, Oded Regev
    ITCS 2016
  • Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing (link)
    Andris Ambainis, Alexander Belov, Oded Regev, Ronald de Wolf
    SODA 2016
  • The Restricted Isometry Property of Subsampled Fourier Matrices (link)
    Ishay Haviv, Oded Regev
    SODA 2016
  • A Counterexample to Monotonicity of Relative Mass in Random Walks (link)
    Oded Regev, Igor Shinkar
    Electronic Communications in Probability
  • Beating the random assignment on constraint satisfaction problems of bounded degree (link)
    Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
    APPROX 2015
  • Recovering Short Generators of Principal Ideals in Cyclotomic Rings (link)
    Ronald Cramer, Léo Ducas, Chris Peikert, Oded Regev
    EUROCRYPT 2016
  • An Inequality for Gaussians on Lattices (link)
    Oded Regev, Noah Stephens-Davidowitz
    SIAM Journal on Discrete Mathematics
  • Tight Hardness of the Non-commutative Grothendieck Problem (link)
    Jop Briët, Oded Regev, Rishi Saket
    FOCS 2015
  • Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian Sampling (link)
    Divesh Aggarwal, Daniel Dadush, Oded Regev, Noah Stephens-Davidowitz
    STOC 2015
  • The List-Decoding Size of Fourier-Sparse Boolean Functions (link)
    Ishay Haviv, Oded Regev
    CCC 2015
  • On the Closest Vector Problem with a Distance Guarantee (link)
    Daniel Dadush, Oded Regev, Noah Stephens-Davidowitz
    CCC 2014
  • On the Lattice Isomorphism Problem (link)
    Ishay Haviv, Oded Regev
    SODA 2014
  • A Note on Discrete Gaussian Combinations of Lattice Vectors (link)
    Divesh Aggarwal, Oded Regev
    Submitted
  • Classical Hardness of Learning with Errors (link)
    Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, Damien Stehlé
    STOC 2013
  • A Toolkit for Ring-LWE Cryptography (link)
    Vadim Lyubashevsky, Chris Peikert, Oded Regev
    Eurocrypt 2013
  • Efficient rounding for the noncommutative Grothendieck inequality (link)
    Assaf Naor, Oded Regev, and Thomas Vidick
    STOC 2013
  • Locally decodable codes and the failure of cotype for projective tensor products (link)
    Jop Briët, Assaf Naor, Oded Regev
    Electronic Research Announcements in Mathematical Sciences 19 (2012) 120--130
  • Quantum XOR Games (link)
    Thomas Vidick, Oded Regev
    CCC 2013
  • Elementary Proofs of Grothendieck Theorems for Completely Bounded Norms (link)
    Thomas Vidick, Oded Regev
    Journal of Operator Theory
  • Krivine schemes are optimal (link)
    Assaf Naor, Oded Regev
    Proceedings of the AMS
  • Entropy-based Bounds on Dimension Reduction in L1 (link)
    Oded Regev
    Israel Journal of Mathematics
  • Bell Violations through Independent Bases Games (link)
    Oded Regev
    Quantum Information and Computation
  • Near-Optimal and Explicit Bell Inequality Violations (link)
    Harry Buhrman, Oded Regev, Giannicola Scarpa, Ronald de Wolf
    CCC 2011
  • Quantum One-Way Communication can be Exponentially Stronger Than Classical Communication (link,pptx)
    Bo'az Klartag, Oded Regev
    STOC 2011
  • An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance (link,pptx)
    Amit Chakrabarti, Oded Regev
    STOC 2011
  • The Learning with Errors Problem (pdf,ppt)
    Oded Regev
    Invited survey in CCC 2010
  • Lattice Enumeration using Extreme Pruning
    Nicolas Gama, Phong Q. Nguyen, Oded Regev
    Eurocrypt 2010
  • On Ideal Lattices and Learning with Errors Over Rings (pdf,link)
    Vadim Lyubashevsky, Chris Peikert, Oded Regev
    Eurocrypt 2010
  • The Euclidean Distortion of Flat Tori (pdf)
    Ishay Haviv, Oded Regev
    APPROX 2010
  • No Strong Parallel Repetition with Entangled and Non-signaling Provers (link)
    Julia Kempe, Oded Regev
    CCC 2010
  • Simultaneous Communication Protocols with Quantum and Classical Messages (pdf)
    Dmitry Gavinsky, Oded Regev, Ronald de Wolf
    Chicago Journal of Theoretical Computer Science 2008:7
  • Lattice-based Cryptography (pdf)
    Daniele Micciancio, Oded Regev
    Book chapter in Post-quantum Cryptography, D. J. Bernstein and J. Buchmann (eds.), Springer (2008)
  • Rounding Parallel Repetitions of Unique Games
    Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev, David Steurer
    Proc. of FOCS 2008
  • Impossibility of a Quantum Speed-up with a Faulty Oracle (pdf)
    Oded Regev, Liron Schiff
    Proc. of ICALP 2008
  • Quantum SAT for a qutrit-cinquit pair is QMA1-complete
    Lior Eldar, Oded Regev
    Proc. of ICALP 2008
  • Upper Bounds on the Noise Threshold for Fault-tolerant Quantum Computing (link)
    Julia Kempe, Oded Regev, Falk Unger, Ronald de Wolf
    Quantum Information and Computation 10(5), 361-376, 2010. Preliminary version in Proc. of ICALP 2008
  • Unique Games with Entangled Provers are Easy (link,ppt)
    Julia Kempe, Oded Regev, Ben Toner
    SIAM Journal on Computing 39(7), pp. 3207--3229, 2010. Preliminary version in Proc. of FOCS 2008
  • A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing (link,ppt)
    Avi Ben-Aroya, Oded Regev, Ronald de Wolf
    Proc. of FOCS 2008
  • Simulating Quantum Correlations with Finite Communication (link,ppt)
    Oded Regev, Ben Toner
    SIAM Journal on Computing 39(4), pp. 1562--1580, 2009. Preliminary version in Proc. of FOCS 2007
  • On the Complexity of Lattice Problems with Polynomial Approximation Factors (ps,pdf)
    Oded Regev
    Survey paper prepared for the LLL+25 conference. Appears in this book
  • Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors (link)
    Ishay Haviv, Oded Regev
    Theory of Computing 8(23), pp. 513-531, 2012. Preliminary version in STOC 2007
  • Lattice-based Cryptography (ps,pdf,ppt)
    Oded Regev
    Tutorial given in CRYPTO 2006
  • Independent Sets in Graph Powers are Almost Contained in Juntas (ps,pdf)
    Irit Dinur, Ehud Friedgut, Oded Regev
    GAFA 18(1) pp. 77-97, 2008
  • Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures (pdf,ppt)
    Phong Q. Nguyen, Oded Regev
    Eurocrypt 2006
  • On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy (ps,pdf)
    Ishay Haviv, Oded Regev, Amnon Ta-Shma
    Theory of Computing 3(3), pp. 45-60, 2007.
  • A Note on the Distribution of the Distance from a Lattice (pdf)
    Ishay Haviv, Vadim Lyubashevsky, Oded Regev
    Discrete and Computational Geometry
  • Hardness of the Covering Radius Problem on Lattices (ps,pdf,link)
    Ishay Haviv, Oded Regev
    Chicago Journal of Theoretical Computer Science. Preliminary version in Proc. of CCC 2006
  • Lattice Problems and Norm Embeddings (ps,pdf)
    Oded Regev, Ricky Rosen
    Proc. of STOC 2006
  • Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity (ps,pdf)
    Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf
    SIAM Journal on Computing 39(1), pp. 1--24, 2009. Preliminary version in Proc. of STOC 2006
  • Conditional Hardness for Approximate Coloring (pdf)
    Irit Dinur, Elchanan Mossel, Oded Regev
    SIAM Journal on Computing 39(3), pp. 843--873, 2009. Preliminary version in Proc. of STOC 2006
  • On Lattices, Learning with Errors, Random Linear Codes, and Cryptography (pdf,ppt)
    Oded Regev
    Journal of the ACM 56(6), article 34, 2009. Preliminary version in Proc. of STOC 2005
  • The Complexity of the Local Hamiltonian Problem (link)
    Julia Kempe, Alexei Kitaev, Oded Regev
    SIAM Journal on Computing 35(5), pp. 1070-1097, 2006. Preliminary version in Proc. of FSTTCS 2004
  • Non-Interactive Correlation Distillation, Inhomogeneous Markov Chains and the Reverse Bonami-Beckner Inequality (ps,pdf)
    Elchanan Mossel, Ryan O'Donnell, Oded Regev, Jeff Steif, Benny Sudakov
    Israel Journal of Mathematics 154, pp. 299-336, 2006
  • Lattice problems in NP intersect coNP (ps,pdf)
    Dorit Aharonov, Oded Regev
    Journal of the ACM 52(5), pp. 749-765, 2005. Preliminary version in Proc. of FOCS 2004
  • An Elementary Proof of the Adiabatic Theorem (link)
    Andris Ambainis, Oded Regev
  • A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space (link)
    Oded Regev
  • Worst-case to Average-case Reductions based on Gaussian Measures (ps,pdf)
    Daniele Micciancio, Oded Regev
    SIAM Journal on Computing 37(1) pp. 267-302, 2007. Preliminary version in Proc. of FOCS 2004
  • The Complexity of the Covering Radius Problem on Lattices (ps,pdf)
    Venkatesan Guruswami, Daniele Micciancio, Oded Regev
    Computational Complexity 14(2), pp. 90-121, 2005. Preliminary version in Proc. of CCC 2004
  • Randomised Nearest Neighbour Lower Bound (pdf)
    Amit Chakrabarti, Oded Regev
    SIAM Journal on Computing 39(5) pp. 1919-1940, 2010. Preliminary version in Proc. of FOCS 2004
  • A Lattice Problem in Quantum NP (link)
    Dorit Aharonov, Oded Regev
    Proc. of FOCS 2003
  • Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation (link)
    Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev
    SIAM Journal on Computing 37(1) pp. 166-194, 2007. Preliminary version in Proc. of FOCS 2004
  • New Lattice Based Cryptographic Constructions (psgz,pdf,ppt)
    Oded Regev
    Journal of the ACM 51(6), pp. 899-942, 2004. Preliminary version in Proc. of STOC 2003
  • Improved Inapproximability of Lattice and Coding Problems with Preprocessing (ps,pdf)
    Oded Regev
    IEEE Trans. on Info. Theory 50(9), pp. 2031-2037, 2004. Preliminary version in Proc. of CCC 2003
  • Vertex Cover Might be Hard to Approximate to within 2-ε (ps,pdf)
    Subhash Khot, Oded Regev
    Journal of Computer and System Sciences 74(3), pp. 335-349, 2008. Preliminary version in Proc. of CCC 2003
  • 3-Local Hamiltonian is QMA-complete (link)
    Julia Kempe, Oded Regev
    Quantum Information and Computation 3(3), 258-264, 2003
  • A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover (ps,pdf)
    Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev
    SIAM Journal on Computing 34(5), pp. 1129-1146, 2005. Preliminary version in STOC 2003
  • Long Monotone Paths in Line Arrangements (ps,pdf)
    Jozsef Balogh, Oded Regev, Clifford Smyth, William Steiger, Mario Szegedy
    Discrete and Computational Geometry 32(2), pp. 167-176, 2004. Preliminary version in SOCG 2003
  • The Hardness of Hypergraph Coloring (ps,pdf)
    Irit Dinur, Oded Regev, Clifford Smyth
    Combinatorica 25(5), pp. 519-535, 2005. Preliminary version in Proc. of FOCS 2002
  • Quantum Computation and Lattice Problems (ps,pdf)
    Oded Regev
    SIAM Journal on Computing 33(3), pp. 738-760, 2004. Preliminary version in Proc. of FOCS 2002
  • Priority Algorithms for Makespan Minimization in the Subset Model (ps,pdf)
    Oded Regev
    Information Processing Letters 84(3), pp. 153-157, 2003
  • On-line Restricted Assignment of Temporary Tasks with Unknown Durations (ps,pdf)
    Amitai Armon, Yossi Azar, Leah Epstein, Oded Regev
    Information Processing Letters 85(2), pp. 67-72, 2003
  • Temporary Tasks Assignment Resolved (ps,pdf)
    Amitai Armon, Yossi Azar, Leah Epstein, Oded Regev
    Algorithmica 36(3), pp. 295-314, 2003. Preliminary version in Proc. of SODA 2002
  • Combinatorial Algorithms for the Unsplittable Flow Problem (ps,pdf)
    Yossi Azar, Oded Regev
    Algorithmica 44(1) pp. 49-66, 2006. Preliminary version in Proc. of IPCO 2001
  • Maximizing Job Benefits On-line (ps,pdf)
    Baruch Awerbuch, Yossi Azar, Oded Regev
    Journal of Scheduling 4(6), pp. 287-296, 2001. Preliminary version in Proc. of APPROX 2000
  • Off-line Temporary Tasks Assignment (ps,pdf)
    Yossi Azar, Oded Regev, Jiří Sgall, Gerhard Woeginger
    Theoretical Computer Science 287(2), pp. 419-428, 2002. Preliminary version in Proc. of ESA 1999
  • Minimizing the Flow Time without Migration (ps,pdf)
    Baruch Awerbuch, Yossi Azar, Stefano Leonardi, Oded Regev
    SIAM Journal on Computing 31(5), pp. 1370-1382, 2002. Preliminary version in Proc. of STOC 1999
  • On-line Bin-Stretching (ps,pdf)
    Yossi Azar, Oded Regev
    Theoretical Computer Science 268(1), pp. 17-41, 2001. Preliminary version in Proc. of RANDOM 1998