Oded Regev

2009
66	EE	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)
65	EE	Phong Q. Nguyen, Oded Regev: Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures. J. Cryptology 22(2): 139-160 (2009)
2008
64	EE	Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev, David Steurer: Rounding Parallel Repetitions of Unique Games. FOCS 2008: 374-383
63	EE	Julia Kempe, Oded Regev, Ben Toner: Unique Games with Entangled Provers are Easy. FOCS 2008: 457-466
62	EE	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
61	EE	Oded Regev, Liron Schiff: Impossibility of a Quantum Speed-Up with a Faulty Oracle. ICALP (1) 2008: 773-781
60	EE	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
59	EE	Lior Eldar, Oded Regev: Quantum SAT for a Qutrit-Cinquit Pair Is QMA1-Complete. ICALP (1) 2008: 881-892
58	EE	Subhash Khot, Oded Regev: Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci. 74(3): 335-349 (2008)
2007
57	EE	Julia Kempe, Oded Regev, Ben Toner: The Unique Games Conjecture with Entangled Provers is False. Algebraic Methods in Computational Complexity 2007
56	EE	Oded Regev, Ben Toner: Simulating Quantum Correlations with Finite Communication. FOCS 2007: 384-394
55	EE	Ishay Haviv, Oded Regev: Tensor-based hardness of the shortest vector problem to within almost polynomial factors. STOC 2007: 469-477
54	EE	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)
53	EE	Daniele Micciancio, Oded Regev: Worst-Case to Average-Case Reductions Based on Gaussian Measures. SIAM J. Comput. 37(1): 267-302 (2007)
52	EE	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)
2006
51	EE	Oded Regev: Lattice-Based Cryptography. CRYPTO 2006: 131-141
50	EE	Phong Q. Nguyen, Oded Regev: Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures. EUROCRYPT 2006: 271-288
49	EE	Ishay Haviv, Oded Regev: Hardness of the Covering Radius Problem on Lattices. IEEE Conference on Computational Complexity 2006: 145-158
48	EE	Irit Dinur, Elchanan Mossel, Oded Regev: Conditional hardness for approximate coloring. STOC 2006: 344-353
47	EE	Oded Regev, Ricky Rosen: Lattice problems and norm embeddings. STOC 2006: 447-456
46	EE	Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf: Bounded-error quantum state identification and exponential separations in communication complexity. STOC 2006: 594-603
45	EE	Yossi Azar, Oded Regev: Combinatorial Algorithms for the Unsplittable Flow Problem. Algorithmica 44(1): 49-66 (2006)
44	EE	Julia Kempe, Alexei Kitaev, Oded Regev: The Complexity of the Local Hamiltonian Problem. SIAM J. Comput. 35(5): 1070-1097 (2006)
2005
43	EE	Oded Regev: On lattices, learning with errors, random linear codes, and cryptography. STOC 2005: 84-93
42	EE	Irit Dinur, Elchanan Mossel, Oded Regev: Conditional Hardness for Approximate Coloring CoRR abs/cs/0504062: (2005)
41	EE	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)
40	EE	Irit Dinur, Oded Regev, Clifford D. Smyth: The Hardness of 3-Uniform Hypergraph Coloring. Combinatorica 25(5): 519-535 (2005)
39	EE	Venkatesan Guruswami, Daniele Micciancio, Oded Regev: The complexity of the covering radius problem. Computational Complexity 14(2): 90-121 (2005)
38	EE	Irit Dinur, Elchanan Mossel, Oded Regev: Conditional Hardness for Approximate Coloring Electronic Colloquium on Computational Complexity (ECCC)(039): (2005)
37	EE	Dorit Aharonov, Oded Regev: Lattice problems in NP cap coNP. J. ACM 52(5): 749-765 (2005)
36	EE	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)
2004
35	EE	Dorit Aharonov, Oded Regev: Lattice Problems in NP cap coNP. FOCS 2004: 362-371
34	EE	Daniele Micciancio, Oded Regev: Worst-Case to Average-Case Reductions Based on Gaussian Measures. FOCS 2004: 372-381
33	EE	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
32	EE	Amit Chakrabarti, Oded Regev: An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching. FOCS 2004: 473-482
31	EE	Julia Kempe, Alexei Kitaev, Oded Regev: The Complexity of the Local Hamiltonian Problem. FSTTCS 2004: 372-383
30	EE	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
29	EE	Julia Kempe, Alexei Kitaev, Oded Regev: The Complexity of the Local Hamiltonian Problem CoRR quant-ph/0406180: (2004)
28	EE	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)
27		Oded Regev: Improved Inapproximability of Lattice and Coding Problems With Preprocessing. IEEE Transactions on Information Theory 50(9): 2031-2037 (2004)
26	EE	Oded Regev: New lattice-based cryptographic constructions. J. ACM 51(6): 899-942 (2004)
25	EE	Oded Regev: Quantum Computation and Lattice Problems. SIAM J. Comput. 33(3): 738-760 (2004)
2003
24	EE	Dorit Aharonov, Oded Regev: A Lattice Problem in Quantum NP. FOCS 2003: 210-219
23	EE	Oded Regev: Improved Inapproximability of Lattice and Coding Problems with Preprocessing. IEEE Conference on Computational Complexity 2003: 363-370
22	EE	Subhash Khot, Oded Regev: Vertex Cover Might be Hard to Approximate to within 2-\varepsilon. IEEE Conference on Computational Complexity 2003: 379-
21	EE	Oded Regev: New lattice based cryptographic constructions. STOC 2003: 407-416
20	EE	Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev: A new multilayered PCP and the hardness of hypergraph vertex cover. STOC 2003: 595-601
19	EE	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
18	EE	Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev: A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover CoRR cs.CC/0304026: (2003)
17	EE	Oded Regev: New Lattice Based Cryptographic Constructions CoRR cs.CR/0309051: (2003)
16	EE	Oded Regev: Quantum Computation and Lattice Problems CoRR cs.DS/0304005: (2003)
15	EE	Amit Chakrabarti, Oded Regev: An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching Electronic Colloquium on Computational Complexity (ECCC)(070): (2003)
14	EE	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)
2002
13	EE	Irit Dinur, Oded Regev, Clifford D. Smyth: The Hardness of 3 - Uniform Hypergraph Coloring. FOCS 2002: 33-
12	EE	Oded Regev: Quantum Computation and Lattice Problems. FOCS 2002: 520-529
11	EE	Amitai Armon, Yossi Azar, Leah Epstein, Oded Regev: Temporary tasks assignment resolved. SODA 2002: 116-124
10	EE	Oded Regev: Priority algorithms for makespan minimization in the subset model. Inf. Process. Lett. 84(3): 153-157 (2002)
9	EE	Baruch Awerbuch, Yossi Azar, Stefano Leonardi, Oded Regev: Minimizing the Flow Time Without Migration. SIAM J. Comput. 31(5): 1370-1382 (2002)
8		Yossi Azar, Oded Regev, Jiri Sgall, Gerhard J. Woeginger: Off-line temporary tasks assignment. Theor. Comput. Sci. 287(2): 419-428 (2002)
2001
7	EE	Yossi Azar, Oded Regev: Strongly Polynomial Algorithms for the Unsplittable Flow Problem. IPCO 2001: 15-29
6	EE	Yossi Azar, Oded Regev: On-line bin-stretching. Theor. Comput. Sci. 268(1): 17-41 (2001)
2000
5	EE	Baruch Awerbuch, Yossi Azar, Oded Regev: Maximizing job benefits on-line. APPROX 2000: 42-50
1999
4	EE	Yossi Azar, Oded Regev: Off-Line Temporary Tasks Assignment. ESA 1999: 163-171
3	EE	Baruch Awerbuch, Yossi Azar, Stefano Leonardi, Oded Regev: Minimizing the Flow Time Without Migration. STOC 1999: 198-205
1998
2	EE	Noam Nisan, Shmulik London, Oded Regev, Noam Camiel: Globally Distributed Computation over the Internet - The POPCORN Project. ICDCS 1998: 592-601
1	EE	Yossi Azar, Oded Regev: On-Line Bin-Stretching. RANDOM 1998: 71-81

