## Regev, Oded

Compute Distance To:
 Author ID: regev.oded Published as: Regev, Oded; Regev, O. Homepage: https://cims.nyu.edu/~regev/ External Links: MGP · ORCID · Wikidata · arXiv · Google Scholar · MathOverflow · dblp
 Documents Indexed: 103 Publications since 1999 Co-Authors: 77 Co-Authors with 91 Joint Publications 2,534 Co-Co-Authors
all top 5

### Co-Authors

 12 single-authored 12 Haviv, Ishay 11 Azar, Yossi 10 Kempe, Julia 8 de Wolf, Ronald Michiel 6 Dinur, Irit 6 Peikert, Chris 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 Golovnev, Alexander 3 Guruswami, Venkatesan 3 Khot, Subhash Ajit 3 Micciancio, Daniele 3 Mossel, Elchanan 3 Nguyen, Phong Q. 3 Smyth, Clifford 3 Weinstein, Omri 2 Aggarwal, Divesh 2 Briët, Jop 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 2 Weiss, Barak 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 Gama, Nicolas 1 Klartag, Bo’az 1 Lovett, Shachar 1 Moitra, Ankur 1 Ordentlich, Or 1 Posobin, Gleb 1 Raghavendra, Prasad 1 Rao, Shravas K. 1 Raz, Ran 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 Stehlé, Damien 1 Steif, Jeffrey E. 1 Steurer, David 1 Sudakov, Benny 1 Ta-Shma, Amnon 1 Tauman Kalai, Yael 1 Trevisan, Luca 1 Vijayaraghavan, Aravindan 1 Witmer, David 1 Woeginger, Gerhard Johannes
all top 5

### Serials

 13 SIAM Journal on Computing 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 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 Journal of the American Mathematical Society 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 Electronic Communications in Probability 1 Journal of Scheduling 1 Electronic Research Announcements in Mathematical Sciences 1 Journal of Topology and Analysis
all top 5

