Oded Regev

Ishay Haviv, Oded Regev: Hardness of the Covering Radius Problem on Lattices. Chicago J. Theor. Comput. Sci. 2012 (2012)

Oded Regev: Bell violations through independent bases games. Quantum Information & Computation 12(1-2): 9-20 (2012)

Amit Chakrabarti, Oded Regev: An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance. SIAM J. Comput. 41(5): 1299-1317 (2012)

Ishay Haviv, Oded Regev: Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors. Theory of Computing 8(1): 513-531 (2012)

Harry Buhrman, Oded Regev, Giannicola Scarpa, Ronald de Wolf: Near-Optimal and Explicit Bell Inequality Violations. Theory of Computing 8(1): 623-645 (2012)

Jop Briët, Assaf Naor, Oded Regev: Locally decodable codes and the failure of cotype for projective tensor products. CoRR abs/1208.0539 (2012)

Assaf Naor, Oded Regev, Thomas Vidick: Efficient rounding for the noncommutative Grothendieck inequality. CoRR abs/1210.7656 (2012)

Vadim Lyubashevsky, Chris Peikert, Oded Regev: On Ideal Lattices and Learning with Errors Over Rings. IACR Cryptology ePrint Archive 2012: 230 (2012)

Harry Buhrman, Oded Regev, Giannicola Scarpa, Ronald de Wolf: Near-Optimal and Explicit Bell Inequality Violations. IEEE Conference on Computational Complexity 2011: 157-166

Oded Regev, Bo'az Klartag: Quantum one-way communication can be exponentially stronger than classical communication. STOC 2011: 31-40

Amit Chakrabarti, Oded Regev: An optimal lower bound on the communication complexity of gap-hamming-distance. STOC 2011: 51-60

Julia Kempe, Oded Regev, Falk Unger, Ronald de Wolf: Upper bounds on the noise threshold for fault-tolerant quantum computing. Quantum Information & Computation 10(5&6): 361-376 (2010)

Amit Chakrabarti, Oded Regev: An Optimal Randomized Cell Probe Lower Bound for Approximate Nearest Neighbor Searching. SIAM J. Comput. 39(5): 1919-1940 (2010)

Julia Kempe, Oded Regev, Ben Toner: Unique Games with Entangled Provers Are Easy. SIAM J. Comput. 39(7): 3207-3229 (2010)

Oded Regev: Learning with Errors over Rings. ANTS 2010: 3

Ishay Haviv, Oded Regev: The Euclidean Distortion of Flat Tori. APPROX-RANDOM 2010: 232-245

Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick, Ronald de Wolf: Better Gap-Hamming Lower Bounds via Better Round Elimination. APPROX-RANDOM 2010: 476-489

Julia Kempe, Oded Regev: No Strong Parallel Repetition with Entangled and Non-signaling Provers. IEEE Conference on Computational Complexity 2010: 7-15

Oded Regev: The Learning with Errors Problem (Invited Survey). IEEE Conference on Computational Complexity 2010: 191-204

Vadim Lyubashevsky, Chris Peikert, Oded Regev: On Ideal Lattices and Learning with Errors over Rings. EUROCRYPT 2010: 1-23

Nicolas Gama, Phong Q. Nguyen, Oded Regev: Lattice Enumeration Using Extreme Pruning. EUROCRYPT 2010: 257-278

Amit Chakrabarti, Oded Regev: An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance. CoRR abs/1009.3460 (2010)

Bo'az Klartag, Oded Regev: Quantum One-Way Communication is Exponentially Stronger Than Classical Communication. CoRR abs/1009.3640 (2010)

Amit Chakrabarti, Oded Regev: An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance. Electronic Colloquium on Computational Complexity (ECCC) 17: 140 (2010)

Bo'az Klartag, Oded Regev: Quantum One-Way Communication is Exponentially Stronger Than Classical Communication. Electronic Colloquium on Computational Complexity (ECCC) 17: 143 (2010)

Ishay Haviv, Vadim Lyubashevsky, Oded Regev: A Note on the Distribution of the Distance from a Lattice. Discrete & Computational Geometry 41(1): 162-176 (2009)

Oded Regev: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6) (2009)

Phong Q. Nguyen, Oded Regev: Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures. J. Cryptology 22(2): 139-160 (2009)

Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf: Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity. SIAM J. Comput. 39(1): 1-24 (2009)

Irit Dinur, Elchanan Mossel, Oded Regev: Conditional Hardness for Approximate Coloring. SIAM J. Comput. 39(3): 843-873 (2009)

Oded Regev, Ben Toner: Simulating Quantum Correlations with Finite Communication. SIAM J. Comput. 39(4): 1562-1580 (2009)

Oded Regev: Astrophysics, Chaos and Complexity in. Encyclopedia of Complexity and Systems Science 2009: 381-399

