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

On the Space Complexity of Linear Programming with Preprocessing (link)
Yael Tauman Kalai, Ran Raz, Oded Regev Submitted.

Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing (link)
Andris Ambainis, Alexander Belov, Oded Regev, Ronald de Wolf Submitted.

The Restricted Isometry Property of Subsampled Fourier Matrices (link)
Ishay Haviv, Oded Regev Submitted.

A Counterexample to Monotonicity of Relative Mass in Random Walks (link)
Oded Regev, Igor Shinkar Submitted.

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 StephensDavidowitz Submitted.

Tight Hardness of the Noncommutative 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 StephensDavidowitz STOC 2015.

The ListDecoding Size of FourierSparse Boolean Functions (link)
Ishay Haviv, Oded Regev CCC 2015.

On the Closest Vector Problem with a Distance Guarantee (link)
Daniel Dadush, Oded Regev, Noah StephensDavidowitz 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 RingLWE 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) 120130.

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.

Entropybased Bounds on Dimension Reduction in L_{1} (link)
Oded Regev Israel Journal of Mathematics.

Bell Violations through Independent Bases Games (link)
Oded Regev Quantum Information and Computation.

NearOptimal and Explicit Bell Inequality Violations (link)
Harry Buhrman, Oded Regev, Giannicola Scarpa, Ronald de Wolf CCC 2011.

Quantum OneWay 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 GapHammingDistance (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 Nonsignaling 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.

Latticebased Cryptography (pdf)
Daniele Micciancio, Oded Regev Book chapter in Postquantum 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 Speedup with a Faulty Oracle (pdf)
Oded Regev, Liron Schiff Proc. of ICALP 2008.

Quantum SAT for a qutritcinquit pair is QMA_{1}complete
Lior Eldar, Oded Regev Proc. of ICALP 2008.

Upper Bounds on the Noise Threshold for Faulttolerant Quantum Computing (link)
Julia Kempe, Oded Regev, Falk Unger, Ronald de Wolf Quantum Information and Computation 10(5), 361376, 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. 32073229, 2010. Preliminary version in Proc. of FOCS 2008.

A Hypercontractive Inequality for MatrixValued Functions with Applications to Quantum Computing (link,ppt)
Avi BenAroya, 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. 15621580, 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.

Tensorbased Hardness of the Shortest Vector Problem to within Almost Polynomial Factors (link)
Ishay Haviv, Oded Regev Theory of Computing 8(23), pp. 513531, 2012. Preliminary version in STOC 2007.

Latticebased 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. 7797, 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 PolynomialTime Hierarchy (ps,pdf)
Ishay Haviv, Oded Regev, Amnon TaShma Theory of Computing 3(3), pp. 4560, 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.

BoundedError 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. 124, 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. 843873, 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. 10701097, 2006. Preliminary version in Proc. of FSTTCS 2004.

NonInteractive Correlation Distillation, Inhomogeneous Markov Chains
and the Reverse BonamiBeckner Inequality (ps,pdf)
Elchanan Mossel, Ryan O'Donnell, Oded Regev, Jeff Steif, Benny Sudakov Israel Journal of Mathematics 154, pp. 299336, 2006.

Lattice problems in NP intersect coNP (ps,pdf)
Dorit Aharonov, Oded Regev Journal of the ACM 52(5), pp. 749765, 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

Worstcase to Averagecase Reductions based on Gaussian Measures (ps,pdf)
Daniele Micciancio, Oded Regev SIAM Journal on Computing 37(1) pp. 267302, 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. 90121, 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. 19191940, 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. 166194, 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. 899942, 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. 20312037, 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. 335349, 2008. Preliminary version in Proc. of CCC 2003.

3Local Hamiltonian is QMAcomplete (link)
Julia Kempe, Oded Regev Quantum Information and Computation 3(3), 258264, 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. 11291146, 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. 167176, 2004. Preliminary version in SOCG 2003.

The Hardness of Hypergraph Coloring (ps,pdf)
Irit Dinur, Oded Regev, Clifford Smyth Combinatorica 25(5), pp. 519535, 2005. Preliminary version in Proc. of FOCS 2002.

Quantum Computation and Lattice Problems (ps,pdf)
Oded Regev SIAM Journal on Computing 33(3), pp. 738760, 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. 153157, 2003.

Online Restricted Assignment of Temporary Tasks with Unknown Durations (ps,pdf)
Amitai Armon, Yossi Azar, Leah Epstein, Oded Regev Information Processing Letters 85(2), pp. 6772, 2003.

Temporary Tasks Assignment Resolved (ps,pdf)
Amitai Armon, Yossi Azar, Leah Epstein, Oded Regev Algorithmica 36(3), pp. 295314, 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. 4966, 2006. Preliminary version in Proc. of IPCO 2001.

Maximizing Job Benefits Online (ps,pdf)
Baruch Awerbuch, Yossi Azar, Oded Regev Journal of Scheduling 4(6), pp. 287296, 2001.
Preliminary version in Proc. of APPROX 2000.

Offline Temporary Tasks Assignment (ps,pdf)
Yossi Azar, Oded Regev, Jiří Sgall, Gerhard Woeginger Theoretical Computer Science 287(2), pp. 419428, 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. 13701382, 2002. Preliminary version in Proc. of STOC 1999.

Online BinStretching (ps,pdf)
Yossi Azar, Oded Regev Theoretical Computer Science 268(1), pp. 1741, 2001.
Preliminary version in Proc. of RANDOM 1998.
Personal:
Past teaching:
Undergraduate:

Discrete Math, Fall 2009

First Steps in Research, Fall 2009

Computational Complexity, Spring 2009

Workshop in Internet Technologies, Fall 2008

Computational Complexity, Spring 2008

Workshop in Internet Technologies, Fall 2007

Computational Complexity, Spring 2007

Workshop in Secure Computing, Fall 2006

Workshop in Secure Computing, Fall 2005

Discrete Math, Fall 2005

Discrete Math, Spring 2005

Discrete Math, Spring 2004

Graduate:

Introduction to Cryptography, Fall 2015

Introduction to Cryptography, Fall 2014

Introduction to Cryptography, Fall 2013

Lattices, Convexity and Algorithms, Spring 2013 (NYU; headed by Daniel Dadush)

Analytical Methods in Computer Science, Fall 2012 (NYU)

Analytical Methods in Comp. Sci., Spring 2011 (ENS, Paris)

Theory Seminar, 20042010

Lattices in Computer Science, Fall 2009

Analytical Methods in Comp. Sci., Fall 2007

Seminar in Coding Theory, Spring 2007

Coding Theory, Fall 2006

Seminar in Quantum Computing, Spring 2006

Quantum Computing, Fall 2005 + Spring 2006
with Amnon TaShma

Lattices in Computer Science, Fall 2004


