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:

Lattices, Convexity and Algorithms (headed by Daniel Dadush)

Students (theses available here):

Ph.D.:

Klim Efremenko (2012, joint with Amnon Ta-Shma)
Ishay Haviv (2011)
Avi Ben-Aroya (2011, joint with Amnon Ta-Shma)
Iftah Gamzu (2010, joint with Yossi Azar)
Ricky Rosen (2010, joint with Ran Raz)

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:

Theory of Computing (Associate Editor-in-Chief)
STOC 2004, CCC 2005, TCC 2007, ANTS 2008, STOC 2008, CCC 2009 , STOC 2010 , STOC 2012

Publications (BibTex):

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
Entropy-based Bounds on Dimension Reduction in L₁ (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 QMA₁-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:

My brother is the creator of SafeWallet, the best password manager out there!
Due to popular demand, I created a page of PowerPoint tips and tricks.

Past teaching:

Undergraduate:

Graduate: