×

zbMATH — the first resource for mathematics

Regev, Oded

Compute Distance To:
Author ID: regev.oded Recent zbMATH articles by "Regev, Oded"
Published as: Regev, Oded; Regev, O.
Documents Indexed: 112 Publications since 1982, including 2 Books
all top 5

Co-Authors

14 single-authored
12 Haviv, Ishay
11 Azar, Yossi
10 Kempe, Julia
8 de Wolf, Ronald Michiel
6 Dinur, Irit
6 Peikert, Chris
6 Umurhan, Orkan M.
6 Vidick, Thomas
5 Naor, Assaf
4 Awerbuch, Baruch
4 Chakrabarti, Amit
4 Lyubashevsky, Vadim
4 Stephens-Davidowitz, Noah
3 Aharonov, Dorit
3 Armon, Amitai
3 Epstein, Leah
3 Gavinsky, Dmitry
3 Guruswami, Venkatesan
3 Khot, Subhash Ajit
3 Micciancio, Daniele
3 Mossel, Elchanan
3 Nguyen, Phong Q.
3 Smyth, Clifford
2 Aggarwal, Divesh
2 Briët, Jop
2 Buchler, J. Robert
2 Friedgut, Ehud
2 Golovnev, Alexander
2 Kitaev, Alexei Yu.
2 Landau, Zeph A.
2 Leonardi, Stefano
2 Lloyd, Seth
2 O’Donnell, Ryan
2 Steiger, William L.
2 Szegedy, Mario
2 Toner, Ben
2 Unger, Falk
2 van Dam, Wim
2 Weinstein, Omri
1 Ambainis, Andris
1 Balogh, Jazsef
1 Balogh, József
1 Barak, Boaz
1 Belovs, Aleksandrs
1 Brakerski, Zvika
1 Brody, Joshua E.
1 Buhrman, Harry
1 Cramer, Ronald John Fitzgerald
1 Dadush, Daniel
1 Ducas, Léo
1 Eldar, Lior
1 Elphick, Christian
1 Gama, Nicolas
1 Klartag, Bo’az
1 Kluzniak, Włodek
1 Lovett, Shachar
1 Moitra, Ankur
1 Nemirovski, Arkadi S.
1 Raghavendra, Prasad
1 Rao, Shravas K.
1 Raz, Ran
1 Rebusco, Paola
1 Rosen, Ricky
1 Roux-Langlois, Adeline
1 Saket, Rishi
1 Scarpa, Giannicola
1 Schiff, Liron
1 Sgall, Jiří
1 Shapira, Uri
1 Shinkar, Igor
1 Spiegel, Edward A.
1 Stehlé, Damien
1 Steif, Jeffrey E.
1 Sternberg, Alexander
1 Steurer, David
1 Sudakov, Benny
1 Ta-Shma, Amnon
1 Tauman Kalai, Yael
1 Trevisan, Luca
1 Vijayaraghavan, Aravindan
1 Weiss, Barak
1 Witmer, David
1 Woeginger, Gerhard Johannes
1 Yecko, Philip A.

Publications by Year

Citations contained in zbMATH Open