Julia Kempe, Oded Regev: No Strong Parallel Repetition with Entangled and Non-signaling Provers. CoRR abs/0911.0201 (2009)

Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick, Ronald de Wolf: Better Gap-Hamming Lower Bounds via Better Round Elimination. CoRR abs/0912.5276 (2009)

Dmitry Gavinsky, Oded Regev, Ronald de Wolf: Simultaneous Communication Protocols with Quantum and Classical Messages. Chicago J. Theor. Comput. Sci. 2008 (2008)

Subhash Khot, Oded Regev: Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci. 74(3): 335-349 (2008)

Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev, David Steurer: Rounding Parallel Repetitions of Unique Games. FOCS 2008: 374-383

Julia Kempe, Oded Regev, Ben Toner: Unique Games with Entangled Provers are Easy. FOCS 2008: 457-466

Avraham Ben-Aroya, Oded Regev, Ronald de Wolf: A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs. FOCS 2008: 477-486

Oded Regev, Liron Schiff: Impossibility of a Quantum Speed-Up with a Faulty Oracle. ICALP (1) 2008: 773-781

Julia Kempe, Oded Regev, Falk Unger, Ronald de Wolf: Upper Bounds on the Noise Threshold for Fault-Tolerant Quantum Computing. ICALP (1) 2008: 845-856

Lior Eldar, Oded Regev: Quantum SAT for a Qutrit-Cinquit Pair Is QMA1-Complete. ICALP (1) 2008: 881-892

Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev: Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation. SIAM J. Comput. 37(1): 166-194 (2007)

Daniele Micciancio, Oded Regev: Worst-Case to Average-Case Reductions Based on Gaussian Measures. SIAM J. Comput. 37(1): 267-302 (2007)

Ishay Haviv, Oded Regev, Amnon Ta-Shma: On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy. Theory of Computing 3(1): 45-60 (2007)

Julia Kempe, Oded Regev, Ben Toner: The Unique Games Conjecture with Entangled Provers is False. Algebraic Methods in Computational Complexity 2007

Oded Regev, Ben Toner: Simulating Quantum Correlations with Finite Communication. FOCS 2007: 384-394

Ishay Haviv, Oded Regev: Tensor-based hardness of the shortest vector problem to within almost polynomial factors. STOC 2007: 469-477

Oded Regev: Chaos and complexity in astrophysics. Cambridge University Press 2006, isbn 978-0-521-85534-1, pp. I-XI, 1-455

Yossi Azar, Oded Regev: Combinatorial Algorithms for the Unsplittable Flow Problem. Algorithmica 44(1): 49-66 (2006)

Julia Kempe, Alexei Kitaev, Oded Regev: The Complexity of the Local Hamiltonian Problem. SIAM J. Comput. 35(5): 1070-1097 (2006)

Ishay Haviv, Oded Regev: Hardness of the Covering Radius Problem on Lattices. IEEE Conference on Computational Complexity 2006: 145-158

Oded Regev: Lattice-Based Cryptography. CRYPTO 2006: 131-141

Phong Q. Nguyen, Oded Regev: Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures. EUROCRYPT 2006: 271-288

Irit Dinur, Elchanan Mossel, Oded Regev: Conditional hardness for approximate coloring. STOC 2006: 344-353

Oded Regev, Ricky Rosen: Lattice problems and norm embeddings. STOC 2006: 447-456

Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf: Bounded-error quantum state identification and exponential separations in communication complexity. STOC 2006: 594-603

Venkatesan Guruswami, Daniele Micciancio, Oded Regev: The complexity of the covering radius problem. Computational Complexity 14(2): 90-121 (2005)

Irit Dinur, Oded Regev, Clifford D. Smyth: The Hardness of 3-Uniform Hypergraph Coloring. Combinatorica 25(5): 519-535 (2005)

Dorit Aharonov, Oded Regev: Lattice problems in NP cap coNP. J. ACM 52(5): 749-765 (2005)

Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev: A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover. SIAM J. Comput. 34(5): 1129-1146 (2005)

Oded Regev: On lattices, learning with errors, random linear codes, and cryptography. STOC 2005: 84-93

Irit Dinur, Elchanan Mossel, Oded Regev: Conditional Hardness for Approximate Coloring. CoRR abs/cs/0504062 (2005)

Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf: Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity. CoRR abs/quant-ph/0511013 (2005)

Irit Dinur, Elchanan Mossel, Oded Regev: Conditional Hardness for Approximate Coloring. Electronic Colloquium on Computational Complexity (ECCC)(039) (2005)

József Balogh, Oded Regev, Clifford D. Smyth, William L. Steiger, Mario Szegedy: Long Monotone Paths in Line Arrangements. Discrete & Computational Geometry 32(2): 167-176 (2004)

Oded Regev: New lattice-based cryptographic constructions. J. ACM 51(6): 899-942 (2004)

