Oded Regev

Address:

Blavatnik School of Computer Science
Tel-Aviv University
Tel-Aviv 69978
Israel
Tel: (+972)-3-640-7996
Fax: (+972)-3-640-9357
Office: Schreiber 103
odedr@tau dŏt ac dőt il

Our new Foundations of Computing group website

Teaching:

Undergraduate:

Graduate:

Theory Seminar, 2004-
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 Ta-Shma
Lattices in Computer Science, Fall 2004

Professional activities:

Selected Publications (see all or download as BibTex):

No Strong Parallel Repetition with Entangled and Non-signaling Provers (link)
Julia Kempe, Oded Regev
Submitted.
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
Proc. of ICALP 2008.
Unique Games with Entangled Provers are Easy (link,ppt)
Julia Kempe, Oded Regev, Ben Toner
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
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.
Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors (ps,pdf)
Ishay Haviv, Oded Regev
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)
Ishay Haviv, Oded Regev
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
Proc. of STOC 2006.
Conditional Hardness for Approximate Coloring (pdf)
Irit Dinur, Elchanan Mossel, Oded Regev
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
Submitted.
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
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.