90 Publications have been cited 1,494 times in 955 Documents Cited by Year
On lattices, learning with errors, random linear codes, and cryptography. Zbl 1192.94106
Regev, Oded
205
2005
Vertex cover might be hard to approximate to within \(2 - \varepsilon \). Zbl 1133.68061
Khot, Subhash; Regev, Oded
147
2008
On lattices, learning with errors, random linear codes, and cryptography. Zbl 1325.68101
Regev, Oded
135
2009
Worst-case to average-case reductions based on Gaussian measures. Zbl 1142.68037
Micciancio, Daniele; Regev, Oded
78
2007
On ideal lattices and learning with errors over rings. Zbl 1279.94099
Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded
75
2010
Classical hardness of learning with errors. Zbl 1293.68159
Brakerski, Zvika; Langlois, Adeline; Peikert, Chris; Regev, Oded; Stehlé, Damien
60
2013
New lattice-based cryptographic constructions. Zbl 1125.94026
Regev, Oded
59
2004
Lattice-based cryptography. Zbl 1161.81324
Micciancio, Daniele; Regev, Oded
47
2009
The complexity of the local Hamiltonian problem. Zbl 1102.81032
Kempe, Julia; Kitaev, Alexei; Regev, Oded
46
2006
Adiabatic quantum computation is equivalent to standard quantum computation. Zbl 1134.81009
Aharonov, Dorit; Van Dam, Wim; Kempe, Julia; Landau, Zeph; Lloyd, Seth; Regev, Oded
42
2007
A new multilayered PCP and the hardness of hypergraph vertex cover. Zbl 1079.68039
Dinur, Irit; Guruswami, Venkatesan; Khot, Subhash; Regev, Oded
36
2005
On-line bin-stretching. Zbl 0984.68195
Azar, Y.; Regev, O.
33
2001
A toolkit for ring-LWE cryptography. Zbl 1300.94082
Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded
27
2013
Lattice enumeration using extreme pruning. Zbl 1280.94056
Gama, Nicolas; Nguyen, Phong Q.; Regev, Oded
25
2010
On ideal lattices and learning with errors over rings. Zbl 1281.68140
Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded
23
2013
Lattice problems in NP \(\cap\) coNP. Zbl 1286.68218
Aharonov, Dorit; Regev, Oded
17
2005
The hardness of 3-uniform hypergraph coloring. Zbl 1106.68080
Dinur, Irit; Regev, Oded; Smyth, Clifford
17
2005
Adiabatic quantum computation is equivalent to standard quantum computation. Zbl 1152.81008
Aharonov, Dorit; van Dam, Wim; Kempe, Julia; Landau, Zeph; Lloyd, Seth; Regev, Oded
16
2008
Lattice-based cryptography. Zbl 1161.94425
Regev, Oded
15
2006
Conditional hardness for approximate coloring. Zbl 1192.68317
Dinur, Irit; Mossel, Elchanan; Regev, Oded
15
2009
Near-optimal and explicit Bell inequality violations. Zbl 1298.81034
Buhrman, Harry; Regev, Oded; Scarpa, Giannicola; de Wolf, Ronald
15
2012
Unique games with entangled provers are easy. Zbl 1244.68040
Kempe, Julia; Regev, Oded; Toner, Ben
13
2010
Quantum computation and lattice problems. Zbl 1057.81012
Regev, Oded
13
2004
Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality. Zbl 1140.60007
Mossel, Elchanan; O’Donnell, Ryan; Regev, Oded; Steif, Jeffrey E.; Sudakov, Benny
13
2006
Recovering short generators of principal ideals in cyclotomic rings. Zbl 1371.94630
Cramer, Ronald; Ducas, Léo; Peikert, Chris; Regev, Oded
13
2016
An optimal lower bound on the communication complexity of gap-Hamming-distance. Zbl 1259.68087
Chakrabarti, Amit; Regev, Oded
12
2012
The complexity of the covering radius problem. Zbl 1085.68063
Guruswami, Venkatesan; Micciancio, Daniele; Regev, Oded
11
2005
A new multilayered {PCP} and the hardness of hypergraph vertex cover. Zbl 1192.68290
Dinur, Irit; Guruswami, Venkatesan; Khot, Subhash; Regev, Oded
11
2003
An optimal lower bound on the communication complexity of gap-Hamming-distance. Zbl 1288.90005
Chakrabarti, Amit; Regev, Oded
11
2011
Independent sets in graph powers are almost contained in juntas. Zbl 1147.05058
Dinur, Irit; Friedgut, Ehud; Regev, Oded
10
2008
Quantum one-way communication can be exponentially stronger than classical communication. Zbl 1288.68074
Regev, Oded; Klartag, Bo’az
10
2011
Conditional hardness for approximate coloring. Zbl 1301.68143
Dinur, Irit; Mossel, Elchanan; Regev, Oded
10
2006
Bell violations through independent bases games. Zbl 1268.81038
Regev, Oded
10
2012
Priority algorithms for makespan minimization in the subset model. Zbl 1042.68019
Regev, Oded
9
2002
Solving the shortest vector problem in \(2^n\) time using discrete Gaussian sampling (extended abstract). Zbl 1321.68426
Aggarwal, Divesh; Dadush, Daniel; Regev, Oded; Stephens-Davidowitz, Noah
9
2015
Minimizing the flow time without migration. Zbl 1345.68025
Awerbuch, Baruch; Azar, Yossi; Leonardi, Stefano; Regev, Oded
9
1999
Strongly polynomial algorithms for the unsplittable flow problem. Zbl 1010.90521
Azar, Yossi; Regev, Oded
8
2001
Simulating quantum correlations with finite communication. Zbl 1205.68181
Regev, Oded; Toner, Ben
8
2009
Lattice problems and norm embeddings. Zbl 1301.68151
Regev, Oded; Rosen, Ricky
8
2006
The restricted isometry property of subsampled Fourier matrices. Zbl 1439.94011
Haviv, Ishay; Regev, Oded
8
2016
Tensor-based hardness of the shortest vector problem to within almost polynomial factors. Zbl 1232.68066
Haviv, Ishay; Regev, Oded
7
2007
Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures. Zbl 1159.94369
Nguyen, Phong Q.; Regev, Oded
7
2009
Efficient rounding for the noncommutative Grothendieck inequality. Zbl 1293.68151
Naor, Assaf; Regev, Oded; Vidick, Thomas
7
2013
Learning a parallelepiped: cryptanalysis of GGH and NTRU signatures. Zbl 1140.94365
Nguyen, Phong Q.; Regev, Oded
6
2006
Impossibility of a quantum speed-up with a faulty oracle. Zbl 1153.68365
Regev, Oded; Schiff, Liron
6
2008
New lattice based cryptographic constructions. Zbl 1192.94105
Regev, Oded
6
2003
The restricted isometry property of subsampled Fourier matrices. Zbl 1379.46014
Haviv, Ishay; Regev, Oded
6
2017
Tight hardness of the non-commutative Grothendieck problem. Zbl 1387.68122
Briët, Jop; Regev, Oded; Saket, Rishi
6
2017
Tensor-based hardness of the shortest vector problem to within almost polynomial factors. Zbl 1253.68152
Haviv, Ishay; Regev, Oded
6
2012
Minimizing the flow time without migration. Zbl 1051.68072
Awerbuch, Baruch; Azar, Yossi; Leonardi, Stefano; Regev, Oded
5
2002
Combinatorial algorithms for the unsplittable flow problem. Zbl 1092.68116
Azar, Yossi; Regev, Oded
5
2006
3-local Hamiltonian is QMA-complete. Zbl 1152.81749
Kempe, J.; Regev, O.
5
2003
An inequality for Gaussians on lattices. Zbl 1395.11105
Regev, Oded; Stephens-Davidowitz, Noah
5
2017
Entropy-based bounds on dimension reduction in \(L^1\). Zbl 1311.68176
Regev, Oded
5
2013
Quantum XOR games. Zbl 1348.81177
Regev, Oded; Vidick, Thomas
5
2015
Pseudorandomness of ring-LWE for any ring and modulus. Zbl 1370.94536
Peikert, Chris; Regev, Oded; Stephens-Davidowitz, Noah
5
2017
Long monotone paths in line arrangements. Zbl 1065.52016
Balogh, József; Regev, Oded; Smyth, Clifford; Steiger, William; Szegedy, Mario
4
2004
Hydrodynamic stability of rotationally supported flows: linear and nonlinear 2D shearing box results. Zbl 1070.85003
Umurhan, O. M.; Regev, O.
4
2004
On the complexity of lattice problems with polynomial approximation factors. Zbl 1237.68102
Regev, Oded
4
2010
Hardness of the covering radius problem on lattices. Zbl 1286.68192
Haviv, Ishay; Regev, Oded
4
2012
Elementary proofs of Grothendieck theorems for completely bounded norms. Zbl 1349.46062
Regev, Oded; Vidick, Thomas
4
2014
The minrank of random graphs. Zbl 1432.05095
Golovnev, Alexander; Regev, Oded; Weinstein, Omri
4
2018
Locally decodable codes and the failure of cotype for projective tensor products. Zbl 1262.46008
Briët, Jop; Naor, Assaf; Regev, Oded
4
2012
A note on the distribution of the distance from a lattice. Zbl 1163.68040
Haviv, Ishay; Lyubashevsky, Vadim; Regev, Oded
3
2009
Better gap-Hamming lower bounds via better round elimination. Zbl 1305.68091
Brody, Joshua; Chakrabarti, Amit; Regev, Oded; Vidick, Thomas; de Wolf, Ronald
3
2010
Learning with errors over rings. (Abstract). Zbl 1231.94055
Regev, Oded
3
2010
The Euclidean distortion of flat tori. Zbl 1279.46014
Haviv, Ishay; Regev, Oded
3
2013
Temporary tasks assignment resolved. Zbl 1093.68546
Armon, Amitai; Azar, Yossi; Epstein, Leah; Regev, Oded
2
2002
Hydrodynamic response of rotationally supported flows in the small shearing box model. Zbl 1147.85002
Sternberg, A.; Umurhan, O. M.; Gil, Y.; Regev, O.
2
2008
Improved inapproximability of lattice and coding problems with preprocessing. Zbl 1315.94036
Regev, Oded
2
2004
On the hardness of satisfiability with bounded occurrences in the polynomial-time hierarchy. Zbl 1213.68311
Haviv, Ishay; Regev, Oded; Ta-Shma, Amnon
2
2007
A counterexample to monotonicity of relative mass in random walks. Zbl 1343.60054
Regev, Oded; Shinkar, Igor
2
2016
Counterexamples to a conjecture of Woods. Zbl 1380.11086
Regev, Oded; Shapira, Uri; Weiss, Barak
2
2017
Simultaneous communication protocols with quantum and classical messages. Zbl 1286.68019
Gavinsky, Dmitry; Regev, Oded; de Wolf, Ronald
2
2008
A note on discrete Gaussian combinations of lattice vectors. Zbl 1375.60062
Aggarwal, Divesh; Regev, Oded
2
2016
Kneser graphs are like Swiss cheese. Zbl 1404.05088
Friedgut, Ehud; Regev, Oded
2
2018
Beating the random assignment on constraint satisfaction problems of bounded degree. Zbl 1375.68102
Barak, Boaz; Moitra, Ankur; O’donnell, Ryan; Raghavendra, Prasad; Regev, Oded; Steurer, David; Trevisan, Luca; Vijayaraghavan, Aravindan; Witmer, David; Wright, John
2
2015
Complexity from thermal instability. Zbl 0719.76030
Elphick, Christian; Regev, Oded; Spiegel, E. A.
1
1991
Off-line temporary tasks assignment. Zbl 1061.90043
Azar, Yossi; Regev, Oded; Sgall, Jiří; Woeginger, Gerhard J.
1
2002
On the viability of the shearing box approximation for numerical studies of MHD turbulence in accretion disks. Zbl 1140.85314
Regev, O.; Umurhan, O. M.
1
2008
Global axisymmetric dynamics of thin viscous accretion disks. Zbl 1179.85016
Umurhan, O. M.; Nemirovsky, A.; Regev, O.; Shaviv, G.
1
2006
An optimal randomized cell probe lower bound for approximate nearest neighbor searching. Zbl 1207.68156
Chakrabarti, Amit; Regev, Oded
1
2010
Upper bounds on the noise threshold for fault-tolerant quantum computing. Zbl 1153.81467
Kempe, Julia; Regev, Oded; Unger, Falk; de Wolf, Ronald
1
2008
Quantum SAT for a qutrit-cinquit pair is QMA\(_{1}\)-complete. Zbl 1153.81465
Eldar, Lior; Regev, Oded
1
2008
The list-decoding size of Fourier-sparse Boolean functions. Zbl 1378.94082
Haviv, Ishay; Regev, Oded
1
2015
Modern fluid dynamics for physics and astrophysics. Zbl 1339.76004
Regev, Oded; Umurhan, Orkan M.; Yecko, Philip A.
1
2016
Efficient rounding for the noncommutative Grothendieck inequality. Zbl 1302.68323
Naor, Assaf; Regev, Oded; Vidick, Thomas
1
2014
A reverse Minkowski theorem. Zbl 1370.11073
Regev, Oded; Stephens-Davidowitz, Noah
1
2017
Efficient quantum algorithms for (gapped) group testing and junta testing. Zbl 1410.68132
Ambainis, Andris; Belovs, Aleksandrs; Regev, Oded; de Wolf, Ronald
1
2016
On the lattice isomorphism problem. Zbl 1421.68085
Haviv, Ishay; Regev, Oded
1
2014
The minrank of random graphs. Zbl 1432.05095
Golovnev, Alexander; Regev, Oded; Weinstein, Omri
4
2018
Kneser graphs are like Swiss cheese. Zbl 1404.05088
Friedgut, Ehud; Regev, Oded
2
2018
The restricted isometry property of subsampled Fourier matrices. Zbl 1379.46014
Haviv, Ishay; Regev, Oded
6
2017
Tight hardness of the non-commutative Grothendieck problem. Zbl 1387.68122
Briët, Jop; Regev, Oded; Saket, Rishi
6
2017
An inequality for Gaussians on lattices. Zbl 1395.11105
Regev, Oded; Stephens-Davidowitz, Noah
5
2017
Pseudorandomness of ring-LWE for any ring and modulus. Zbl 1370.94536
Peikert, Chris; Regev, Oded; Stephens-Davidowitz, Noah
5
2017
Counterexamples to a conjecture of Woods. Zbl 1380.11086
Regev, Oded; Shapira, Uri; Weiss, Barak
2
2017
A reverse Minkowski theorem. Zbl 1370.11073
Regev, Oded; Stephens-Davidowitz, Noah
1
2017
Recovering short generators of principal ideals in cyclotomic rings. Zbl 1371.94630
Cramer, Ronald; Ducas, Léo; Peikert, Chris; Regev, Oded
13
2016
The restricted isometry property of subsampled Fourier matrices. Zbl 1439.94011
Haviv, Ishay; Regev, Oded
8
2016
A counterexample to monotonicity of relative mass in random walks. Zbl 1343.60054
Regev, Oded; Shinkar, Igor
2
2016
A note on discrete Gaussian combinations of lattice vectors. Zbl 1375.60062
Aggarwal, Divesh; Regev, Oded
2
2016
Modern fluid dynamics for physics and astrophysics. Zbl 1339.76004
Regev, Oded; Umurhan, Orkan M.; Yecko, Philip A.
1
2016
Efficient quantum algorithms for (gapped) group testing and junta testing. Zbl 1410.68132
Ambainis, Andris; Belovs, Aleksandrs; Regev, Oded; de Wolf, Ronald
1
2016
Solving the shortest vector problem in \(2^n\) time using discrete Gaussian sampling (extended abstract). Zbl 1321.68426
Aggarwal, Divesh; Dadush, Daniel; Regev, Oded; Stephens-Davidowitz, Noah
9
2015
Quantum XOR games. Zbl 1348.81177
Regev, Oded; Vidick, Thomas
5
2015
Beating the random assignment on constraint satisfaction problems of bounded degree. Zbl 1375.68102
Barak, Boaz; Moitra, Ankur; O’donnell, Ryan; Raghavendra, Prasad; Regev, Oded; Steurer, David; Trevisan, Luca; Vijayaraghavan, Aravindan; Witmer, David; Wright, John
2
2015
The list-decoding size of Fourier-sparse Boolean functions. Zbl 1378.94082
Haviv, Ishay; Regev, Oded
1
2015
Elementary proofs of Grothendieck theorems for completely bounded norms. Zbl 1349.46062
Regev, Oded; Vidick, Thomas
4
2014
Efficient rounding for the noncommutative Grothendieck inequality. Zbl 1302.68323
Naor, Assaf; Regev, Oded; Vidick, Thomas
1
2014
On the lattice isomorphism problem. Zbl 1421.68085
Haviv, Ishay; Regev, Oded
1
2014
Classical hardness of learning with errors. Zbl 1293.68159
Brakerski, Zvika; Langlois, Adeline; Peikert, Chris; Regev, Oded; Stehlé, Damien
60
2013
A toolkit for ring-LWE cryptography. Zbl 1300.94082
Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded
27
2013
On ideal lattices and learning with errors over rings. Zbl 1281.68140
Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded
23
2013
Efficient rounding for the noncommutative Grothendieck inequality. Zbl 1293.68151
Naor, Assaf; Regev, Oded; Vidick, Thomas
7
2013
Entropy-based bounds on dimension reduction in \(L^1\). Zbl 1311.68176
Regev, Oded
5
2013
The Euclidean distortion of flat tori. Zbl 1279.46014
Haviv, Ishay; Regev, Oded
3
2013
Near-optimal and explicit Bell inequality violations. Zbl 1298.81034
Buhrman, Harry; Regev, Oded; Scarpa, Giannicola; de Wolf, Ronald
15
2012
An optimal lower bound on the communication complexity of gap-Hamming-distance. Zbl 1259.68087
Chakrabarti, Amit; Regev, Oded
12
2012
Bell violations through independent bases games. Zbl 1268.81038
Regev, Oded
10
2012
Tensor-based hardness of the shortest vector problem to within almost polynomial factors. Zbl 1253.68152
Haviv, Ishay; Regev, Oded
6
2012
Hardness of the covering radius problem on lattices. Zbl 1286.68192
Haviv, Ishay; Regev, Oded
4
2012
Locally decodable codes and the failure of cotype for projective tensor products. Zbl 1262.46008
Briët, Jop; Naor, Assaf; Regev, Oded
4
2012
An optimal lower bound on the communication complexity of gap-Hamming-distance. Zbl 1288.90005
Chakrabarti, Amit; Regev, Oded
11
2011
Quantum one-way communication can be exponentially stronger than classical communication. Zbl 1288.68074
Regev, Oded; Klartag, Bo’az
10
2011
On ideal lattices and learning with errors over rings. Zbl 1279.94099
Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded
75
2010
Lattice enumeration using extreme pruning. Zbl 1280.94056
Gama, Nicolas; Nguyen, Phong Q.; Regev, Oded
25
2010
Unique games with entangled provers are easy. Zbl 1244.68040
Kempe, Julia; Regev, Oded; Toner, Ben
13
2010
On the complexity of lattice problems with polynomial approximation factors. Zbl 1237.68102
Regev, Oded
4
2010
Better gap-Hamming lower bounds via better round elimination. Zbl 1305.68091
Brody, Joshua; Chakrabarti, Amit; Regev, Oded; Vidick, Thomas; de Wolf, Ronald
3
2010
Learning with errors over rings. (Abstract). Zbl 1231.94055
Regev, Oded
3
2010
An optimal randomized cell probe lower bound for approximate nearest neighbor searching. Zbl 1207.68156
Chakrabarti, Amit; Regev, Oded
1
2010
On lattices, learning with errors, random linear codes, and cryptography. Zbl 1325.68101
Regev, Oded
135
2009
Lattice-based cryptography. Zbl 1161.81324
Micciancio, Daniele; Regev, Oded
47
2009
Conditional hardness for approximate coloring. Zbl 1192.68317
Dinur, Irit; Mossel, Elchanan; Regev, Oded
15
2009
Simulating quantum correlations with finite communication. Zbl 1205.68181
Regev, Oded; Toner, Ben
8
2009
Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures. Zbl 1159.94369
Nguyen, Phong Q.; Regev, Oded
7
2009
A note on the distribution of the distance from a lattice. Zbl 1163.68040
Haviv, Ishay; Lyubashevsky, Vadim; Regev, Oded
3
2009
Vertex cover might be hard to approximate to within \(2 - \varepsilon \). Zbl 1133.68061
Khot, Subhash; Regev, Oded
147
2008
Adiabatic quantum computation is equivalent to standard quantum computation. Zbl 1152.81008
Aharonov, Dorit; van Dam, Wim; Kempe, Julia; Landau, Zeph; Lloyd, Seth; Regev, Oded
16
2008
Independent sets in graph powers are almost contained in juntas. Zbl 1147.05058
Dinur, Irit; Friedgut, Ehud; Regev, Oded
10
2008
Impossibility of a quantum speed-up with a faulty oracle. Zbl 1153.68365
Regev, Oded; Schiff, Liron
6
2008
Hydrodynamic response of rotationally supported flows in the small shearing box model. Zbl 1147.85002
Sternberg, A.; Umurhan, O. M.; Gil, Y.; Regev, O.
2
2008
Simultaneous communication protocols with quantum and classical messages. Zbl 1286.68019
Gavinsky, Dmitry; Regev, Oded; de Wolf, Ronald
2
2008
On the viability of the shearing box approximation for numerical studies of MHD turbulence in accretion disks. Zbl 1140.85314
Regev, O.; Umurhan, O. M.
1
2008
Upper bounds on the noise threshold for fault-tolerant quantum computing. Zbl 1153.81467
Kempe, Julia; Regev, Oded; Unger, Falk; de Wolf, Ronald
1
2008
Quantum SAT for a qutrit-cinquit pair is QMA\(_{1}\)-complete. Zbl 1153.81465
Eldar, Lior; Regev, Oded
1
2008
Worst-case to average-case reductions based on Gaussian measures. Zbl 1142.68037
Micciancio, Daniele; Regev, Oded
78
2007
Adiabatic quantum computation is equivalent to standard quantum computation. Zbl 1134.81009
Aharonov, Dorit; Van Dam, Wim; Kempe, Julia; Landau, Zeph; Lloyd, Seth; Regev, Oded
42
2007
Tensor-based hardness of the shortest vector problem to within almost polynomial factors. Zbl 1232.68066
Haviv, Ishay; Regev, Oded
7
2007
On the hardness of satisfiability with bounded occurrences in the polynomial-time hierarchy. Zbl 1213.68311
Haviv, Ishay; Regev, Oded; Ta-Shma, Amnon
2
2007
The complexity of the local Hamiltonian problem. Zbl 1102.81032
Kempe, Julia; Kitaev, Alexei; Regev, Oded
46
2006
Lattice-based cryptography. Zbl 1161.94425
Regev, Oded
15
2006
Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality. Zbl 1140.60007
Mossel, Elchanan; O’Donnell, Ryan; Regev, Oded; Steif, Jeffrey E.; Sudakov, Benny
13
2006
Conditional hardness for approximate coloring. Zbl 1301.68143
Dinur, Irit; Mossel, Elchanan; Regev, Oded
10
2006
Lattice problems and norm embeddings. Zbl 1301.68151
Regev, Oded; Rosen, Ricky
8
2006
Learning a parallelepiped: cryptanalysis of GGH and NTRU signatures. Zbl 1140.94365
Nguyen, Phong Q.; Regev, Oded
6
2006
Combinatorial algorithms for the unsplittable flow problem. Zbl 1092.68116
Azar, Yossi; Regev, Oded
5
2006
Global axisymmetric dynamics of thin viscous accretion disks. Zbl 1179.85016
Umurhan, O. M.; Nemirovsky, A.; Regev, O.; Shaviv, G.
1
2006
On lattices, learning with errors, random linear codes, and cryptography. Zbl 1192.94106
Regev, Oded
205
2005
A new multilayered PCP and the hardness of hypergraph vertex cover. Zbl 1079.68039
Dinur, Irit; Guruswami, Venkatesan; Khot, Subhash; Regev, Oded
36
2005
Lattice problems in NP \(\cap\) coNP. Zbl 1286.68218
Aharonov, Dorit; Regev, Oded
17
2005
The hardness of 3-uniform hypergraph coloring. Zbl 1106.68080
Dinur, Irit; Regev, Oded; Smyth, Clifford
17
2005
The complexity of the covering radius problem. Zbl 1085.68063
Guruswami, Venkatesan; Micciancio, Daniele; Regev, Oded
11
2005
New lattice-based cryptographic constructions. Zbl 1125.94026
Regev, Oded
59
2004
Quantum computation and lattice problems. Zbl 1057.81012
Regev, Oded
13
2004
Long monotone paths in line arrangements. Zbl 1065.52016
Balogh, József; Regev, Oded; Smyth, Clifford; Steiger, William; Szegedy, Mario
4
2004
Hydrodynamic stability of rotationally supported flows: linear and nonlinear 2D shearing box results. Zbl 1070.85003
Umurhan, O. M.; Regev, O.
4
2004
Improved inapproximability of lattice and coding problems with preprocessing. Zbl 1315.94036
Regev, Oded
2
2004
A new multilayered {PCP} and the hardness of hypergraph vertex cover. Zbl 1192.68290
Dinur, Irit; Guruswami, Venkatesan; Khot, Subhash; Regev, Oded
11
2003
New lattice based cryptographic constructions. Zbl 1192.94105
Regev, Oded
6
2003
3-local Hamiltonian is QMA-complete. Zbl 1152.81749
Kempe, J.; Regev, O.
5
2003
Priority algorithms for makespan minimization in the subset model. Zbl 1042.68019
Regev, Oded
9
2002
Minimizing the flow time without migration. Zbl 1051.68072
Awerbuch, Baruch; Azar, Yossi; Leonardi, Stefano; Regev, Oded
5
2002
Temporary tasks assignment resolved. Zbl 1093.68546
Armon, Amitai; Azar, Yossi; Epstein, Leah; Regev, Oded
2
2002
Off-line temporary tasks assignment. Zbl 1061.90043
Azar, Yossi; Regev, Oded; Sgall, Jiří; Woeginger, Gerhard J.
1
2002
On-line bin-stretching. Zbl 0984.68195
Azar, Y.; Regev, O.
33
2001
Strongly polynomial algorithms for the unsplittable flow problem. Zbl 1010.90521
Azar, Yossi; Regev, Oded
8
2001
Minimizing the flow time without migration. Zbl 1345.68025
Awerbuch, Baruch; Azar, Yossi; Leonardi, Stefano; Regev, Oded
9
1999
Complexity from thermal instability. Zbl 0719.76030
Elphick, Christian; Regev, Oded; Spiegel, E. A.
1
1991
all top 5

