Edit Profile (opens in new tab) Regev, Oded Compute Distance To: Compute 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,537 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 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) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 90 Publications have been cited 2,179 times in 1,314 Documents Cited by ▼ Year ▼ On lattices, learning with errors, random linear codes, and cryptography. Zbl 1192.94106Regev, Oded 319 2005 On lattices, learning with errors, random linear codes, and cryptography. Zbl 1325.68101Regev, Oded 214 2009 Vertex cover might be hard to approximate to within \(2 - \varepsilon \). Zbl 1133.68061Khot, Subhash; Regev, Oded 180 2008 On ideal lattices and learning with errors over rings. Zbl 1279.94099Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded 142 2010 Worst-case to average-case reductions based on Gaussian measures. Zbl 1142.68037Micciancio, Daniele; Regev, Oded 141 2007 Classical hardness of learning with errors. Zbl 1293.68159Brakerski, Zvika; Langlois, Adeline; Peikert, Chris; Regev, Oded; Stehlé, Damien 103 2013 Lattice-based cryptography. Zbl 1161.81324Micciancio, Daniele; Regev, Oded 64 2009 New lattice-based cryptographic constructions. Zbl 1125.94026Regev, Oded 61 2004 A toolkit for ring-LWE cryptography. Zbl 1300.94082Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded 56 2013 The complexity of the local Hamiltonian problem. Zbl 1102.81032Kempe, Julia; Kitaev, Alexei; Regev, Oded 53 2006 Adiabatic quantum computation is equivalent to standard quantum computation. Zbl 1134.81009Aharonov, Dorit; Van Dam, Wim; Kempe, Julia; Landau, Zeph; Lloyd, Seth; Regev, Oded 53 2007 Lattice enumeration using extreme pruning. Zbl 1280.94056Gama, Nicolas; Nguyen, Phong Q.; Regev, Oded 41 2010 A new multilayered PCP and the hardness of hypergraph vertex cover. Zbl 1079.68039Dinur, Irit; Guruswami, Venkatesan; Khot, Subhash; Regev, Oded 40 2005 On-line bin-stretching. Zbl 0984.68195Azar, Y.; Regev, O. 40 2001 On ideal lattices and learning with errors over rings. Zbl 1281.68140Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded 40 2013 Solving the shortest vector problem in \(2^n\) time using discrete Gaussian sampling (extended abstract). Zbl 1321.68426Aggarwal, Divesh; Dadush, Daniel; Regev, Oded; Stephens-Davidowitz, Noah 29 2015 Recovering short generators of principal ideals in cyclotomic rings. Zbl 1371.94630Cramer, Ronald; Ducas, Léo; Peikert, Chris; Regev, Oded 27 2016 Lattice problems in NP \(\cap\) coNP. Zbl 1286.68218Aharonov, Dorit; Regev, Oded 25 2005 Quantum computation and lattice problems. Zbl 1057.81012Regev, Oded 23 2004 Adiabatic quantum computation is equivalent to standard quantum computation. Zbl 1152.81008Aharonov, Dorit; van Dam, Wim; Kempe, Julia; Landau, Zeph; Lloyd, Seth; Regev, Oded 23 2008 Pseudorandomness of ring-LWE for any ring and modulus. Zbl 1370.94536Peikert, Chris; Regev, Oded; Stephens-Davidowitz, Noah 22 2017 Conditional hardness for approximate coloring. Zbl 1192.68317Dinur, Irit; Mossel, Elchanan; Regev, Oded 22 2009 The hardness of 3-uniform hypergraph coloring. Zbl 1106.68080Dinur, Irit; Regev, Oded; Smyth, Clifford 21 2005 Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality. Zbl 1140.60007Mossel, Elchanan; O’Donnell, Ryan; Regev, Oded; Steif, Jeffrey E.; Sudakov, Benny 20 2006 An optimal lower bound on the communication complexity of gap-Hamming-distance. Zbl 1259.68087Chakrabarti, Amit; Regev, Oded 18 2012 Unique games with entangled provers are easy. Zbl 1244.68040Kempe, Julia; Regev, Oded; Toner, Ben 17 2010 Lattice-based cryptography. Zbl 1161.94425Regev, Oded 16 2006 Near-optimal and explicit Bell inequality violations. Zbl 1298.81034Buhrman, Harry; Regev, Oded; Scarpa, Giannicola; de Wolf, Ronald 16 2012 Quantum one-way communication can be exponentially stronger than classical communication. Zbl 1288.68074Regev, Oded; Klartag, Bo’az 14 2011 The complexity of the covering radius problem. Zbl 1085.68063Guruswami, Venkatesan; Micciancio, Daniele; Regev, Oded 13 2005 An optimal lower bound on the communication complexity of gap-Hamming-distance. Zbl 1288.90005Chakrabarti, Amit; Regev, Oded 12 2011 Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures. Zbl 1159.94369Nguyen, Phong Q.; Regev, Oded 11 2009 Independent sets in graph powers are almost contained in juntas. Zbl 1147.05058Dinur, Irit; Friedgut, Ehud; Regev, Oded 11 2008 Conditional hardness for approximate coloring. Zbl 1301.68143Dinur, Irit; Mossel, Elchanan; Regev, Oded 11 2006 A new multilayered {PCP} and the hardness of hypergraph vertex cover. Zbl 1192.68290Dinur, Irit; Guruswami, Venkatesan; Khot, Subhash; Regev, Oded 11 2003 An inequality for Gaussians on lattices. Zbl 1395.11105Regev, Oded; Stephens-Davidowitz, Noah 10 2017 Bell violations through independent bases games. Zbl 1268.81038Regev, Oded 10 2012 Lattice problems and norm embeddings. Zbl 1301.68151Regev, Oded; Rosen, Ricky 10 2006 The restricted isometry property of subsampled Fourier matrices. Zbl 1439.94011Haviv, Ishay; Regev, Oded 9 2016 Priority algorithms for makespan minimization in the subset model. Zbl 1042.68019Regev, Oded 9 2002 Minimizing the flow time without migration. Zbl 1345.68025Awerbuch, Baruch; Azar, Yossi; Leonardi, Stefano; Regev, Oded 9 1999 Learning a parallelepiped: cryptanalysis of GGH and NTRU signatures. Zbl 1140.94365Nguyen, Phong Q.; Regev, Oded 9 2006 Tensor-based hardness of the shortest vector problem to within almost polynomial factors. Zbl 1232.68066Haviv, Ishay; Regev, Oded 9 2007 Tensor-based hardness of the shortest vector problem to within almost polynomial factors. Zbl 1253.68152Haviv, Ishay; Regev, Oded 9 2012 New lattice based cryptographic constructions. Zbl 1192.94105Regev, Oded 9 2003 Strongly polynomial algorithms for the unsplittable flow problem. Zbl 1010.90521Azar, Yossi; Regev, Oded 8 2001 3-local Hamiltonian is QMA-complete. Zbl 1152.81749Kempe, J.; Regev, O. 8 2003 Simulating quantum correlations with finite communication. Zbl 1205.68181Regev, Oded; Toner, Ben 8 2009 Efficient rounding for the noncommutative Grothendieck inequality. Zbl 1293.68151Naor, Assaf; Regev, Oded; Vidick, Thomas 8 2013 Efficient quantum algorithms for (gapped) group testing and junta testing. Zbl 1410.68132Ambainis, Andris; Belovs, Aleksandrs; Regev, Oded; de Wolf, Ronald 7 2016 The restricted isometry property of subsampled Fourier matrices. Zbl 1379.46014Haviv, Ishay; Regev, Oded 7 2017 Quantum XOR games. Zbl 1348.81177Regev, Oded; Vidick, Thomas 7 2015 Tight hardness of the non-commutative Grothendieck problem. Zbl 1387.68122Briët, Jop; Regev, Oded; Saket, Rishi 7 2017 Impossibility of a quantum speed-up with a faulty oracle. Zbl 1153.68365Regev, Oded; Schiff, Liron 6 2008 Minimizing the flow time without migration. Zbl 1051.68072Awerbuch, Baruch; Azar, Yossi; Leonardi, Stefano; Regev, Oded 5 2002 Long monotone paths in line arrangements. Zbl 1065.52016Balogh, József; Regev, Oded; Smyth, Clifford; Steiger, William; Szegedy, Mario 5 2004 The minrank of random graphs. Zbl 1432.05095Golovnev, Alexander; Regev, Oded; Weinstein, Omri 5 2018 Kneser graphs are like Swiss cheese. Zbl 1404.05088Friedgut, Ehud; Regev, Oded 5 2018 Hardness of the covering radius problem on lattices. Zbl 1286.68192Haviv, Ishay; Regev, Oded 5 2012 Elementary proofs of Grothendieck theorems for completely bounded norms. Zbl 1349.46062Regev, Oded; Vidick, Thomas 5 2014 A reverse Minkowski theorem. Zbl 1370.11073Regev, Oded; Stephens-Davidowitz, Noah 5 2017 Combinatorial algorithms for the unsplittable flow problem. Zbl 1092.68116Azar, Yossi; Regev, Oded 5 2006 Entropy-based bounds on dimension reduction in \(L^1\). Zbl 1311.68176Regev, Oded 5 2013 A note on the distribution of the distance from a lattice. Zbl 1163.68040Haviv, Ishay; Lyubashevsky, Vadim; Regev, Oded 5 2009 Learning with errors over rings. (Abstract). Zbl 1231.94055Regev, Oded 4 2010 A note on discrete Gaussian combinations of lattice vectors. Zbl 1375.60062Aggarwal, Divesh; Regev, Oded 4 2016 Counterexamples to a conjecture of Woods. Zbl 1380.11086Regev, Oded; Shapira, Uri; Weiss, Barak 4 2017 On the complexity of lattice problems with polynomial approximation factors. Zbl 1237.68102Regev, Oded 4 2010 Locally decodable codes and the failure of cotype for projective tensor products. Zbl 1262.46008Briët, Jop; Naor, Assaf; Regev, Oded 4 2012 Better gap-Hamming lower bounds via better round elimination. Zbl 1305.68091Brody, Joshua; Chakrabarti, Amit; Regev, Oded; Vidick, Thomas; de Wolf, Ronald 4 2010 On the hardness of satisfiability with bounded occurrences in the polynomial-time hierarchy. Zbl 1213.68311Haviv, Ishay; Regev, Oded; Ta-Shma, Amnon 3 2007 A counterexample to monotonicity of relative mass in random walks. Zbl 1343.60054Regev, Oded; Shinkar, Igor 3 2016 The Euclidean distortion of flat tori. Zbl 1279.46014Haviv, Ishay; Regev, Oded 3 2013 Improved inapproximability of lattice and coding problems with preprocessing. Zbl 1315.94036Regev, Oded 3 2004 Temporary tasks assignment resolved. Zbl 1093.68546Armon, Amitai; Azar, Yossi; Epstein, Leah; Regev, Oded 2 2002 An optimal randomized cell probe lower bound for approximate nearest neighbor searching. Zbl 1207.68156Chakrabarti, Amit; Regev, Oded 2 2010 A counterexample to a strong variant of the polynomial Freiman-Ruzsa conjecture in Euclidean space. Zbl 1404.11010Lovett, Shachar; Regev, Oded 2 2017 On the lattice isomorphism problem. Zbl 1421.68085Haviv, Ishay; Regev, Oded 2 2014 The list-decoding size of Fourier-sparse Boolean functions. Zbl 1427.68362Haviv, Ishay; Regev, Oded 2 2016 Simultaneous communication protocols with quantum and classical messages. Zbl 1286.68019Gavinsky, Dmitry; Regev, Oded; de Wolf, Ronald 2 2008 Beating the random assignment on constraint satisfaction problems of bounded degree. Zbl 1375.68102Barak, Boaz; Moitra, Ankur; O’donnell, Ryan; Raghavendra, Prasad; Regev, Oded; Steurer, David; Trevisan, Luca; Vijayaraghavan, Aravindan; Witmer, David; Wright, John 2 2015 Efficient rounding for the noncommutative Grothendieck inequality. Zbl 1302.68323Naor, Assaf; Regev, Oded; Vidick, Thomas 2 2014 The list-decoding size of Fourier-sparse Boolean functions. Zbl 1378.94082Haviv, Ishay; Regev, Oded 2 2015 The complexity of the local Hamiltonian problem. Zbl 1117.68378Kempe, Julia; Kitaev, Alexei; Regev, Oded 1 2004 Off-line temporary tasks assignment. Zbl 1061.90043Azar, Yossi; Regev, Oded; Sgall, Jiří; Woeginger, Gerhard J. 1 2002 Concentration of Markov chains with bounded moments. Zbl 07310525Naor, Assaf; Rao, Shravas; Regev, Oded 1 2020 Upper bounds on the noise threshold for fault-tolerant quantum computing. Zbl 1153.81467Kempe, Julia; Regev, Oded; Unger, Falk; de Wolf, Ronald 1 2008 Quantum SAT for a qutrit-cinquit pair is QMA\(_{1}\)-complete. Zbl 1153.81465Eldar, Lior; Regev, Oded 1 2008 Krivine schemes are optimal. Zbl 1317.46010Naor, Assaf; Regev, Oded 1 2014 On the space complexity of linear programming with preprocessing. Zbl 1334.68105Tauman Kalai, Yael; Raz, Ran; Regev, Oded 1 2016 Concentration of Markov chains with bounded moments. Zbl 07310525Naor, Assaf; Rao, Shravas; Regev, Oded 1 2020 The minrank of random graphs. Zbl 1432.05095Golovnev, Alexander; Regev, Oded; Weinstein, Omri 5 2018 Kneser graphs are like Swiss cheese. Zbl 1404.05088Friedgut, Ehud; Regev, Oded 5 2018 Pseudorandomness of ring-LWE for any ring and modulus. Zbl 1370.94536Peikert, Chris; Regev, Oded; Stephens-Davidowitz, Noah 22 2017 An inequality for Gaussians on lattices. Zbl 1395.11105Regev, Oded; Stephens-Davidowitz, Noah 10 2017 The restricted isometry property of subsampled Fourier matrices. Zbl 1379.46014Haviv, Ishay; Regev, Oded 7 2017 Tight hardness of the non-commutative Grothendieck problem. Zbl 1387.68122Briët, Jop; Regev, Oded; Saket, Rishi 7 2017 A reverse Minkowski theorem. Zbl 1370.11073Regev, Oded; Stephens-Davidowitz, Noah 5 2017 Counterexamples to a conjecture of Woods. Zbl 1380.11086Regev, Oded; Shapira, Uri; Weiss, Barak 4 2017 A counterexample to a strong variant of the polynomial Freiman-Ruzsa conjecture in Euclidean space. Zbl 1404.11010Lovett, Shachar; Regev, Oded 2 2017 Recovering short generators of principal ideals in cyclotomic rings. Zbl 1371.94630Cramer, Ronald; Ducas, Léo; Peikert, Chris; Regev, Oded 27 2016 The restricted isometry property of subsampled Fourier matrices. Zbl 1439.94011Haviv, Ishay; Regev, Oded 9 2016 Efficient quantum algorithms for (gapped) group testing and junta testing. Zbl 1410.68132Ambainis, Andris; Belovs, Aleksandrs; Regev, Oded; de Wolf, Ronald 7 2016 A note on discrete Gaussian combinations of lattice vectors. Zbl 1375.60062Aggarwal, Divesh; Regev, Oded 4 2016 A counterexample to monotonicity of relative mass in random walks. Zbl 1343.60054Regev, Oded; Shinkar, Igor 3 2016 The list-decoding size of Fourier-sparse Boolean functions. Zbl 1427.68362Haviv, Ishay; Regev, Oded 2 2016 On the space complexity of linear programming with preprocessing. Zbl 1334.68105Tauman Kalai, Yael; Raz, Ran; Regev, Oded 1 2016 Solving the shortest vector problem in \(2^n\) time using discrete Gaussian sampling (extended abstract). Zbl 1321.68426Aggarwal, Divesh; Dadush, Daniel; Regev, Oded; Stephens-Davidowitz, Noah 29 2015 Quantum XOR games. Zbl 1348.81177Regev, Oded; Vidick, Thomas 7 2015 Beating the random assignment on constraint satisfaction problems of bounded degree. Zbl 1375.68102Barak, 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.94082Haviv, Ishay; Regev, Oded 2 2015 Elementary proofs of Grothendieck theorems for completely bounded norms. Zbl 1349.46062Regev, Oded; Vidick, Thomas 5 2014 On the lattice isomorphism problem. Zbl 1421.68085Haviv, Ishay; Regev, Oded 2 2014 Efficient rounding for the noncommutative Grothendieck inequality. Zbl 1302.68323Naor, Assaf; Regev, Oded; Vidick, Thomas 2 2014 Krivine schemes are optimal. Zbl 1317.46010Naor, Assaf; Regev, Oded 1 2014 Classical hardness of learning with errors. Zbl 1293.68159Brakerski, Zvika; Langlois, Adeline; Peikert, Chris; Regev, Oded; Stehlé, Damien 103 2013 A toolkit for ring-LWE cryptography. Zbl 1300.94082Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded 56 2013 On ideal lattices and learning with errors over rings. Zbl 1281.68140Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded 40 2013 Efficient rounding for the noncommutative Grothendieck inequality. Zbl 1293.68151Naor, Assaf; Regev, Oded; Vidick, Thomas 8 2013 Entropy-based bounds on dimension reduction in \(L^1\). Zbl 1311.68176Regev, Oded 5 2013 The Euclidean distortion of flat tori. Zbl 1279.46014Haviv, Ishay; Regev, Oded 3 2013 An optimal lower bound on the communication complexity of gap-Hamming-distance. Zbl 1259.68087Chakrabarti, Amit; Regev, Oded 18 2012 Near-optimal and explicit Bell inequality violations. Zbl 1298.81034Buhrman, Harry; Regev, Oded; Scarpa, Giannicola; de Wolf, Ronald 16 2012 Bell violations through independent bases games. Zbl 1268.81038Regev, Oded 10 2012 Tensor-based hardness of the shortest vector problem to within almost polynomial factors. Zbl 1253.68152Haviv, Ishay; Regev, Oded 9 2012 Hardness of the covering radius problem on lattices. Zbl 1286.68192Haviv, Ishay; Regev, Oded 5 2012 Locally decodable codes and the failure of cotype for projective tensor products. Zbl 1262.46008Briët, Jop; Naor, Assaf; Regev, Oded 4 2012 Quantum one-way communication can be exponentially stronger than classical communication. Zbl 1288.68074Regev, Oded; Klartag, Bo’az 14 2011 An optimal lower bound on the communication complexity of gap-Hamming-distance. Zbl 1288.90005Chakrabarti, Amit; Regev, Oded 12 2011 On ideal lattices and learning with errors over rings. Zbl 1279.94099Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded 142 2010 Lattice enumeration using extreme pruning. Zbl 1280.94056Gama, Nicolas; Nguyen, Phong Q.; Regev, Oded 41 2010 Unique games with entangled provers are easy. Zbl 1244.68040Kempe, Julia; Regev, Oded; Toner, Ben 17 2010 Learning with errors over rings. (Abstract). Zbl 1231.94055Regev, Oded 4 2010 On the complexity of lattice problems with polynomial approximation factors. Zbl 1237.68102Regev, Oded 4 2010 Better gap-Hamming lower bounds via better round elimination. Zbl 1305.68091Brody, Joshua; Chakrabarti, Amit; Regev, Oded; Vidick, Thomas; de Wolf, Ronald 4 2010 An optimal randomized cell probe lower bound for approximate nearest neighbor searching. Zbl 1207.68156Chakrabarti, Amit; Regev, Oded 2 2010 On lattices, learning with errors, random linear codes, and cryptography. Zbl 1325.68101Regev, Oded 214 2009 Lattice-based cryptography. Zbl 1161.81324Micciancio, Daniele; Regev, Oded 64 2009 Conditional hardness for approximate coloring. Zbl 1192.68317Dinur, Irit; Mossel, Elchanan; Regev, Oded 22 2009 Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures. Zbl 1159.94369Nguyen, Phong Q.; Regev, Oded 11 2009 Simulating quantum correlations with finite communication. Zbl 1205.68181Regev, Oded; Toner, Ben 8 2009 A note on the distribution of the distance from a lattice. Zbl 1163.68040Haviv, Ishay; Lyubashevsky, Vadim; Regev, Oded 5 2009 Vertex cover might be hard to approximate to within \(2 - \varepsilon \). Zbl 1133.68061Khot, Subhash; Regev, Oded 180 2008 Adiabatic quantum computation is equivalent to standard quantum computation. Zbl 1152.81008Aharonov, Dorit; van Dam, Wim; Kempe, Julia; Landau, Zeph; Lloyd, Seth; Regev, Oded 23 2008 Independent sets in graph powers are almost contained in juntas. Zbl 1147.05058Dinur, Irit; Friedgut, Ehud; Regev, Oded 11 2008 Impossibility of a quantum speed-up with a faulty oracle. Zbl 1153.68365Regev, Oded; Schiff, Liron 6 2008 Simultaneous communication protocols with quantum and classical messages. Zbl 1286.68019Gavinsky, Dmitry; Regev, Oded; de Wolf, Ronald 2 2008 Upper bounds on the noise threshold for fault-tolerant quantum computing. Zbl 1153.81467Kempe, Julia; Regev, Oded; Unger, Falk; de Wolf, Ronald 1 2008 Quantum SAT for a qutrit-cinquit pair is QMA\(_{1}\)-complete. Zbl 1153.81465Eldar, Lior; Regev, Oded 1 2008 Worst-case to average-case reductions based on Gaussian measures. Zbl 1142.68037Micciancio, Daniele; Regev, Oded 141 2007 Adiabatic quantum computation is equivalent to standard quantum computation. Zbl 1134.81009Aharonov, Dorit; Van Dam, Wim; Kempe, Julia; Landau, Zeph; Lloyd, Seth; Regev, Oded 53 2007 Tensor-based hardness of the shortest vector problem to within almost polynomial factors. Zbl 1232.68066Haviv, Ishay; Regev, Oded 9 2007 On the hardness of satisfiability with bounded occurrences in the polynomial-time hierarchy. Zbl 1213.68311Haviv, Ishay; Regev, Oded; Ta-Shma, Amnon 3 2007 The complexity of the local Hamiltonian problem. Zbl 1102.81032Kempe, Julia; Kitaev, Alexei; Regev, Oded 53 2006 Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality. Zbl 1140.60007Mossel, Elchanan; O’Donnell, Ryan; Regev, Oded; Steif, Jeffrey E.; Sudakov, Benny 20 2006 Lattice-based cryptography. Zbl 1161.94425Regev, Oded 16 2006 Conditional hardness for approximate coloring. Zbl 1301.68143Dinur, Irit; Mossel, Elchanan; Regev, Oded 11 2006 Lattice problems and norm embeddings. Zbl 1301.68151Regev, Oded; Rosen, Ricky 10 2006 Learning a parallelepiped: cryptanalysis of GGH and NTRU signatures. Zbl 1140.94365Nguyen, Phong Q.; Regev, Oded 9 2006 Combinatorial algorithms for the unsplittable flow problem. Zbl 1092.68116Azar, Yossi; Regev, Oded 5 2006 On lattices, learning with errors, random linear codes, and cryptography. Zbl 1192.94106Regev, Oded 319 2005 A new multilayered PCP and the hardness of hypergraph vertex cover. Zbl 1079.68039Dinur, Irit; Guruswami, Venkatesan; Khot, Subhash; Regev, Oded 40 2005 Lattice problems in NP \(\cap\) coNP. Zbl 1286.68218Aharonov, Dorit; Regev, Oded 25 2005 The hardness of 3-uniform hypergraph coloring. Zbl 1106.68080Dinur, Irit; Regev, Oded; Smyth, Clifford 21 2005 The complexity of the covering radius problem. Zbl 1085.68063Guruswami, Venkatesan; Micciancio, Daniele; Regev, Oded 13 2005 New lattice-based cryptographic constructions. Zbl 1125.94026Regev, Oded 61 2004 Quantum computation and lattice problems. Zbl 1057.81012Regev, Oded 23 2004 Long monotone paths in line arrangements. Zbl 1065.52016Balogh, József; Regev, Oded; Smyth, Clifford; Steiger, William; Szegedy, Mario 5 2004 Improved inapproximability of lattice and coding problems with preprocessing. Zbl 1315.94036Regev, Oded 3 2004 The complexity of the local Hamiltonian problem. Zbl 1117.68378Kempe, Julia; Kitaev, Alexei; Regev, Oded 1 2004 A new multilayered {PCP} and the hardness of hypergraph vertex cover. Zbl 1192.68290Dinur, Irit; Guruswami, Venkatesan; Khot, Subhash; Regev, Oded 11 2003 New lattice based cryptographic constructions. Zbl 1192.94105Regev, Oded 9 2003 3-local Hamiltonian is QMA-complete. Zbl 1152.81749Kempe, J.; Regev, O. 8 2003 Priority algorithms for makespan minimization in the subset model. Zbl 1042.68019Regev, Oded 9 2002 Minimizing the flow time without migration. Zbl 1051.68072Awerbuch, Baruch; Azar, Yossi; Leonardi, Stefano; Regev, Oded 5 2002 Temporary tasks assignment resolved. Zbl 1093.68546Armon, Amitai; Azar, Yossi; Epstein, Leah; Regev, Oded 2 2002 Off-line temporary tasks assignment. Zbl 1061.90043Azar, Yossi; Regev, Oded; Sgall, Jiří; Woeginger, Gerhard J. 1 2002 On-line bin-stretching. Zbl 0984.68195Azar, Y.; Regev, O. 40 2001 Strongly polynomial algorithms for the unsplittable flow problem. Zbl 1010.90521Azar, Yossi; Regev, Oded 8 2001 Minimizing the flow time without migration. Zbl 1345.68025Awerbuch, Baruch; Azar, Yossi; Leonardi, Stefano; Regev, Oded 9 1999 all cited Publications top 5 cited Publications all top 5 Cited by 2,301 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 Lu, Songfeng 11 Peikert, Chris 11 Sun, Jie 11 Vaikuntanathan, Vinod 11 Yasuda, Masaya 10 Epstein, Leah 10 Khot, Subhash Ajit 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 Roux-Langlois, Adeline 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 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,201 more Authors all top 5 Cited in 199 Serials 88 Theoretical Computer Science 42 Algorithmica 36 Journal of Cryptology 36 Designs, Codes and Cryptography 35 Quantum Information Processing 34 SIAM Journal on Computing 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 Information and Computation 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 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 Cybernetics and Systems Analysis 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 Advances in Mathematics 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 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 ...and 99 more Serials all top 5 Cited in 47 Fields 635 Computer science (68-XX) 585 Information and communication theory, circuits (94-XX) 240 Quantum theory (81-XX) 181 Combinatorics (05-XX) 163 Operations research, mathematical programming (90-XX) 93 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) 32 Functional analysis (46-XX) 26 Convex and discrete geometry (52-XX) 26 Statistics (62-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) 8 Mathematical logic and foundations (03-XX) 8 Order, lattices, ordered algebraic structures (06-XX) 7 Biology and other natural sciences (92-XX) 6 Functions of a complex variable (30-XX) 6 Harmonic analysis on Euclidean spaces (42-XX) 5 Measure and integration (28-XX) 4 Partial differential equations (35-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 Dynamical systems and ergodic theory (37-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 Optics, electromagnetic theory (78-XX) 1 Relativity and gravitational theory (83-XX) 1 Geophysics (86-XX) Citations by Year Wikidata Timeline The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.