### Fields

 68 Computer science (68-XX) 31 Information and communication theory, circuits (94-XX) 26 Quantum theory (81-XX) 15 Number theory (11-XX) 11 Operations research, mathematical programming (90-XX) 10 Combinatorics (05-XX) 8 Probability theory and stochastic processes (60-XX) 5 Functional analysis (46-XX) 5 Convex and discrete geometry (52-XX) 3 Linear and multilinear algebra; matrix theory (15-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 Harmonic analysis on Euclidean spaces (42-XX) 1 Operator theory (47-XX) 1 Geometry (51-XX) 1 Mechanics of particles and systems (70-XX) 1 Statistical mechanics, structure of matter (82-XX)

### Citations contained in zbMATH Open

90 Publications have been cited 2,117 times in 1,299 Documents Cited by Year
On lattices, learning with errors, random linear codes, and cryptography. Zbl 1192.94106
Regev, Oded
2005
On lattices, learning with errors, random linear codes, and cryptography. Zbl 1325.68101
Regev, Oded
2009
Vertex cover might be hard to approximate to within $$2 - \varepsilon$$. Zbl 1133.68061
Khot, Subhash; Regev, Oded
2008
On ideal lattices and learning with errors over rings. Zbl 1279.94099
Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded
2010
Worst-case to average-case reductions based on Gaussian measures. Zbl 1142.68037
Micciancio, Daniele; Regev, Oded
2007
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
New lattice-based cryptographic constructions. Zbl 1125.94026
Regev, Oded
2004
A toolkit for ring-LWE cryptography. Zbl 1300.94082
Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded
2013
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
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
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
Recovering short generators of principal ideals in cyclotomic rings. Zbl 1371.94630
Cramer, Ronald; Ducas, Léo; Peikert, Chris; Regev, Oded
2016
Lattice problems in NP $$\cap$$ coNP. Zbl 1286.68218
Aharonov, Dorit; Regev, Oded
2005
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
Pseudorandomness of ring-LWE for any ring and modulus. Zbl 1370.94536
Peikert, Chris; Regev, Oded; Stephens-Davidowitz, Noah
2017
Conditional hardness for approximate coloring. Zbl 1192.68317
Dinur, Irit; Mossel, Elchanan; Regev, Oded
2009
The hardness of 3-uniform hypergraph coloring. Zbl 1106.68080
Dinur, Irit; Regev, Oded; Smyth, Clifford
2005
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
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
Quantum computation and lattice problems. Zbl 1057.81012
Regev, Oded
2004
An optimal lower bound on the communication complexity of gap-Hamming-distance. Zbl 1259.68087
Chakrabarti, Amit; Regev, Oded
2012
Near-optimal and explicit Bell inequality violations. Zbl 1298.81034
Buhrman, Harry; Regev, Oded; Scarpa, Giannicola; de Wolf, Ronald
2012
Unique games with entangled provers are easy. Zbl 1244.68040
Kempe, Julia; Regev, Oded; Toner, Ben
2010
Lattice-based cryptography. Zbl 1161.94425
Regev, Oded
2006
Quantum one-way communication can be exponentially stronger than classical communication. Zbl 1288.68074
Regev, Oded; Klartag, Bo’az
2011
The complexity of the covering radius problem. Zbl 1085.68063
Guruswami, Venkatesan; Micciancio, Daniele; Regev, Oded
2005
An optimal lower bound on the communication complexity of gap-Hamming-distance. Zbl 1288.90005
Chakrabarti, Amit; Regev, Oded
2011
Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures. Zbl 1159.94369
Nguyen, Phong Q.; Regev, Oded
2009
Independent sets in graph powers are almost contained in juntas. Zbl 1147.05058
Dinur, Irit; Friedgut, Ehud; Regev, Oded
2008
Conditional hardness for approximate coloring. Zbl 1301.68143
Dinur, Irit; Mossel, Elchanan; Regev, Oded
2006
A new multilayered {PCP} and the hardness of hypergraph vertex cover. Zbl 1192.68290
Dinur, Irit; Guruswami, Venkatesan; Khot, Subhash; Regev, Oded
2003
Lattice problems and norm embeddings. Zbl 1301.68151
Regev, Oded; Rosen, Ricky
2006
Bell violations through independent bases games. Zbl 1268.81038
Regev, Oded
2012
The restricted isometry property of subsampled Fourier matrices. Zbl 1439.94011
Haviv, Ishay; Regev, Oded
2016
Minimizing the flow time without migration. Zbl 1345.68025
Awerbuch, Baruch; Azar, Yossi; Leonardi, Stefano; Regev, Oded
1999
An inequality for Gaussians on lattices. Zbl 1395.11105
Regev, Oded; Stephens-Davidowitz, Noah
2017
Learning a parallelepiped: cryptanalysis of GGH and NTRU signatures. Zbl 1140.94365
Nguyen, Phong Q.; Regev, Oded
2006
Tensor-based hardness of the shortest vector problem to within almost polynomial factors. Zbl 1232.68066
Haviv, Ishay; Regev, Oded
2007
New lattice based cryptographic constructions. Zbl 1192.94105
Regev, Oded
2003
Priority algorithms for makespan minimization in the subset model. Zbl 1042.68019
Regev, Oded
2002
Strongly polynomial algorithms for the unsplittable flow problem. Zbl 1010.90521
Azar, Yossi; Regev, Oded
2001
Efficient rounding for the noncommutative Grothendieck inequality. Zbl 1293.68151
Naor, Assaf; Regev, Oded; Vidick, Thomas
2013
Simulating quantum correlations with finite communication. Zbl 1205.68181
Regev, Oded; Toner, Ben
2009
Tensor-based hardness of the shortest vector problem to within almost polynomial factors. Zbl 1253.68152
Haviv, Ishay; Regev, Oded
2012
3-local Hamiltonian is QMA-complete. Zbl 1152.81749
Kempe, J.; Regev, O.
2003
The restricted isometry property of subsampled Fourier matrices. Zbl 1379.46014
Haviv, Ishay; Regev, Oded
2017
Efficient quantum algorithms for (gapped) group testing and junta testing. Zbl 1410.68132
Ambainis, Andris; Belovs, Aleksandrs; Regev, Oded; de Wolf, Ronald
2016
Quantum XOR games. Zbl 1348.81177
Regev, Oded; Vidick, Thomas
2015
Tight hardness of the non-commutative Grothendieck problem. Zbl 1387.68122
Briët, Jop; Regev, Oded; Saket, Rishi
2017
Impossibility of a quantum speed-up with a faulty oracle. Zbl 1153.68365
Regev, Oded; Schiff, Liron
2008
A reverse Minkowski theorem. Zbl 1370.11073
Regev, Oded; Stephens-Davidowitz, Noah
2017
The minrank of random graphs. Zbl 1432.05095
Golovnev, Alexander; Regev, Oded; Weinstein, Omri
2018
Minimizing the flow time without migration. Zbl 1051.68072
Awerbuch, Baruch; Azar, Yossi; Leonardi, Stefano; Regev, Oded
2002
Combinatorial algorithms for the unsplittable flow problem. Zbl 1092.68116
Azar, Yossi; Regev, Oded
2006
Kneser graphs are like Swiss cheese. Zbl 1404.05088
Friedgut, Ehud; Regev, Oded
2018
Hardness of the covering radius problem on lattices. Zbl 1286.68192
Haviv, Ishay; Regev, Oded
2012
Elementary proofs of Grothendieck theorems for completely bounded norms. Zbl 1349.46062
Regev, Oded; Vidick, Thomas
2014
Entropy-based bounds on dimension reduction in $$L^1$$. Zbl 1311.68176
Regev, Oded
2013
A note on the distribution of the distance from a lattice. Zbl 1163.68040
Haviv, Ishay; Lyubashevsky, Vadim; Regev, Oded
2009
A note on discrete Gaussian combinations of lattice vectors. Zbl 1375.60062
Aggarwal, Divesh; Regev, Oded
2016
On the complexity of lattice problems with polynomial approximation factors. Zbl 1237.68102
Regev, Oded
2010
Counterexamples to a conjecture of Woods. Zbl 1380.11086
Regev, Oded; Shapira, Uri; Weiss, Barak
2017
Long monotone paths in line arrangements. Zbl 1065.52016
Balogh, József; Regev, Oded; Smyth, Clifford; Steiger, William; Szegedy, Mario
2004
Locally decodable codes and the failure of cotype for projective tensor products. Zbl 1262.46008
Briët, Jop; Naor, Assaf; Regev, Oded
2012
Better gap-Hamming lower bounds via better round elimination. Zbl 1305.68091
Brody, Joshua; Chakrabarti, Amit; Regev, Oded; Vidick, Thomas; de Wolf, Ronald
2010
Learning with errors over rings. (Abstract). Zbl 1231.94055
Regev, Oded
2010
Improved inapproximability of lattice and coding problems with preprocessing. Zbl 1315.94036
Regev, Oded
2004
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 Euclidean distortion of flat tori. Zbl 1279.46014
Haviv, Ishay; Regev, Oded
2013
A counterexample to monotonicity of relative mass in random walks. Zbl 1343.60054
Regev, Oded; Shinkar, Igor
2016
On the lattice isomorphism problem. Zbl 1421.68085
Haviv, Ishay; Regev, Oded
2014
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
Temporary tasks assignment resolved. Zbl 1093.68546
Armon, Amitai; Azar, Yossi; Epstein, Leah; Regev, Oded
2002
The list-decoding size of Fourier-sparse Boolean functions. Zbl 1427.68362
Haviv, Ishay; Regev, Oded
2016
Efficient rounding for the noncommutative Grothendieck inequality. Zbl 1302.68323
Naor, Assaf; Regev, Oded; Vidick, Thomas
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
The complexity of the local Hamiltonian problem. Zbl 1117.68378
Kempe, Julia; Kitaev, Alexei; Regev, Oded
2004
The list-decoding size of Fourier-sparse Boolean functions. Zbl 1378.94082
Haviv, Ishay; Regev, Oded
2015
A counterexample to a strong variant of the polynomial Freiman-Ruzsa conjecture in Euclidean space. Zbl 1404.11010
Lovett, Shachar; Regev, Oded
2017
Krivine schemes are optimal. Zbl 1317.46010
Naor, Assaf; Regev, Oded
2014
On the space complexity of linear programming with preprocessing. Zbl 1334.68105
Tauman Kalai, Yael; Raz, Ran; Regev, Oded
2016
Upper bounds on the noise threshold for fault-tolerant quantum computing. Zbl 1153.81467
Kempe, Julia; Regev, Oded; Unger, Falk; de Wolf, Ronald
2008
Quantum SAT for a qutrit-cinquit pair is QMA$$_{1}$$-complete. Zbl 1153.81465
Eldar, Lior; Regev, Oded
2008
Concentration of Markov chains with bounded moments. Zbl 07310525
Naor, Assaf; Rao, Shravas; Regev, Oded
2020
Off-line temporary tasks assignment. Zbl 1061.90043
Azar, Yossi; Regev, Oded; Sgall, Jiří; Woeginger, Gerhard J.
2002
Concentration of Markov chains with bounded moments. Zbl 07310525
Naor, Assaf; Rao, Shravas; Regev, Oded
2020
The minrank of random graphs. Zbl 1432.05095
Golovnev, Alexander; Regev, Oded; Weinstein, Omri
2018
Kneser graphs are like Swiss cheese. Zbl 1404.05088
Friedgut, Ehud; Regev, Oded
2018
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
The restricted isometry property of subsampled Fourier matrices. Zbl 1379.46014
Haviv, Ishay; Regev, Oded
2017
Tight hardness of the non-commutative Grothendieck problem. Zbl 1387.68122
Briët, Jop; Regev, Oded; Saket, Rishi
2017
A reverse Minkowski theorem. Zbl 1370.11073
Regev, Oded; Stephens-Davidowitz, Noah
2017
Counterexamples to a conjecture of Woods. Zbl 1380.11086
Regev, Oded; Shapira, Uri; Weiss, Barak
2017
A counterexample to a strong variant of the polynomial Freiman-Ruzsa conjecture in Euclidean space. Zbl 1404.11010
Lovett, Shachar; Regev, Oded
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
Efficient quantum algorithms for (gapped) group testing and junta testing. Zbl 1410.68132
Ambainis, Andris; Belovs, Aleksandrs; Regev, Oded; de Wolf, Ronald
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
The list-decoding size of Fourier-sparse Boolean functions. Zbl 1427.68362
Haviv, Ishay; Regev, Oded
2016
On the space complexity of linear programming with preprocessing. Zbl 1334.68105
Tauman Kalai, Yael; Raz, Ran; Regev, Oded
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&rsquo;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
Efficient rounding for the noncommutative Grothendieck inequality. Zbl 1302.68323
Naor, Assaf; Regev, Oded; Vidick, Thomas
2014
Krivine schemes are optimal. Zbl 1317.46010
Naor, Assaf; 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
An optimal lower bound on the communication complexity of gap-Hamming-distance. Zbl 1259.68087
Chakrabarti, Amit; Regev, Oded
2012
Near-optimal and explicit Bell inequality violations. Zbl 1298.81034
Buhrman, Harry; Regev, Oded; Scarpa, Giannicola; de Wolf, Ronald
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
Quantum one-way communication can be exponentially stronger than classical communication. Zbl 1288.68074
Regev, Oded; Klartag, Bo&rsquo;az
2011
An optimal lower bound on the communication complexity of gap-Hamming-distance. Zbl 1288.90005
Chakrabarti, Amit; Regev, Oded
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
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
Learning with errors over rings. (Abstract). Zbl 1231.94055
Regev, Oded
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
Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures. Zbl 1159.94369
Nguyen, Phong Q.; Regev, Oded
2009
Simulating quantum correlations with finite communication. Zbl 1205.68181
Regev, Oded; Toner, Ben
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
Simultaneous communication protocols with quantum and classical messages. Zbl 1286.68019
Gavinsky, Dmitry; Regev, Oded; de Wolf, Ronald
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
Quantum SAT for a qutrit-cinquit pair is QMA$$_{1}$$-complete. Zbl 1153.81465
Eldar, Lior; Regev, Oded
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
Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality. Zbl 1140.60007
Mossel, Elchanan; O&rsquo;Donnell, Ryan; Regev, Oded; Steif, Jeffrey E.; Sudakov, Benny
2006
Lattice-based cryptography. Zbl 1161.94425
Regev, Oded
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
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
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
Priority algorithms for makespan minimization in the subset model. Zbl 1042.68019
Regev, Oded
2002
Minimizing the flow time without migration. Zbl 1051.68072
Awerbuch, Baruch; Azar, Yossi; Leonardi, Stefano; 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
all top 5

### Cited by 2,267 Authors

 15 Libert, Benoît 15 Regev, Oded 15 Susilo, Willy 14 Stehlé, Damien 13 Guruswami, Venkatesan 12 Brakerski, Zvika 12 Mossel, Elchanan 12 Nguyen, Khoa 12 Palazuelos, Carlos 12 Wang, Huaxiong 11 Ducas, Léo 11 Fouque, Pierre-Alain 11 Peikert, Chris 11 Vaikuntanathan, Vinod 11 Yasuda, Masaya 10 Epstein, Leah 10 Khot, Subhash Ajit 10 Lu, Songfeng 10 Sun, Jie 9 Albrecht, Martin R. 9 Chandrasekaran, Karthekeyan 9 Haviv, Ishay 9 Lyubashevsky, Vadim 9 Vidick, Thomas 8 Bitansky, Nir 8 Escoffier, Bruno 8 Ishai, Yuval 8 Junge, Marius 8 Laarhoven, Thijs 8 Ling, San 8 May, Alexander 8 Steinfeld, Ron 8 Tan, Zhiyi 8 Waters, Brent 7 Halevi, Shai 7 Katsumata, Shuichi 7 Naor, Assaf 7 Rosen, Alon 7 Tibouchi, Mehdi 7 Yu, Yang 6 Bai, Shi 6 Briët, Jop 6 Chen, Yilei 6 Dósa, György 6 Duong, Dung Hoang 6 Espitau, Thomas 6 He, Yong 6 Hu, Yupu 6 Liu, Fang 6 Ma, Chunguang 6 Masny, Daniel 6 Micciancio, Daniele 6 Roux-Langlois, Adeline 6 Sarathi Roy, Partha 6 Wichs, Daniel 6 Yamakawa, Takashi 6 Zhandry, Mark 6 Zhang, Jiang 5 Aggarwal, Divesh 5 Azar, Yossi 5 Borodin, Allan B. 5 Boyen, Xavier 5 Braverman, Mark 5 Broadbent, Anne 5 Castryck, Wouter 5 Cheon, Jung Hee 5 Chiesa, Alessandro 5 Cubitt, Toby S. 5 Döttling, Nico 5 El Ouali, Mourad 5 Feldman, Vitaly 5 Galbraith, Steven D. 5 Gama, Nicolas 5 Garg, Sanjam 5 Grigorescu, Elena 5 Guo, Siyao 5 Kao, Mong-Jen 5 Karpinski, Marek 5 Kirchner, Paul 5 Kirshanova, Elena 5 Koppula, Venkata 5 Kotov, Vladimir M. 5 Li, Qinyi 5 Lin, Huijia 5 Lindner, Richard 5 Mouhartem, Fabrice 5 Nakamura, Satoshi 5 Nishimaki, Ryo 5 Perret, Ludovic 5 Ran, Yingli 5 Sahai, Amit 5 Sakzad, Amin 5 Saurabh, Saket 5 Schmied, Richard 5 Srivastav, Anand 5 Stephens-Davidowitz, Noah 5 Takagi, Tsuyoshi 5 Vercauteren, Frederik 5 Viehmann, Claus 5 Wee, Hoeteck ...and 2,167 more Authors
all top 5

### Cited in 199 Serials

 88 Theoretical Computer Science 42 Algorithmica 36 Designs, Codes and Cryptography 34 SIAM Journal on Computing 34 Journal of Cryptology 27 Quantum Information Processing 20 Journal of Mathematical Cryptology 17 Discrete Applied Mathematics 17 Journal of Combinatorial Optimization 16 Information Processing Letters 16 Journal of Computer and System Sciences 15 SIAM Journal on Discrete Mathematics 14 Communications in Mathematical Physics 14 New Journal of Physics 12 Journal of Mathematical Physics 12 Theory of Computing Systems 10 Computational Complexity 9 International Journal of Theoretical Physics 9 Information Sciences 9 Operations Research Letters 9 Journal of Scheduling 9 International Journal of Quantum Information 8 Israel Journal of Mathematics 8 Information and Computation 8 Random Structures & Algorithms 7 Discrete & Computational Geometry 7 Journal of Discrete Algorithms 6 International Journal of Foundations of Computer Science 6 Mathematical Problems in Engineering 6 Advances in Mathematics of Communications 6 Discrete Analysis 5 Mathematics of Operations Research 5 Computational Geometry 5 Mathematical Programming. Series A. Series B 5 Theory of Computing 5 SIAM Journal on Applied Algebra and Geometry 4 Applicable Algebra in Engineering, Communication and Computing 4 Combinatorics, Probability and Computing 4 The Journal of Fourier Analysis and Applications 4 Discrete Optimization 4 Science China. Information Sciences 3 Discrete Mathematics 3 Mathematics of Computation 3 Computing 3 Journal of Combinatorial Theory. Series A 3 Journal of Functional Analysis 3 Combinatorica 3 Probability Theory and Related Fields 3 Journal of Complexity 3 Proceedings of the National Academy of Sciences of the United States of America 3 Bulletin of the American Mathematical Society. New Series 3 SIAM Journal on Optimization 3 Open Systems & Information Dynamics 3 Soft Computing 3 Chicago Journal of Theoretical Computer Science 3 Journal of Graph Algorithms and Applications 3 Journal of the ACM 3 LMS Journal of Computation and Mathematics 3 Annales Henri Poincaré 3 Optimization Letters 3 Cryptography and Communications 3 ACM Transactions on Computation Theory 2 Artificial Intelligence 2 Bulletin of the Australian Mathematical Society 2 Computers & Mathematics with Applications 2 Journal of Statistical Physics 2 Reports on Mathematical Physics 2 Reviews of Modern Physics 2 Journal of Graph Theory 2 Journal of the Korean Mathematical Society 2 Journal of Number Theory 2 Proceedings of the American Mathematical Society 2 Transactions of the American Mathematical Society 2 Statistical Science 2 Computers & Operations Research 2 Asia-Pacific Journal of Operational Research 2 Journal of the American Mathematical Society 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 SIAM Review 2 Cybernetics and Systems Analysis 2 Journal de Théorie des Nombres de Bordeaux 2 Applied and Computational Harmonic Analysis 2 Journal of Mathematical Sciences (New York) 2 Wuhan University Journal of Natural Sciences (WUJNS) 2 Data Mining and Knowledge Discovery 2 Journal of Discrete Mathematical Sciences & Cryptography 2 Journal of the European Mathematical Society (JEMS) 2 CEJOR. Central European Journal of Operations Research 2 Journal of Systems Science and Complexity 2 Journal of Applied Mathematics 2 4OR 2 Journal of Algebra and its Applications 2 Journal of Physics A: Mathematical and Theoretical 2 Algorithms 2 RAIRO. Theoretical Informatics and Applications 2 Diskretnyĭ Analiz i Issledovanie Operatsiĭ ...and 99 more Serials
all top 5

### Cited in 46 Fields

 630 Computer science (68-XX) 579 Information and communication theory, circuits (94-XX) 234 Quantum theory (81-XX) 180 Combinatorics (05-XX) 163 Operations research, mathematical programming (90-XX) 90 Number theory (11-XX) 54 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 45 Probability theory and stochastic processes (60-XX) 31 Functional analysis (46-XX) 26 Statistics (62-XX) 25 Convex and discrete geometry (52-XX) 23 Statistical mechanics, structure of matter (82-XX) 22 Numerical analysis (65-XX) 20 Linear and multilinear algebra; matrix theory (15-XX) 13 Algebraic geometry (14-XX) 11 Group theory and generalizations (20-XX) 10 Operator theory (47-XX) 9 Order, lattices, ordered algebraic structures (06-XX) 8 Mathematical logic and foundations (03-XX) 7 Biology and other natural sciences (92-XX) 6 Functions of a complex variable (30-XX) 5 Measure and integration (28-XX) 5 Harmonic analysis on Euclidean spaces (42-XX) 4 Partial differential equations (35-XX) 4 Dynamical systems and ergodic theory (37-XX) 4 Calculus of variations and optimal control; optimization (49-XX) 4 Geometry (51-XX) 3 General algebraic systems (08-XX) 3 Field theory and polynomials (12-XX) 3 Commutative algebra (13-XX) 3 Abstract harmonic analysis (43-XX) 2 Associative rings and algebras (16-XX) 2 Differential geometry (53-XX) 2 Classical thermodynamics, heat transfer (80-XX) 2 Systems theory; control (93-XX) 1 General and overarching topics; collections (00-XX) 1 History and biography (01-XX) 1 Real functions (26-XX) 1 Approximations and expansions (41-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 Relativity and gravitational theory (83-XX) 1 Geophysics (86-XX)

### Wikidata Timeline

The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.