Cited by 1,736 Authors

12 Guruswami, Venkatesan
12 Regev, Oded
10 Epstein, Leah
10 Lu, Songfeng
10 Mossel, Elchanan
10 Sun, Jie
9 Chandrasekaran, Karthekeyan
9 Palazuelos, Carlos
9 Stehlé, Damien
8 Haviv, Ishay
8 Khot, Subhash Ajit
8 Libert, Benoît
8 Peikert, Chris
8 Tan, Zhiyi
8 Vaikuntanathan, Vinod
8 Wang, Huaxiong
8 Yasuda, Masaya
7 Brakerski, Zvika
7 Fouque, Pierre-Alain
7 Lyubashevsky, Vadim
7 Naor, Assaf
7 Nguyen, Khoa
7 Vidick, Thomas
6 Dósa, György
6 Escoffier, Bruno
6 He, Yong
6 Junge, Marius
6 Ling, San
6 Liu, Fang
6 Ma, Chunguang
6 Waters, Brent
5 Azar, Yossi
5 Bitansky, Nir
5 Borodin, Allan B.
5 Braverman, Mark
5 El Ouali, Mourad
5 Feldman, Vitaly
5 Gama, Nicolas
5 Grigorescu, Elena
5 Hu, Yupu
5 Karpinski, Marek
5 Koppula, Venkata
5 Kotov, Vladimir M.
5 Lindner, Richard
5 Perret, Ludovic
5 Schmied, Richard
5 Srivastav, Anand
5 Vercauteren, Frederik
5 Viehmann, Claus
4 Albrecht, Martin R.
4 Bai, Shi
4 Bansal, Nikhil
4 Boyar, Joan F.
4 Briët, Jop
4 Buchbinder, Niv
4 Buchmann, Johannes A.
4 Cash, David M.
4 Castryck, Wouter
4 Cseh, Ágnes
4 Ducas, Léo
4 Faugère, Jean-Charles
4 Feige, Uriel
4 Fernau, Henning
4 Fiorini, Samuel
4 Galbraith, Steven D.
4 Gandikota, Venkata
4 Goldwasser, Shafi
4 Goyal, Rishab
4 Halevi, Shai
4 Harrow, Aram Wettroth
4 Herold, Gottfried
4 Ishai, Yuval
4 Ivanyos, Gábor
4 Kao, Mong-Jen
4 Kellerer, Johann
4 Kirchner, Paul
4 Koshiba, Takeshi
4 Larsen, Kim Skak
4 Lee, Euiwoong
4 Li, Jiamei
4 Manlove, David F.
4 Masny, Daniel
4 May, Alexander
4 Montanaro, Ashley
4 Mouhartem, Fabrice
4 Nagaj, Daniel
4 Papageorgiou, Anargyros
4 Rawitz, Dror
4 Rosen, Alon
4 Saket, Rishi
4 Santha, Miklos
4 Saurabh, Saket
4 Schneider, Michael
4 Sikora, Jamie
4 Singer, Amit
4 Steinfeld, Ron
4 Takayasu, Atsushi
4 Tian, Chengliang
4 Tuza, Zsolt
4 van Stee, Rob
...and 1,636 more Authors
all top 5

