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.

Currently teaching:

Introduction to Cryptography (Fall 2014)

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):

  • 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