Coauthor Index

1	Dorit Aharonov	[24] [33] [35] [37] [54]
2	Amitai Armon	[11] [14]
3	Baruch Awerbuch	[3] [5] [9]
4	Yossi Azar	[1] [3] [4] [5] [6] [7] [8] [9] [11] [14] [45]
5	József Balogh	[19] [28]
6	Boaz Barak	[64]
7	Avraham Ben-Aroya	[62]
8	Noam Camiel	[2]
9	Amit Chakrabarti	[15] [32]
10	Wim van Dam	[33] [54]
11	Irit Dinur	[13] [18] [20] [36] [38] [40] [42] [48]
12	Lior Eldar	[59]
13	Leah Epstein	[11] [14]
14	Dmitry Gavinsky	[41] [46]
15	Venkatesan Guruswami	[18] [20] [30] [36] [39]
16	Moritz Hardt	[64]
17	Ishay Haviv	[49] [52] [55] [64] [66]
18	Julia Kempe	[29] [31] [33] [41] [44] [46] [54] [57] [60] [63]
19	Subhash Khot	[18] [20] [22] [36] [58]
20	Alexei Kitaev	[29] [31] [44]
21	Zeph Landau	[33] [54]
22	Stefano Leonardi	[3] [9]
23	Seth Lloyd	[33] [54]
24	Shmulik London	[2]
25	Vadim Lyubashevsky	[66]
26	Daniele Micciancio	[30] [34] [39] [53]
27	Elchanan Mossel	[38] [42] [48]
28	Phong Q. Nguyen	[50] [65]
29	Noam Nisan	[2]
30	Anup Rao	[64]
31	Ricky Rosen	[47]
32	Liron Schiff	[61]
33	Jiri Sgall	[8]
34	Clifford D. Smyth	[13] [19] [28] [40]
35	William L. Steiger	[19] [28]
36	David Steurer	[64]
37	Mario Szegedy	[19] [28]
38	Amnon Ta-Shma	[52]
39	Ben Toner	[56] [57] [63]
40	Falk Unger	[60]
41	Gerhard J. Woeginger	[8]
42	Ronald de Wolf	[41] [46] [60] [62]

Colors in the list of coauthors