Cited in 173 Serials

69 Theoretical Computer Science
39 Algorithmica
30 Designs, Codes and Cryptography
27 SIAM Journal on Computing
27 Journal of Cryptology
25 Quantum Information Processing
17 Journal of Mathematical Cryptology
16 Information Processing Letters
15 Discrete Applied Mathematics
14 Journal of Computer and System Sciences
14 Journal of Combinatorial Optimization
14 New Journal of Physics
13 Communications in Mathematical Physics
13 SIAM Journal on Discrete Mathematics
12 Journal of Mathematical Physics
11 Theory of Computing Systems
10 Computational Complexity
9 Operations Research Letters
9 Journal of Scheduling
9 International Journal of Quantum Information
8 Random Structures & Algorithms
7 Israel Journal of Mathematics
7 Information Sciences
7 Information and Computation
7 Journal of Discrete Algorithms
6 International Journal of Theoretical Physics
6 International Journal of Foundations of Computer Science
6 Mathematical Problems in Engineering
6 Advances in Mathematics of Communications
5 Discrete & Computational Geometry
5 Mathematical Programming. Series A. Series B
5 Theory of Computing
5 SIAM Journal on Applied Algebra and Geometry
4 Mathematics of Operations Research
4 Computational Geometry
4 Combinatorics, Probability and Computing
4 Discrete Optimization
3 Discrete Mathematics
3 Mathematics of Computation
3 Computing
3 Journal of Combinatorial Theory. Series A
3 Combinatorica
3 Probability Theory and Related Fields
3 Journal of Complexity
3 SIAM Journal on Optimization
3 Open Systems & Information Dynamics
3 Chicago Journal of Theoretical Computer Science
3 Journal of the ACM
3 LMS Journal of Computation and Mathematics
3 Optimization Letters
3 Cryptography and Communications
3 Science China. Information Sciences
3 ACM Transactions on Computation Theory
2 Bulletin of the Australian Mathematical Society
2 Computers & Mathematics with Applications
2 Journal of Fluid Mechanics
2 Journal of Statistical Physics
2 Reports on Mathematical Physics
2 Reviews of Modern Physics
2 Journal of Graph Theory
2 Journal of Number Theory
2 Proceedings of the American Mathematical Society
2 Transactions of the American Mathematical Society
2 Asia-Pacific Journal of Operational Research
2 Machine Learning
2 Japan Journal of Industrial and Applied Mathematics
2 MSCS. Mathematical Structures in Computer Science
2 Geometric and Functional Analysis. GAFA
2 Linear Algebra and its Applications
2 Proceedings of the National Academy of Sciences of the United States of America
2 SIAM Review
2 Bulletin of the American Mathematical Society. New Series
2 Applicable Algebra in Engineering, Communication and Computing
2 Cybernetics and Systems Analysis
2 International Journal of Modern Physics D
2 Journal de Théorie des Nombres de Bordeaux
2 Applied and Computational Harmonic Analysis
2 Journal of Mathematical Sciences (New York)
2 The Journal of Fourier Analysis and Applications
2 Wuhan University Journal of Natural Sciences (WUJNS)
2 Journal of the European Mathematical Society (JEMS)
2 CEJOR. Central European Journal of Operations Research
2 Annales Henri Poincaré
2 Journal of Applied Mathematics
2 4OR
2 Journal of Physics A: Mathematical and Theoretical
2 Algorithms
2 RAIRO. Theoretical Informatics and Applications
2 Frontiers of Computer Science
2 Computer Science Review
1 Acta Informatica
1 Artificial Intelligence
1 Classical and Quantum Gravity
1 Communications on Pure and Applied Mathematics
1 Inverse Problems
1 Physics Letters. A
1 Russian Mathematical Surveys
1 Theoretical and Mathematical Physics
1 ACM Transactions on Mathematical Software
1 The Annals of Statistics
...and 73 more Serials
all top 5

Cited in 48 Fields

485 Computer science (68-XX)
355 Information and communication theory, circuits (94-XX)
166 Quantum theory (81-XX)
149 Combinatorics (05-XX)
149 Operations research, mathematical programming (90-XX)
68 Number theory (11-XX)
48 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
34 Probability theory and stochastic processes (60-XX)
25 Functional analysis (46-XX)
20 Convex and discrete geometry (52-XX)
19 Statistics (62-XX)
18 Statistical mechanics, structure of matter (82-XX)
17 Numerical analysis (65-XX)
15 Linear and multilinear algebra; matrix theory (15-XX)
10 Algebraic geometry (14-XX)
9 Group theory and generalizations (20-XX)
7 Operator theory (47-XX)
7 Biology and other natural sciences (92-XX)
6 Functions of a complex variable (30-XX)
6 Fluid mechanics (76-XX)
5 Mathematical logic and foundations (03-XX)
5 Measure and integration (28-XX)
5 Partial differential equations (35-XX)
5 Harmonic analysis on Euclidean spaces (42-XX)
4 Order, lattices, ordered algebraic structures (06-XX)
4 Dynamical systems and ergodic theory (37-XX)
4 Geometry (51-XX)
3 Field theory and polynomials (12-XX)
3 Commutative algebra (13-XX)
3 Calculus of variations and optimal control; optimization (49-XX)
3 Relativity and gravitational theory (83-XX)
3 Astronomy and astrophysics (85-XX)
2 General algebraic systems (08-XX)
2 Classical thermodynamics, heat transfer (80-XX)
1 General and overarching topics; collections (00-XX)
1 History and biography (01-XX)
1 Associative rings and algebras (16-XX)
1 Real functions (26-XX)
1 Approximations and expansions (41-XX)
1 Abstract harmonic analysis (43-XX)
1 Differential geometry (53-XX)
1 General topology (54-XX)
1 Manifolds and cell complexes (57-XX)
1 Global analysis, analysis on manifolds (58-XX)
1 Mechanics of particles and systems (70-XX)
1 Mechanics of deformable solids (74-XX)
1 Geophysics (86-XX)
1 Systems theory; control (93-XX)

Citations by Year