# zbMATH — the first resource for mathematics

## Regev, Oded

Compute Distance To:
 Author ID: regev.oded Published as: Regev, O.; Regev, Oded
 Documents Indexed: 111 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 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 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 Gil, Yossi 1 Golovnev, Alexander 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 Shaviv, Guy E. 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 Weinstein, Omri 1 Weiss, Barak 1 Witmer, David 1 Woeginger, Gerhard Johannes 1 Wright, John L. 1 Yecko, Philip A.
all top 5

#### Serials

 12 SIAM Journal on Computing 7 Astronomy and Astrophysics 5 Theory of Computing 4 Journal of the ACM 3 Chicago Journal of Theoretical Computer Science 3 Quantum Information & Computation 2 IEEE Transactions on Information Theory 2 Information Processing Letters 2 Israel Journal of Mathematics 2 Theoretical Computer Science 2 Algorithmica 2 Discrete & Computational Geometry 2 ACM Transactions on Computation Theory 2 Discrete Analysis 1 Monthly Notices of the Royal Astronomical Society 1 Duke Mathematical Journal 1 Journal of Computer and System Sciences 1 Proceedings of the American Mathematical Society 1 Journal of Operator Theory 1 Combinatorica 1 SIAM Journal on Discrete Mathematics 1 Journal of Cryptology 1 Geometric and Functional Analysis. GAFA 1 SIAM Review 1 Annales de l’Institut Henri Poincaré. Probabilités et Statistiques 1 Computational Complexity 1 Physics of Fluids 1 Electronic Communications in Probability 1 Journal of Scheduling 1 Electronic Research Announcements in Mathematical Sciences 1 Journal of Topology and Analysis 1 Graduate Texts in Physics
all top 5

#### Fields

 66 Computer science (68-XX) 29 Information and communication theory, circuits (94-XX) 26 Quantum theory (81-XX) 14 Number theory (11-XX) 11 Operations research, mathematical programming (90-XX) 9 Combinatorics (05-XX) 9 Astronomy and astrophysics (85-XX) 7 Probability theory and stochastic processes (60-XX) 5 Functional analysis (46-XX) 5 Convex and discrete geometry (52-XX) 5 Fluid mechanics (76-XX) 3 Linear and multilinear algebra; matrix theory (15-XX) 3 Mechanics of particles and systems (70-XX) 3 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 1 Mathematical logic and foundations (03-XX) 1 Functions of a complex variable (30-XX) 1 Several complex variables and analytic spaces (32-XX) 1 Dynamical systems and ergodic theory (37-XX) 1 Harmonic analysis on Euclidean spaces (42-XX) 1 Operator theory (47-XX) 1 Geometry (51-XX) 1 Statistical mechanics, structure of matter (82-XX)

#### Citations contained in zbMATH Open

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

#### Cited by 1,750 Authors

 12 Regev, Oded 11 Guruswami, Venkatesan 10 Epstein, Leah 10 Lu, Songfeng 10 Mossel, Elchanan 10 Palazuelos, Carlos 10 Sun, Jie 9 Chandrasekaran, Karthekeyan 8 Khot, Subhash Ajit 8 Peikert, Chris 8 Stehlé, Damien 8 Tan, Zhiyi 8 Vaikuntanathan, Vinod 8 Wang, Huaxiong 7 Brakerski, Zvika 7 Fouque, Pierre-Alain 7 Libert, Benoît 7 Lyubashevsky, Vadim 7 Naor, Assaf 7 Nguyen, Khoa 7 Vidick, Thomas 7 Yasuda, Masaya 6 Escoffier, Bruno 6 Haviv, Ishay 6 He, Yong 6 Hu, Yupu 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 Dósa, György 5 El Ouali, Mourad 5 Feldman, Vitaly 5 Gama, Nicolas 5 Grigorescu, Elena 5 Koppula, Venkata 5 Kotov, Vladimir M. 5 Lindner, Richard 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 Buchmann, Johannes A. 4 Cash, David M. 4 Castryck, Wouter 4 Cseh, Ágnes 4 Ducas, Léo 4 Feige, Uriel 4 Fernau, Henning 4 Fiorini, Samuel 4 Galbraith, Steven D. 4 Gandikota, Venkata 4 Goldwasser, Shafi 4 Goyal, Rishab 4 Harrow, Aram Wettroth 4 Herold, Gottfried 4 Ishai, Yuval 4 Kao, Mong-Jen 4 Karpinski, Marek 4 Kirchner, Paul 4 Koshiba, Takeshi 4 Larsen, Kim Skak 4 Lee, Euiwoong 4 Lei, Hao 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 Perret, Ludovic 4 Rosen, Alon 4 Saket, Rishi 4 Schneider, Michael 4 Sikora, Jamie 4 Singer, Amit 4 Steinfeld, Ron 4 van Stee, Rob 3 Aggarwal, Divesh 3 Alekhnovich, Michael 3 Arora, Sanjeev 3 Aspuru-Guzik, Alán 3 Bartlett, Stephen D. 3 Bausch, Johannes 3 Bhattacharya, Sayan 3 Brandão, Fernando G. S. L. 3 Branković, Ljiljana 3 Broadbent, Anne ...and 1,650 more Authors