Oded Regev: Quantum Computation and Lattice Problems. SIAM J. Comput. 33(3): 738-760 (2004)

Oded Regev: Improved Inapproximability of Lattice and Coding Problems With Preprocessing. IEEE Transactions on Information Theory 50(9): 2031-2037 (2004)

Venkatesan Guruswami, Daniele Micciancio, Oded Regev: The Complexity of the Covering Radius Problem on Lattices and Codes. IEEE Conference on Computational Complexity 2004: 161-173

Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev: Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation. FOCS 2004: 42-51

Dorit Aharonov, Oded Regev: Lattice Problems in NP cap coNP. FOCS 2004: 362-371

Daniele Micciancio, Oded Regev: Worst-Case to Average-Case Reductions Based on Gaussian Measures. FOCS 2004: 372-381

Amit Chakrabarti, Oded Regev: An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching. FOCS 2004: 473-482

Julia Kempe, Alexei Kitaev, Oded Regev: The Complexity of the Local Hamiltonian Problem. FSTTCS 2004: 372-383

Julia Kempe, Alexei Kitaev, Oded Regev: The Complexity of the Local Hamiltonian Problem. CoRR quant-ph/0406180 (2004)

Amitai Armon, Yossi Azar, Leah Epstein, Oded Regev: On-line restricted assignment of temporary tasks with unknown durations. Inf. Process. Lett. 85(2): 67-72 (2003)

Julia Kempe, Oded Regev: 3-local Hamitonian is QMA-complete. Quantum Information & Computation 3(3): 258-264 (2003)

Oded Regev: Improved Inapproximability of Lattice and Coding Problems with Preprocessing. IEEE Conference on Computational Complexity 2003: 363-370

Subhash Khot, Oded Regev: Vertex Cover Might be Hard to Approximate to within 2-\varepsilon. IEEE Conference on Computational Complexity 2003: 379-

József Balogh, Oded Regev, Clifford D. Smyth, William L. Steiger, Mario Szegedy: Long monotone paths in line arrangements. Symposium on Computational Geometry 2003: 124-128

Dorit Aharonov, Oded Regev: A Lattice Problem in Quantum NP. FOCS 2003: 210-219

Oded Regev: New lattice based cryptographic constructions. STOC 2003: 407-416

Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev: A new multilayered PCP and the hardness of hypergraph vertex cover. STOC 2003: 595-601

Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev: A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover. CoRR cs.CC/0304026 (2003)

Oded Regev: New Lattice Based Cryptographic Constructions. CoRR cs.CR/0309051 (2003)

Oded Regev: Quantum Computation and Lattice Problems. CoRR cs.DS/0304005 (2003)

Amit Chakrabarti, Oded Regev: An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching. Electronic Colloquium on Computational Complexity (ECCC)(070) (2003)

Oded Regev: Priority algorithms for makespan minimization in the subset model. Inf. Process. Lett. 84(3): 153-157 (2002)

Baruch Awerbuch, Yossi Azar, Stefano Leonardi, Oded Regev: Minimizing the Flow Time Without Migration. SIAM J. Comput. 31(5): 1370-1382 (2002)

Yossi Azar, Oded Regev, Jiri Sgall, Gerhard J. Woeginger: Off-line temporary tasks assignment. Theor. Comput. Sci. 287(2): 419-428 (2002)

Irit Dinur, Oded Regev, Clifford D. Smyth: The Hardness of 3 - Uniform Hypergraph Coloring. FOCS 2002: 33-

Oded Regev: Quantum Computation and Lattice Problems. FOCS 2002: 520-529

Amitai Armon, Yossi Azar, Leah Epstein, Oded Regev: Temporary tasks assignment resolved. SODA 2002: 116-124

Yossi Azar, Oded Regev: On-line bin-stretching. Theor. Comput. Sci. 268(1): 17-41 (2001)

Yossi Azar, Oded Regev: Strongly Polynomial Algorithms for the Unsplittable Flow Problem. IPCO 2001: 15-29

Baruch Awerbuch, Yossi Azar, Oded Regev: Maximizing job benefits on-line. APPROX 2000: 42-50

Yossi Azar, Oded Regev: Off-Line Temporary Tasks Assignment. ESA 1999: 163-171

Baruch Awerbuch, Yossi Azar, Stefano Leonardi, Oded Regev: Minimizing the Flow Time Without Migration. STOC 1999: 198-205

Noam Nisan, Shmulik London, Oded Regev, Noam Camiel: Globally Distributed Computation over the Internet - The POPCORN Project. ICDCS 1998: 592-601

Yossi Azar, Oded Regev: On-Line Bin-Stretching. RANDOM 1998: 71-81

Andrew R. King, Oded Regev: Physics with answers - 500 problems and solutions. Cambridge University Press 1997, isbn 978-0-521-48369-8, pp. I-XI, 1-317