Oded Regev

Address:

  • Courant Institute of Mathematical Sciences
  • New York University
  • 251 Mercer Street
  • New York, NY 10012
  • Office: WWH 303 (251 Mercer St)
  • Tel: +1-(212)-998-3771
  • lästnamë äţ cims dŏt nyu dőt edu

New:

TCS+, an online seminar series in theoretical computer science, accessible to the widest possible audience, and ensuring a carbon-free dissemination of ideas across the globe.

Students (theses available here):

Ph.D.:
M.Sc.:
  • Guy Moshkovitz (2011)
  • Michal Moshkovitz (2010, joint with Amir Shpilka)
  • Liron Schiff (2008)
  • Lior Eldar (2008)
  • Ishay Haviv (2006)
  • Ricky Rosen (2005)

Professional activities:

Publications (BibTex):

  • 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
    Submitted.
  • An Inequality for Gaussians on Lattices (link)
    Oded Regev, Noah Stephens-Davidowitz
    Submitted.
  • 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.
  • 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.

Personal:

Past teaching:

Undergraduate:
Graduate:
Me