all top 5

#### Cited in 171 Serials

 67 Theoretical Computer Science 36 Algorithmica 27 Designs, Codes and Cryptography 25 SIAM Journal on Computing 25 Quantum Information Processing 24 Journal of Cryptology 17 Journal of Mathematical Cryptology 16 Information Processing Letters 14 Discrete Applied Mathematics 14 Journal of Combinatorial Optimization 14 New Journal of Physics 13 Communications in Mathematical Physics 13 Journal of Computer and System Sciences 13 SIAM Journal on Discrete Mathematics 12 Journal of Mathematical Physics 11 Theory of Computing Systems 10 Operations Research Letters 10 Computational Complexity 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 4 Computational Geometry 4 Combinatorics, Probability and Computing 4 Discrete Optimization 4 Science China. Information Sciences 4 SIAM Journal on Applied Algebra and Geometry 3 Discrete Mathematics 3 Reports on Mathematical Physics 3 Mathematics of Computation 3 Computing 3 Journal of Combinatorial Theory. Series A 3 Combinatorica 3 Probability Theory and Related Fields 3 Linear Algebra and its Applications 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 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 Reviews of Modern Physics 2 Journal of Functional Analysis 2 Journal of Graph Theory 2 Mathematics of Operations Research 2 Proceedings of the American Mathematical Society 2 Transactions of the American Mathematical Society 2 Journal of Complexity 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 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 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 Journal of Computational Physics 1 Physics Letters. A 1 Physics Reports 1 Russian Mathematical Surveys 1 Theoretical and Mathematical Physics 1 ACM Transactions on Mathematical Software 1 Annales Scientifiques de l’École Normale Supérieure. Quatrième Série ...and 71 more Serials
all top 5

#### Cited in 47 Fields

 461 Computer science (68-XX) 345 Information and communication theory, circuits (94-XX) 167 Quantum theory (81-XX) 145 Combinatorics (05-XX) 142 Operations research, mathematical programming (90-XX) 66 Number theory (11-XX) 48 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 33 Probability theory and stochastic processes (60-XX) 25 Functional analysis (46-XX) 21 Convex and discrete geometry (52-XX) 20 Statistical mechanics, structure of matter (82-XX) 17 Statistics (62-XX) 16 Linear and multilinear algebra; matrix theory (15-XX) 15 Numerical analysis (65-XX) 10 Algebraic geometry (14-XX) 9 Group theory and generalizations (20-XX) 7 Mathematical logic and foundations (03-XX) 7 Operator theory (47-XX) 6 Functions of a complex variable (30-XX) 6 Fluid mechanics (76-XX) 5 Measure and integration (28-XX) 5 Partial differential equations (35-XX) 5 Harmonic analysis on Euclidean spaces (42-XX) 5 Biology and other natural sciences (92-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 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)