Regev, Oded; Stephens-Davidowitz, Noah A reverse Minkowski theorem. (English) Zbl 07782629 Ann. Math. (2) 199, No. 1, 1-49 (2024). Reviewer: Oleg Karpenkov (Liverpool) MSC: 52C07 PDFBibTeX XMLCite \textit{O. Regev} and \textit{N. Stephens-Davidowitz}, Ann. Math. (2) 199, No. 1, 1--49 (2024; Zbl 07782629) Full Text: DOI
Regev, Oded Some questions related to the reverse Minkowski theorem. (English) Zbl 07821716 Beliaev, Dmitry (ed.) et al., International congress of mathematicians 2022, ICM 2022, Helsinki, Finland, virtual, July 6–14, 2022. Volume 6. Sections 12–14. Berlin: European Mathematical Society (EMS). 4898-4912 (2023). MSC: 11H06 52C07 PDFBibTeX XMLCite \textit{O. Regev}, in: International congress of mathematicians 2022, ICM 2022, Helsinki, Finland, virtual, July 6--14, 2022. Volume 6. Sections 12--14. Berlin: European Mathematical Society (EMS). 4898--4912 (2023; Zbl 07821716) Full Text: DOI OA License
Naor, Assaf; Regev, Oded An integer parallelotope with small surface area. (English) Zbl 07740623 J. Funct. Anal. 285, No. 10, Article ID 110122, 17 p. (2023). MSC: 52B12 PDFBibTeX XMLCite \textit{A. Naor} and \textit{O. Regev}, J. Funct. Anal. 285, No. 10, Article ID 110122, 17 p. (2023; Zbl 07740623) Full Text: DOI arXiv
Ordentlich, Or; Regev, Oded; Weiss, Barak Bounds on the density of smooth lattice coverings. arXiv:2311.04644 Preprint, arXiv:2311.04644 [math.NT] (2023). BibTeX Cite \textit{O. Ordentlich} et al., ``Bounds on the density of smooth lattice coverings'', Preprint, arXiv:2311.04644 [math.NT] (2023) Full Text: arXiv OA License
Regev, Oded; Stephens-Davidowitz, Noah A simple proof of a reverse Minkowski theorem for integral lattices. arXiv:2306.03697 Preprint, arXiv:2306.03697 [math.MG] (2023). BibTeX Cite \textit{O. Regev} and \textit{N. Stephens-Davidowitz}, ``A simple proof of a reverse Minkowski theorem for integral lattices'', Preprint, arXiv:2306.03697 [math.MG] (2023) Full Text: arXiv OA License
Golovnev, Alexander; Posobin, Gleb; Regev, Oded; Weinstein, Omri Polynomial data structure lower bounds in the group model. (English) Zbl 1483.68462 SIAM J. Comput. 51, No. 2, FOCS20-74-FOCS20-101 (2022). MSC: 68U05 68P05 68Q17 PDFBibTeX XMLCite \textit{A. Golovnev} et al., SIAM J. Comput. 51, No. 2, FOCS20--74-FOCS20--101 (2022; Zbl 1483.68462) Full Text: DOI
Ordentlich, Or; Regev, Oded; Weiss, Barak New bounds on the density of lattice coverings. (English) Zbl 1480.11086 J. Am. Math. Soc. 35, No. 1, 295-308 (2022). Reviewer: Steven T. Dougherty (Scranton) MSC: 11H31 94B75 11T30 PDFBibTeX XMLCite \textit{O. Ordentlich} et al., J. Am. Math. Soc. 35, No. 1, 295--308 (2022; Zbl 1480.11086) Full Text: DOI arXiv
Eisenberg, Yael; Regev, Oded; Stephens-Davidowitz, Noah A Tight Reverse Minkowski Inequality for the Epstein Zeta Function. arXiv:2201.05201 Preprint, arXiv:2201.05201 [math.MG] (2022). BibTeX Cite \textit{Y. Eisenberg} et al., ``A Tight Reverse Minkowski Inequality for the Epstein Zeta Function'', Preprint, arXiv:2201.05201 [math.MG] (2022) Full Text: arXiv OA License
Bruna, Joan; Regev, Oded; Song, Min Jae; Tang, Yi Continuous LWE. (English) Zbl 07765203 Khuller, Samir (ed.) et al., Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, STOC ’21, virtual, Italy, June 21–25, 2021. New York, NY: Association for Computing Machinery (ACM). 694-707 (2021). MSC: 68Qxx PDFBibTeX XMLCite \textit{J. Bruna} et al., in: Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, STOC '21, virtual, Italy, June 21--25, 2021. New York, NY: Association for Computing Machinery (ACM). 694--707 (2021; Zbl 07765203) Full Text: DOI arXiv
Arunachalam, Srinivasan; Regev, Oded; Yao, Penghui On the Gaussian surface area of spectrahedra. arXiv:2112.01463 Preprint, arXiv:2112.01463 [math.PR] (2021). BibTeX Cite \textit{S. Arunachalam} et al., ``On the Gaussian surface area of spectrahedra'', Preprint, arXiv:2112.01463 [math.PR] (2021) Full Text: arXiv OA License
Agarwal, Ishan; Regev, Oded; Tang, Yi Nearly optimal embeddings of flat tori. (English) Zbl 07758345 Byrka, Jarosław (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 23rd international conference, APPROX 2020, and 24th international conference, RANDOM 2020, August 17–19, 2020, Virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 176, Article 43, 14 p. (2020). MSC: 68W20 68W25 90C27 PDFBibTeX XMLCite \textit{I. Agarwal} et al., LIPIcs -- Leibniz Int. Proc. Inform. 176, Article 43, 14 p. (2020; Zbl 07758345) Full Text: DOI arXiv
Naor, Assaf; Rao, Shravas; Regev, Oded Concentration of Markov chains with bounded moments. (English. French summary) Zbl 1511.60107 Ann. Inst. Henri Poincaré, Probab. Stat. 56, No. 3, 2270-2280 (2020). MSC: 60J10 60F10 PDFBibTeX XMLCite \textit{A. Naor} et al., Ann. Inst. Henri Poincaré, Probab. Stat. 56, No. 3, 2270--2280 (2020; Zbl 1511.60107) Full Text: DOI arXiv Euclid
Regev, Oded; Vidick, Thomas Bounds on dimension reduction in the nuclear norm. (English) Zbl 1452.46017 Klartag, Bo’az (ed.) et al., Geometric aspects of functional analysis. Israel seminar (GAFA) 2017–2019. Volume II. Cham: Springer. Lect. Notes Math. 2266, 279-299 (2020). Reviewer: Mikhail Ostrovskii (New York) MSC: 46B85 30L05 46B07 51F30 68R12 PDFBibTeX XMLCite \textit{O. Regev} and \textit{T. Vidick}, Lect. Notes Math. 2266, 279--299 (2020; Zbl 1452.46017) Full Text: DOI arXiv Link
Regev, Shaked; Farago, Oded Application of underdamped Langevin dynamics simulations for the study of diffusion from a drug-eluting stent. (English) Zbl 1514.92031 Physica A 507, 231-239 (2018). MSC: 92C40 60J70 82C31 PDFBibTeX XMLCite \textit{S. Regev} and \textit{O. Farago}, Physica A 507, 231--239 (2018; Zbl 1514.92031) Full Text: DOI arXiv
Friedgut, Ehud; Regev, Oded Kneser graphs are like Swiss cheese. (English) Zbl 1404.05088 Discrete Anal. 2018, Paper No. 2, 18 p. (2018). MSC: 05C35 05D05 PDFBibTeX XMLCite \textit{E. Friedgut} and \textit{O. Regev}, Discrete Anal. 2018, Paper No. 2, 18 p. (2018; Zbl 1404.05088) Full Text: DOI arXiv
Golovnev, Alexander; Regev, Oded; Weinstein, Omri The minrank of random graphs. (English) Zbl 1432.05095 IEEE Trans. Inf. Theory 64, No. 11, 6990-6995 (2018). MSC: 05C80 05C50 60C05 94A29 PDFBibTeX XMLCite \textit{A. Golovnev} et al., IEEE Trans. Inf. Theory 64, No. 11, 6990--6995 (2018; Zbl 1432.05095) Full Text: DOI arXiv
Golovnev, Alexander; Regev, Oded; Weinstein, Omri The minrank of random graphs. (English) Zbl 1467.05244 Jansen, Klaus (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 20th international workshop, APPROX 2017 and 21st international workshop, RANDOM 2017, Berkeley, CA, USA, August 16–18, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 81, Article 46, 13 p. (2017). MSC: 05C80 05C50 60C05 68Q06 94A29 PDFBibTeX XMLCite \textit{A. Golovnev} et al., LIPIcs -- Leibniz Int. Proc. Inform. 81, Article 46, 13 p. (2017; Zbl 1467.05244) Full Text: DOI
Lovett, Shachar; Regev, Oded A counterexample to a strong variant of the polynomial Freiman-Ruzsa conjecture in Euclidean space. (English) Zbl 1404.11010 Discrete Anal. 2017, Paper No. 8, 6 p. (2017). MSC: 11B13 11B30 PDFBibTeX XMLCite \textit{S. Lovett} and \textit{O. Regev}, Discrete Anal. 2017, Paper No. 8, 6 p. (2017; Zbl 1404.11010) Full Text: DOI arXiv
Briët, Jop; Regev, Oded; Saket, Rishi Tight hardness of the non-commutative Grothendieck problem. (English) Zbl 1387.68122 Theory Comput. 13, Paper No. 15, 24 p. (2017). MSC: 68Q17 15A60 32A70 68W25 90C22 PDFBibTeX XMLCite \textit{J. Briët} et al., Theory Comput. 13, Paper No. 15, 24 p. (2017; Zbl 1387.68122) Full Text: DOI arXiv
Regev, Oded; Shapira, Uri; Weiss, Barak Counterexamples to a conjecture of Woods. (English) Zbl 1380.11086 Duke Math. J. 166, No. 13, 2443-2446 (2017). Reviewer: Gabriele Nebe (Aachen) MSC: 11H31 11H06 PDFBibTeX XMLCite \textit{O. Regev} et al., Duke Math. J. 166, No. 13, 2443--2446 (2017; Zbl 1380.11086) Full Text: DOI arXiv Euclid
Regev, Oded; Stephens-Davidowitz, Noah A reverse Minkowski theorem. (English) Zbl 1370.11073 Hatami, Hamed (ed.) et al., Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC ’17, Montreal, QC, Canada, June 19–23, 2017. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4528-6). 941-953 (2017). MSC: 11H06 PDFBibTeX XMLCite \textit{O. Regev} and \textit{N. Stephens-Davidowitz}, in: Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC '17, Montreal, QC, Canada, June 19--23, 2017. New York, NY: Association for Computing Machinery (ACM). 941--953 (2017; Zbl 1370.11073) Full Text: DOI arXiv
Peikert, Chris; Regev, Oded; Stephens-Davidowitz, Noah Pseudorandomness of ring-LWE for any ring and modulus. (English) Zbl 1370.94536 Hatami, Hamed (ed.) et al., Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC ’17, Montreal, QC, Canada, June 19–23, 2017. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4528-6). 461-473 (2017). MSC: 94A60 68Q12 PDFBibTeX XMLCite \textit{C. Peikert} et al., in: Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC '17, Montreal, QC, Canada, June 19--23, 2017. New York, NY: Association for Computing Machinery (ACM). 461--473 (2017; Zbl 1370.94536) Full Text: DOI
Haviv, Ishay; Regev, Oded The restricted isometry property of subsampled Fourier matrices. (English) Zbl 1379.46014 Klartag, Bo’az (ed.) et al., Geometric aspects of functional analysis. Israel seminar (GAFA) 2014–2016. Cham: Springer (ISBN 978-3-319-45281-4/pbk; 978-3-319-45282-1/ebook). Lecture Notes in Mathematics 2169, 163-179 (2017). MSC: 94A12 15A60 60E15 PDFBibTeX XMLCite \textit{I. Haviv} and \textit{O. Regev}, Lect. Notes Math. 2169, 163--179 (2017; Zbl 1379.46014) Full Text: DOI arXiv
Regev, Oded; Stephens-Davidowitz, Noah An inequality for Gaussians on lattices. (English) Zbl 1395.11105 SIAM J. Discrete Math. 31, No. 2, 749-757 (2017). Reviewer: Ranjeet Sehmi (Chandigarh) MSC: 11H06 52C07 PDFBibTeX XMLCite \textit{O. Regev} and \textit{N. Stephens-Davidowitz}, SIAM J. Discrete Math. 31, No. 2, 749--757 (2017; Zbl 1395.11105) Full Text: DOI arXiv
Rao, Shravas; Regev, Oded A Sharp Tail Bound for the Expander Random Sampler. arXiv:1703.10205 Preprint, arXiv:1703.10205 [math.PR] (2017). BibTeX Cite \textit{S. Rao} and \textit{O. Regev}, ``A Sharp Tail Bound for the Expander Random Sampler'', Preprint, arXiv:1703.10205 [math.PR] (2017) Full Text: arXiv OA License
Haviv, Ishay; Regev, Oded The list-decoding size of Fourier-sparse Boolean functions. (English) Zbl 1427.68362 ACM Trans. Comput. Theory 8, No. 3, Article No. 10, 14 p. (2016). MSC: 68W20 68Q25 68Q32 94B35 94D10 PDFBibTeX XMLCite \textit{I. Haviv} and \textit{O. Regev}, ACM Trans. Comput. Theory 8, No. 3, Article No. 10, 14 p. (2016; Zbl 1427.68362) Full Text: DOI Link
Ambainis, Andris; Belovs, Aleksandrs; Regev, Oded; de Wolf, Ronald Efficient quantum algorithms for (gapped) group testing and junta testing. (English) Zbl 1410.68132 Krauthgamer, Robert (ed.), Proceedings of the 27th annual ACM-SIAM symposium on discrete algorithms, SODA 2016, Arlington, VA, USA, January 10–12, 2016. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 903-922 (2016). MSC: 68Q12 68Q25 PDFBibTeX XMLCite \textit{A. Ambainis} et al., in: Proceedings of the 27th annual ACM-SIAM symposium on discrete algorithms, SODA 2016, Arlington, VA, USA, January 10--12, 2016. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 903--922 (2016; Zbl 1410.68132) Full Text: DOI arXiv
Haviv, Ishay; Regev, Oded The restricted isometry property of subsampled Fourier matrices. (English) Zbl 1439.94011 Krauthgamer, Robert (ed.), Proceedings of the 27th annual ACM-SIAM symposium on discrete algorithms, SODA 2016, Arlington, VA, USA, January 10–12, 2016. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 288-297 (2016). MSC: 94A12 15A60 15B52 PDFBibTeX XMLCite \textit{I. Haviv} and \textit{O. Regev}, in: Proceedings of the 27th annual ACM-SIAM symposium on discrete algorithms, SODA 2016, Arlington, VA, USA, January 10--12, 2016. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 288--297 (2016; Zbl 1439.94011) Full Text: DOI
Aggarwal, Divesh; Regev, Oded A note on discrete Gaussian combinations of lattice vectors. (English) Zbl 1375.60062 Chic. J. Theor. Comput. Sci. 2016, Article No. 7, 11 p. (2016). MSC: 60F05 60C05 PDFBibTeX XMLCite \textit{D. Aggarwal} and \textit{O. Regev}, Chic. J. Theor. Comput. Sci. 2016, Article No. 7, 11 p. (2016; Zbl 1375.60062) Full Text: DOI arXiv
Cramer, Ronald; Ducas, Léo; Peikert, Chris; Regev, Oded Recovering short generators of principal ideals in cyclotomic rings. (English) Zbl 1371.94630 Fischlin, Marc (ed.) et al., Advances in cryptology – EUROCRYPT 2016. 35th annual international conference on the theory and applications of cryptographic techniques, Vienna, Austria, May 8–12, 2016. Proceedings. Part II. Berlin: Springer (ISBN 978-3-662-49895-8/pbk; 978-3-662-49896-5/ebook). Lecture Notes in Computer Science 9666, 559-585 (2016). MSC: 94A60 11Y16 PDFBibTeX XMLCite \textit{R. Cramer} et al., Lect. Notes Comput. Sci. 9666, 559--585 (2016; Zbl 1371.94630) Full Text: DOI Link
Regev, Oded; Shinkar, Igor A counterexample to monotonicity of relative mass in random walks. (English) Zbl 1343.60054 Electron. Commun. Probab. 21, Paper No. 8, 8 p. (2016). MSC: 60G50 60J27 05C81 PDFBibTeX XMLCite \textit{O. Regev} and \textit{I. Shinkar}, Electron. Commun. Probab. 21, Paper No. 8, 8 p. (2016; Zbl 1343.60054) Full Text: DOI arXiv Euclid
Tauman Kalai, Yael; Raz, Ran; Regev, Oded On the space complexity of linear programming with preprocessing. (English) Zbl 1334.68105 Proceedings of the 7th ACM conference on innovations in theoretical computer science, ITCS’16, Cambridge, MA, USA, January 14–16, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4057-1). 293-300 (2016). MSC: 68Q25 68Q17 68W25 90C05 PDFBibTeX XMLCite \textit{Y. Tauman Kalai} et al., in: Proceedings of the 7th ACM conference on innovations in theoretical computer science, ITCS'16, Cambridge, MA, USA, January 14--16, 2016. New York, NY: Association for Computing Machinery (ACM). 293--300 (2016; Zbl 1334.68105) Full Text: DOI
Regev, Oded; Umurhan, Orkan M.; Yecko, Philip A. Modern fluid dynamics for physics and astrophysics. (English) Zbl 1339.76004 Graduate Texts in Physics. New York, NY: Springer (ISBN 978-1-4939-3163-7/hbk; 978-1-4939-3164-4/ebook). xxiii, 680 p. (2016). MSC: 76-02 85-02 76Wxx 76Lxx PDFBibTeX XMLCite \textit{O. Regev} et al., Modern fluid dynamics for physics and astrophysics. New York, NY: Springer (2016; Zbl 1339.76004) Full Text: DOI
Regev, Oded A Note on Koldobsky’s Lattice Slicing Inequality. arXiv:1608.04945 Preprint, arXiv:1608.04945 [math.MG] (2016). BibTeX Cite \textit{O. Regev}, ``A Note on Koldobsky's Lattice Slicing Inequality'', Preprint, arXiv:1608.04945 [math.MG] (2016) Full Text: arXiv OA License
Dadush, Daniel; Regev, Oded Towards Strong Reverse Minkowski-type Inequalities for Lattices. arXiv:1606.06913 Preprint, arXiv:1606.06913 [math.MG] (2016). BibTeX Cite \textit{D. Dadush} and \textit{O. Regev}, ``Towards Strong Reverse Minkowski-type Inequalities for Lattices'', Preprint, arXiv:1606.06913 [math.MG] (2016) Full Text: arXiv OA License
Haviv, Ishay; Regev, Oded The list-decoding size of Fourier-sparse Boolean functions. (English) Zbl 1378.94082 Zuckerman, David (ed.), 30th conference on computational complexity, CCC’15, Portland, OR, USA, June 17–19, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-81-1). LIPIcs – Leibniz International Proceedings in Informatics 33, 58-71 (2015). MSC: 94B35 94C10 68Q25 68Q32 68W20 PDFBibTeX XMLCite \textit{I. Haviv} and \textit{O. Regev}, LIPIcs -- Leibniz Int. Proc. Inform. 33, 58--71 (2015; Zbl 1378.94082) Full Text: DOI arXiv
Barak, Boaz; Moitra, Ankur; O’donnell, Ryan; Raghavendra, Prasad; Regev, Oded; Steurer, David; Trevisan, Luca; Vijayaraghavan, Aravindan; Witmer, David; Wright, John Beating the random assignment on constraint satisfaction problems of bounded degree. (English) Zbl 1375.68102 Garg, Naveen (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. Proceedings of the 18th international workshop on approximation algorithms for combinatorial optimization problems (APPROX 2015) and the 19th international workshop on randomization and computation (RANDOM 2015), Princeton, NJ, USA, August 24–26, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-89-7). LIPIcs – Leibniz International Proceedings in Informatics 40, 110-123 (2015). MSC: 68T20 PDFBibTeX XMLCite \textit{B. Barak} et al., LIPIcs -- Leibniz Int. Proc. Inform. 40, 110--123 (2015; Zbl 1375.68102) Full Text: DOI arXiv
Regev, Oded; Vidick, Thomas Quantum XOR games. (English) Zbl 1348.81177 ACM Trans. Comput. Theory 7, No. 4, Article No. 15, 43 p. (2015). MSC: 81P68 81P40 91A80 PDFBibTeX XMLCite \textit{O. Regev} and \textit{T. Vidick}, ACM Trans. Comput. Theory 7, No. 4, Article No. 15, 43 p. (2015; Zbl 1348.81177) Full Text: DOI arXiv Link
Aggarwal, Divesh; Dadush, Daniel; Regev, Oded; Stephens-Davidowitz, Noah Solving the shortest vector problem in \(2^n\) time using discrete Gaussian sampling (extended abstract). (English) Zbl 1321.68426 Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 733-742 (2015). MSC: 68W20 11Y16 94A60 PDFBibTeX XMLCite \textit{D. Aggarwal} et al., in: Proceedings of the 47th annual ACM symposium on theory of computing, STOC '15, Portland, OR, USA, June 14--17, 2015. New York, NY: Association for Computing Machinery (ACM). 733--742 (2015; Zbl 1321.68426) Full Text: DOI arXiv
Haviv, Ishay; Regev, Oded On the lattice isomorphism problem. (English) Zbl 1421.68085 Chekuri, Chandra (ed.), Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Portland, OR, USA, January 5–7, 2014. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 391-404 (2014). MSC: 68Q25 PDFBibTeX XMLCite \textit{I. Haviv} and \textit{O. Regev}, in: Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Portland, OR, USA, January 5--7, 2014. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 391--404 (2014; Zbl 1421.68085) Full Text: DOI
Naor, Assaf; Regev, Oded Krivine schemes are optimal. (English) Zbl 1317.46010 Proc. Am. Math. Soc. 142, No. 12, 4315-4320 (2014). MSC: 46B07 PDFBibTeX XMLCite \textit{A. Naor} and \textit{O. Regev}, Proc. Am. Math. Soc. 142, No. 12, 4315--4320 (2014; Zbl 1317.46010) Full Text: DOI arXiv
Naor, Assaf; Regev, Oded; Vidick, Thomas Efficient rounding for the noncommutative Grothendieck inequality. (English) Zbl 1302.68323 Theory Comput. 10, Paper No. 11, 257-295 (2014). Reviewer: Frank Werner (Magdeburg) MSC: 68W25 90C22 68Q25 68W40 PDFBibTeX XMLCite \textit{A. Naor} et al., Theory Comput. 10, Paper No. 11, 257--295 (2014; Zbl 1302.68323) Full Text: DOI arXiv
Regev, Oded; Vidick, Thomas Elementary proofs of Grothendieck theorems for completely bounded norms. (English) Zbl 1349.46062 J. Oper. Theory 71, No. 2, 491-506 (2014). Reviewer: Florin P. Boca (Urbana) MSC: 46L07 47L25 PDFBibTeX XMLCite \textit{O. Regev} and \textit{T. Vidick}, J. Oper. Theory 71, No. 2, 491--506 (2014; Zbl 1349.46062) Full Text: DOI arXiv Link
Brakerski, Zvika; Langlois, Adeline; Peikert, Chris; Regev, Oded; Stehlé, Damien Classical hardness of learning with errors. (English) Zbl 1293.68159 Proceedings of the 45th annual ACM symposium on theory of computing, STOC ’13. Palo Alto, CA, USA, June 1–4, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2029-0). 575-584 (2013). MSC: 68Q25 68Q17 94A60 PDFBibTeX XMLCite \textit{Z. Brakerski} et al., in: Proceedings of the 45th annual ACM symposium on theory of computing, STOC '13. Palo Alto, CA, USA, June 1--4, 2013. New York, NY: Association for Computing Machinery (ACM). 575--584 (2013; Zbl 1293.68159) Full Text: DOI arXiv
Naor, Assaf; Regev, Oded; Vidick, Thomas Efficient rounding for the noncommutative Grothendieck inequality. (English) Zbl 1293.68151 Proceedings of the 45th annual ACM symposium on theory of computing, STOC ’13. Palo Alto, CA, USA, June 1–4, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2029-0). 71-80 (2013). MSC: 68Q17 68W25 90C22 PDFBibTeX XMLCite \textit{A. Naor} et al., in: Proceedings of the 45th annual ACM symposium on theory of computing, STOC '13. Palo Alto, CA, USA, June 1--4, 2013. New York, NY: Association for Computing Machinery (ACM). 71--80 (2013; Zbl 1293.68151) Full Text: DOI Link
Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded On ideal lattices and learning with errors over rings. (English) Zbl 1281.68140 J. ACM 60, No. 6, Article No. 43, 35 p. (2013). MSC: 68P25 94A60 81P94 68Q17 PDFBibTeX XMLCite \textit{V. Lyubashevsky} et al., J. ACM 60, No. 6, Article No. 43, 35 p. (2013; Zbl 1281.68140) Full Text: DOI
Regev, Oded Entropy-based bounds on dimension reduction in \(L^1\). (English) Zbl 1311.68176 Isr. J. Math. 195, Part B, 825-832 (2013). MSC: 68U05 68Q17 68R10 94A17 PDFBibTeX XMLCite \textit{O. Regev}, Isr. J. Math. 195, Part B, 825--832 (2013; Zbl 1311.68176) Full Text: DOI arXiv
Haviv, Ishay; Regev, Oded The Euclidean distortion of flat tori. (English) Zbl 1279.46014 J. Topol. Anal. 5, No. 2, 205-223 (2013). MSC: 46B85 PDFBibTeX XMLCite \textit{I. Haviv} and \textit{O. Regev}, J. Topol. Anal. 5, No. 2, 205--223 (2013; Zbl 1279.46014) Full Text: DOI arXiv
Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded A toolkit for ring-LWE cryptography. (English) Zbl 1300.94082 Johansson, Thomas (ed.) et al., Advances in cryptology – EUROCRYPT 2013. 32nd annual international conference on the theory and applications of cryptographic techniques, Athens, Greece, May 26–30, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-38347-2/pbk). Lecture Notes in Computer Science 7881, 35-54 (2013). MSC: 94A60 PDFBibTeX XMLCite \textit{V. Lyubashevsky} et al., Lect. Notes Comput. Sci. 7881, 35--54 (2013; Zbl 1300.94082) Full Text: DOI
Buhrman, Harry; Regev, Oded; Scarpa, Giannicola; de Wolf, Ronald Near-optimal and explicit Bell inequality violations. (English) Zbl 1298.81034 Theory Comput. 8, Paper No. 27, 623-645 (2012). MSC: 81P45 81P40 68Q12 91A05 42A16 PDFBibTeX XMLCite \textit{H. Buhrman} et al., Theory Comput. 8, Paper No. 27, 623--645 (2012; Zbl 1298.81034) Full Text: DOI arXiv
Haviv, Ishay; Regev, Oded Hardness of the covering radius problem on lattices. (English) Zbl 1286.68192 Chic. J. Theor. Comput. Sci. 2012, Article No. 4, 12 p. (2012). MSC: 68Q17 PDFBibTeX XMLCite \textit{I. Haviv} and \textit{O. Regev}, Chic. J. Theor. Comput. Sci. 2012, Article No. 4, 12 p. (2012; Zbl 1286.68192) Full Text: DOI arXiv
Chakrabarti, Amit; Regev, Oded An optimal lower bound on the communication complexity of gap-Hamming-distance. (English) Zbl 1259.68087 SIAM J. Comput. 41, No. 5, 1299-1317 (2012). MSC: 68Q25 68Q87 94A05 PDFBibTeX XMLCite \textit{A. Chakrabarti} and \textit{O. Regev}, SIAM J. Comput. 41, No. 5, 1299--1317 (2012; Zbl 1259.68087) Full Text: DOI arXiv
Briët, Jop; Naor, Assaf; Regev, Oded Locally decodable codes and the failure of cotype for projective tensor products. (English) Zbl 1262.46008 Electron. Res. Announc. Math. Sci. 19, 120-130 (2012). Reviewer: T.S.S.R.K. Rao (Bangalore) MSC: 46B07 46B28 PDFBibTeX XMLCite \textit{J. Briët} et al., Electron. Res. Announc. Math. Sci. 19, 120--130 (2012; Zbl 1262.46008) Full Text: DOI arXiv
Regev, Oded Bell violations through independent bases games. (English) Zbl 1268.81038 Quantum Inf. Comput. 12, No. 1-2, 9-20 (2012). MSC: 81P45 81P70 91A05 PDFBibTeX XMLCite \textit{O. Regev}, Quantum Inf. Comput. 12, No. 1--2, 9--20 (2012; Zbl 1268.81038) Full Text: arXiv
Haviv, Ishay; Regev, Oded Tensor-based hardness of the shortest vector problem to within almost polynomial factors. (English) Zbl 1253.68152 Theory Comput. 8, Paper No. 23, 513-531 (2012). MSC: 68Q17 52C07 11H06 11H31 05B40 PDFBibTeX XMLCite \textit{I. Haviv} and \textit{O. Regev}, Theory Comput. 8, Paper No. 23, 513--531 (2012; Zbl 1253.68152) Full Text: DOI arXiv
Regev, Oded Chaos and complexity in astrophysics. (English) Zbl 1263.37001 Cambridge: Cambridge University Press (ISBN 978-1-107-40654-4/pbk; 978-0-511-83941-2/ebook). xii, 455 p. (2012). Reviewer: Gasanbek T. Arazov (Baku) MSC: 37-01 37D45 37N20 85-01 85A99 PDFBibTeX XMLCite \textit{O. Regev}, Chaos and complexity in astrophysics. Cambridge: Cambridge University Press (2012; Zbl 1263.37001) Full Text: DOI arXiv
Chakrabarti, Amit; Regev, Oded An optimal lower bound on the communication complexity of gap-Hamming-distance. (English) Zbl 1288.90005 Proceedings of the 43rd annual ACM symposium on theory of computing, STOC ’11. San Jose, CA, USA, June 6–8, 2011. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0691-1). 51-60 (2011). MSC: 90B18 68Q17 90C27 94A17 PDFBibTeX XMLCite \textit{A. Chakrabarti} and \textit{O. Regev}, in: Proceedings of the 43rd annual ACM symposium on theory of computing, STOC '11. San Jose, CA, USA, June 6--8, 2011. New York, NY: Association for Computing Machinery (ACM). 51--60 (2011; Zbl 1288.90005) Full Text: DOI arXiv
Regev, Oded; Klartag, Bo’az Quantum one-way communication can be exponentially stronger than classical communication. (English) Zbl 1288.68074 Proceedings of the 43rd annual ACM symposium on theory of computing, STOC ’11. San Jose, CA, USA, June 6–8, 2011. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0691-1). 31-40 (2011). MSC: 68Q12 68Q17 81P45 81P68 PDFBibTeX XMLCite \textit{O. Regev} and \textit{B. Klartag}, in: Proceedings of the 43rd annual ACM symposium on theory of computing, STOC '11. San Jose, CA, USA, June 6--8, 2011. New York, NY: Association for Computing Machinery (ACM). 31--40 (2011; Zbl 1288.68074) Full Text: DOI arXiv
Kempe, Julia; Regev, Oded; Unger, Falk; de Wolf, Ronald Upper bounds on the noise threshold for fault-tolerant quantum computing. (English) Zbl 1237.81052 Quantum Inf. Comput. 10, No. 5-6, 361-376 (2010). MSC: 81P68 94B60 60H40 PDFBibTeX XMLCite \textit{J. Kempe} et al., Quantum Inf. Comput. 10, No. 5--6, 361--376 (2010; Zbl 1237.81052)
Kempe, Julia; Regev, Oded; Toner, Ben Unique games with entangled provers are easy. (English) Zbl 1244.68040 SIAM J. Comput. 39, No. 7, 3207-3229 (2010). MSC: 68Q25 81P40 90C22 PDFBibTeX XMLCite \textit{J. Kempe} et al., SIAM J. Comput. 39, No. 7, 3207--3229 (2010; Zbl 1244.68040) Full Text: DOI arXiv
Chakrabarti, Amit; Regev, Oded An optimal randomized cell probe lower bound for approximate nearest neighbor searching. (English) Zbl 1207.68156 SIAM J. Comput. 39, No. 5, 1919-1940 (2010). MSC: 68Q17 68P05 PDFBibTeX XMLCite \textit{A. Chakrabarti} and \textit{O. Regev}, SIAM J. Comput. 39, No. 5, 1919--1940 (2010; Zbl 1207.68156) Full Text: DOI
Regev, Oded Learning with errors over rings. (Abstract). (English) Zbl 1231.94055 Hanrot, Guillaume (ed.) et al., Algorithmic number theory. 9th international symposium, ANTS-IX, Nancy, France, July 19–23, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-14517-9/pbk). Lecture Notes in Computer Science 6197, 3 (2010). MSC: 94A60 PDFBibTeX XMLCite \textit{O. Regev}, Lect. Notes Comput. Sci. 6197, 3 (2010; Zbl 1231.94055) Full Text: DOI
Brody, Joshua; Chakrabarti, Amit; Regev, Oded; Vidick, Thomas; de Wolf, Ronald Better gap-Hamming lower bounds via better round elimination. (English) Zbl 1305.68091 Serna, Maria (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 13th international workshop, APPROX 2010, and 14th international workshop, RANDOM 2010, Barcelona, Spain, September 1–3, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-15368-6/pbk). Lecture Notes in Computer Science 6302, 476-489 (2010). MSC: 68Q17 68Q05 PDFBibTeX XMLCite \textit{J. Brody} et al., Lect. Notes Comput. Sci. 6302, 476--489 (2010; Zbl 1305.68091) Full Text: DOI Link
Haviv, Ishay; Regev, Oded The Euclidean distortion of flat tori. (English) Zbl 1305.68236 Serna, Maria (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 13th international workshop, APPROX 2010, and 14th international workshop, RANDOM 2010, Barcelona, Spain, September 1–3, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-15368-6/pbk). Lecture Notes in Computer Science 6302, 232-245 (2010). MSC: 68U05 PDFBibTeX XMLCite \textit{I. Haviv} and \textit{O. Regev}, Lect. Notes Comput. Sci. 6302, 232--245 (2010; Zbl 1305.68236) Full Text: DOI
Gama, Nicolas; Nguyen, Phong Q.; Regev, Oded Lattice enumeration using extreme pruning. (English) Zbl 1280.94056 Gilbert, Henri (ed.), Advances in cryptology – EUROCRYPT 2010. 29th annual international conference on the theory and applications of cryptographic techniques, French Riviera, May 30 – June 3, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-13189-9/pbk). Lecture Notes in Computer Science 6110, 257-278 (2010). MSC: 94A60 PDFBibTeX XMLCite \textit{N. Gama} et al., Lect. Notes Comput. Sci. 6110, 257--278 (2010; Zbl 1280.94056) Full Text: DOI
Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded On ideal lattices and learning with errors over rings. (English) Zbl 1279.94099 Gilbert, Henri (ed.), Advances in cryptology – EUROCRYPT 2010. 29th annual international conference on the theory and applications of cryptographic techniques, French Riviera, May 30 – June 3, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-13189-9/pbk). Lecture Notes in Computer Science 6110, 1-23 (2010). MSC: 94A60 68P25 81P94 68Q17 PDFBibTeX XMLCite \textit{V. Lyubashevsky} et al., Lect. Notes Comput. Sci. 6110, 1--23 (2010; Zbl 1279.94099) Full Text: DOI
Regev, Oded On the complexity of lattice problems with polynomial approximation factors. (English) Zbl 1237.68102 Nguyen, Phong Q. (ed.) et al., The LLL algorithm. Survey and applications. Dordrecht: Springer (ISBN 978-3-642-02294-4/hbk; 978-3-642-02295-1/ebook). Information Security and Cryptography, 475-496 (2010). MSC: 68Q25 68Q17 11Y16 PDFBibTeX XMLCite \textit{O. Regev}, in: The LLL algorithm. Survey and applications. Dordrecht: Springer. 475--496 (2010; Zbl 1237.68102) Full Text: DOI
Regev, Oded On lattices, learning with errors, random linear codes, and cryptography. (English) Zbl 1325.68101 J. ACM 56, No. 6, Article No. 34, 40 p. (2009). MSC: 68Q17 11H71 68Q12 81P68 94A60 94B05 PDFBibTeX XMLCite \textit{O. Regev}, J. ACM 56, No. 6, Article No. 34, 40 p. (2009; Zbl 1325.68101) Full Text: DOI
Regev, Oded; Toner, Ben Simulating quantum correlations with finite communication. (English) Zbl 1205.68181 SIAM J. Comput. 39, No. 4, 1562-1580 (2009). MSC: 68Q25 68Q10 81P68 PDFBibTeX XMLCite \textit{O. Regev} and \textit{B. Toner}, SIAM J. Comput. 39, No. 4, 1562--1580 (2009; Zbl 1205.68181) Full Text: DOI arXiv Link
Dinur, Irit; Mossel, Elchanan; Regev, Oded Conditional hardness for approximate coloring. (English) Zbl 1192.68317 SIAM J. Comput. 39, No. 3, 843-873 (2009). MSC: 68Q17 68R10 PDFBibTeX XMLCite \textit{I. Dinur} et al., SIAM J. Comput. 39, No. 3, 843--873 (2009; Zbl 1192.68317) Full Text: DOI
Rebusco, P.; Umurhan, O. M.; Kluźniak, W.; Regev, O. Global transient dynamics of three-dimensional hydrodynamical disturbances in a thin viscous accretion disk. (English) Zbl 1183.76431 Phys. Fluids 21, No. 7, Paper No. 076601, 20 p. (2009). MSC: 76-XX PDFBibTeX XMLCite \textit{P. Rebusco} et al., Phys. Fluids 21, No. 7, Paper No. 076601, 20 p. (2009; Zbl 1183.76431) Full Text: DOI arXiv
Gavinsky, Dmitry; Kempe, Julia; Regev, Oded; de Wolf, Ronald Bounded-error quantum state identification and exponential separations in communication complexity. (English) Zbl 1197.81087 SIAM J. Comput. 39, No. 1, 1-24 (2009). Reviewer: Nicolae Constantinescu (Craiova) MSC: 81P68 81P45 94A13 94B60 68Q30 PDFBibTeX XMLCite \textit{D. Gavinsky} et al., SIAM J. Comput. 39, No. 1, 1--24 (2009; Zbl 1197.81087) Full Text: DOI arXiv
Bahturin, Yuri; Regev, Amitai; Zeilberger, Doron Commutation relations and Vandermonde determinants. (English) Zbl 1168.15002 Eur. J. Comb. 30, No. 5, 1271-1276 (2009). Reviewer: Václav Burjan (Praha) MSC: 15A15 15A27 15A30 15A69 PDFBibTeX XMLCite \textit{Y. Bahturin} et al., Eur. J. Comb. 30, No. 5, 1271--1276 (2009; Zbl 1168.15002) Full Text: DOI
Bahturin, Yuri; Regev, Amitai Graded tensor products. (English) Zbl 1186.16013 J. Pure Appl. Algebra 213, No. 9, 1643-1650 (2009). Reviewer: Plamen Koshlukov (Campinas) MSC: 16R50 16R10 16W50 16T10 16D70 15A75 PDFBibTeX XMLCite \textit{Y. Bahturin} and \textit{A. Regev}, J. Pure Appl. Algebra 213, No. 9, 1643--1650 (2009; Zbl 1186.16013) Full Text: DOI
Nguyen, Phong Q.; Regev, Oded Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures. (English) Zbl 1159.94369 J. Cryptology 22, No. 2, 139-160 (2009). MSC: 94A60 94A62 PDFBibTeX XMLCite \textit{P. Q. Nguyen} and \textit{O. Regev}, J. Cryptology 22, No. 2, 139--160 (2009; Zbl 1159.94369) Full Text: DOI
Haviv, Ishay; Lyubashevsky, Vadim; Regev, Oded A note on the distribution of the distance from a lattice. (English) Zbl 1163.68040 Discrete Comput. Geom. 41, No. 1, 162-176 (2009). MSC: 68U05 PDFBibTeX XMLCite \textit{I. Haviv} et al., Discrete Comput. Geom. 41, No. 1, 162--176 (2009; Zbl 1163.68040) Full Text: DOI
Micciancio, Daniele; Regev, Oded Lattice-based cryptography. (English) Zbl 1161.81324 Bernstein, Daniel J. (ed.) et al., Post-quantum cryptography. First international workshop PQCrypto 2006, Leuven, The Netherland, May 23–26, 2006. Selected papers. Berlin: Springer (ISBN 978-3-540-88701-0/hbk; 978-3-540-88702-7/ebook). 147-191 (2009). MSC: 81P68 94A60 PDFBibTeX XMLCite \textit{D. Micciancio} and \textit{O. Regev}, in: Post-quantum cryptography. First international workshop PQCrypto 2006, Leuven, The Netherland, May 23--26, 2006. Selected papers. Berlin: Springer. 147--191 (2009; Zbl 1161.81324) Full Text: DOI
Gavinsky, Dmitry; Regev, Oded; de Wolf, Ronald Simultaneous communication protocols with quantum and classical messages. (English) Zbl 1286.68019 Chic. J. Theor. Comput. Sci. 2008, Article No. 7, 11 p. (2008). MSC: 68M12 81P45 PDFBibTeX XMLCite \textit{D. Gavinsky} et al., Chic. J. Theor. Comput. Sci. 2008, Article No. 7, 11 p. (2008; Zbl 1286.68019) Full Text: DOI arXiv
Regev, A.; Agnon, Y.; Stiassnie, M.; Gramstad, O. Sea-swell interaction as a mechanism for the generation of freak waves. (English) Zbl 1182.76625 Phys. Fluids 20, No. 11, Paper No. 112102, 8 p. (2008). MSC: 76-XX PDFBibTeX XMLCite \textit{A. Regev} et al., Phys. Fluids 20, No. 11, Paper No. 112102, 8 p. (2008; Zbl 1182.76625) Full Text: DOI Link
Aharonov, Dorit; van Dam, Wim; Kempe, Julia; Landau, Zeph; Lloyd, Seth; Regev, Oded Adiabatic quantum computation is equivalent to standard quantum computation. (English) Zbl 1152.81008 SIAM Rev. 50, No. 4, 755-787 (2008). MSC: 81P68 68Q05 PDFBibTeX XMLCite \textit{D. Aharonov} et al., SIAM Rev. 50, No. 4, 755--787 (2008; Zbl 1152.81008) Full Text: DOI arXiv
Sternberg, A.; Umurhan, O. M.; Gil, Y.; Regev, O. Hydrodynamic response of rotationally supported flows in the small shearing box model. (English) Zbl 1147.85002 Astron. Astrophys. 486, No. 2, 341-345 (2008). MSC: 85A30 85A15 PDFBibTeX XMLCite \textit{A. Sternberg} et al., Astron. Astrophys. 486, No. 2, 341--345 (2008; Zbl 1147.85002) Full Text: DOI arXiv
Eldar, Lior; Regev, Oded Quantum SAT for a qutrit-cinquit pair is QMA\(_{1}\)-complete. (English) Zbl 1153.81465 Aceto, Luca (ed.) et al., Automata, languages and programming. 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008. Proceedings, Part I. Berlin: Springer (ISBN 978-3-540-70574-1/pbk). Lecture Notes in Computer Science 5125, 881-892 (2008). MSC: 81P68 PDFBibTeX XMLCite \textit{L. Eldar} and \textit{O. Regev}, Lect. Notes Comput. Sci. 5125, 881--892 (2008; Zbl 1153.81465) Full Text: DOI
Kempe, Julia; Regev, Oded; Unger, Falk; de Wolf, Ronald Upper bounds on the noise threshold for fault-tolerant quantum computing. (English) Zbl 1153.81467 Aceto, Luca (ed.) et al., Automata, languages and programming. 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008. Proceedings, Part I. Berlin: Springer (ISBN 978-3-540-70574-1/pbk). Lecture Notes in Computer Science 5125, 845-856 (2008). MSC: 81P68 PDFBibTeX XMLCite \textit{J. Kempe} et al., Lect. Notes Comput. Sci. 5125, 845--856 (2008; Zbl 1153.81467) Full Text: DOI arXiv
Regev, Oded; Schiff, Liron Impossibility of a quantum speed-up with a faulty oracle. (English) Zbl 1153.68365 Aceto, Luca (ed.) et al., Automata, languages and programming. 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008. Proceedings, Part I. Berlin: Springer (ISBN 978-3-540-70574-1/pbk). Lecture Notes in Computer Science 5125, 773-781 (2008). MSC: 68P10 81P68 PDFBibTeX XMLCite \textit{O. Regev} and \textit{L. Schiff}, Lect. Notes Comput. Sci. 5125, 773--781 (2008; Zbl 1153.68365) Full Text: DOI arXiv
Dinur, Irit; Friedgut, Ehud; Regev, Oded Independent sets in graph powers are almost contained in juntas. (English) Zbl 1147.05058 Geom. Funct. Anal. 18, No. 1, 77-97 (2008). MSC: 05D05 PDFBibTeX XMLCite \textit{I. Dinur} et al., Geom. Funct. Anal. 18, No. 1, 77--97 (2008; Zbl 1147.05058) Full Text: DOI
Regev, O.; Umurhan, O. M. On the viability of the shearing box approximation for numerical studies of MHD turbulence in accretion disks. (English) Zbl 1140.85314 Astron. Astrophys. 481, No. 1, 21-32 (2008). MSC: 85A30 85A15 PDFBibTeX XMLCite \textit{O. Regev} and \textit{O. M. Umurhan}, Astron. Astrophys. 481, No. 1, 21--32 (2008; Zbl 1140.85314) Full Text: DOI arXiv
Khot, Subhash; Regev, Oded Vertex cover might be hard to approximate to within \(2 - \varepsilon \). (English) Zbl 1133.68061 J. Comput. Syst. Sci. 74, No. 3, 335-349 (2008). MSC: 68R10 68Q17 68W25 PDFBibTeX XMLCite \textit{S. Khot} and \textit{O. Regev}, J. Comput. Syst. Sci. 74, No. 3, 335--349 (2008; Zbl 1133.68061) Full Text: DOI
Haviv, Ishay; Regev, Oded; Ta-Shma, Amnon On the hardness of satisfiability with bounded occurrences in the polynomial-time hierarchy. (English) Zbl 1213.68311 Theory Comput. 3, Paper No. 3, 45-60 (2007). MSC: 68Q17 03D15 68Q15 PDFBibTeX XMLCite \textit{I. Haviv} et al., Theory Comput. 3, Paper No. 3, 45--60 (2007; Zbl 1213.68311) Full Text: DOI arXiv
Haviv, Ishay; Regev, Oded Tensor-based hardness of the shortest vector problem to within almost polynomial factors. (English) Zbl 1232.68066 STOC’07. Proceedings of the 39th annual ACM symposium on theory of computing, San Diego, CA, USA, June 11–13, 2007. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-59593-631-8). 469-477 (2007). MSC: 68Q17 68W25 68Q25 52C07 PDFBibTeX XMLCite \textit{I. Haviv} and \textit{O. Regev}, in: Proceedings of the 39th annual ACM symposium on theory of computing, STOC 2007. San Diego, CA, USA, June 11--13, 2007. New York, NY: Association for Computing Machinery (ACM). 469--477 (2007; Zbl 1232.68066)
Micciancio, Daniele; Regev, Oded Worst-case to average-case reductions based on Gaussian measures. (English) Zbl 1142.68037 SIAM J. Comput. 37, No. 1, 267-302 (2007). MSC: 68Q25 11H06 PDFBibTeX XMLCite \textit{D. Micciancio} and \textit{O. Regev}, SIAM J. Comput. 37, No. 1, 267--302 (2007; Zbl 1142.68037) Full Text: DOI
Aharonov, Dorit; Van Dam, Wim; Kempe, Julia; Landau, Zeph; Lloyd, Seth; Regev, Oded Adiabatic quantum computation is equivalent to standard quantum computation. (English) Zbl 1134.81009 SIAM J. Comput. 37, No. 1, 166-194 (2007). MSC: 81P68 68Q05 70H11 68Q99 82B20 PDFBibTeX XMLCite \textit{D. Aharonov} et al., SIAM J. Comput. 37, No. 1, 166--194 (2007; Zbl 1134.81009) Full Text: DOI arXiv
Gavinsky, Dmitry; Kempe, Julia; Regev, Oded; de Wolf, Ronald Bounded-error quantum state identification and exponential separations in communication complexity. (English) Zbl 1301.81045 Kleinberg, Jon M. (ed.), Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21–23, 2006. New York, NY: ACM Press (ISBN 1-59593-134-1). 594-603 (2006). MSC: 81P68 81P45 68Q05 68Q30 PDFBibTeX XMLCite \textit{D. Gavinsky} et al., in: Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21--23, 2006. New York, NY: ACM Press. 594--603 (2006; Zbl 1301.81045) Full Text: DOI Link
Regev, Oded; Rosen, Ricky Lattice problems and norm embeddings. (English) Zbl 1301.68151 Kleinberg, Jon M. (ed.), Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21–23, 2006. New York, NY: ACM Press (ISBN 1-59593-134-1). 447-456 (2006). MSC: 68Q17 11H06 68Q25 PDFBibTeX XMLCite \textit{O. Regev} and \textit{R. Rosen}, in: Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21--23, 2006. New York, NY: ACM Press. 447--456 (2006; Zbl 1301.68151) Full Text: DOI
Dinur, Irit; Mossel, Elchanan; Regev, Oded Conditional hardness for approximate coloring. (English) Zbl 1301.68143 Kleinberg, Jon M. (ed.), Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21–23, 2006. New York, NY: ACM Press (ISBN 1-59593-134-1). 344-353 (2006). MSC: 68Q17 05C15 68Q25 PDFBibTeX XMLCite \textit{I. Dinur} et al., in: Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21--23, 2006. New York, NY: ACM Press. 344--353 (2006; Zbl 1301.68143) Full Text: DOI arXiv
Mossel, Elchanan; O’Donnell, Ryan; Regev, Oded; Steif, Jeffrey E.; Sudakov, Benny Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality. (English) Zbl 1140.60007 Isr. J. Math. 154, 299-336 (2006). Reviewer: Nicko G. Gamkrelidze (Moskva) MSC: 60C05 60J10 PDFBibTeX XMLCite \textit{E. Mossel} et al., Isr. J. Math. 154, 299--336 (2006; Zbl 1140.60007) Full Text: DOI arXiv
Nguyen, Phong Q.; Regev, Oded Learning a parallelepiped: cryptanalysis of GGH and NTRU signatures. (English) Zbl 1140.94365 Vaudenay, Serge (ed.), Advances in cryptology – EUROCRYPT 2006. 25th annual international conference on the theory and applications of cryptographic techniques, St. Petersburg, Russia, May 28 – June 1, 2006. Proceedings. Berlin: Springer (ISBN 3-540-34546-9/pbk). Lecture Notes in Computer Science 4004, 271-288 (2006). MSC: 94A60 94A62 11T71 PDFBibTeX XMLCite \textit{P. Q. Nguyen} and \textit{O. Regev}, Lect. Notes Comput. Sci. 4004, 271--288 (2006; Zbl 1140.94365) Full Text: DOI
Regev, Oded Lattice-based cryptography. (English) Zbl 1161.94425 Dwork, Cynthia (ed.), Advances in cryptology – CRYPTO 2006. 26th annual international cryptology conference, Santa Barbara, California, USA, August 20–24, 2006. Proceedings. Berlin: Springer (ISBN 3-540-37432-9/pbk). Lecture Notes in Computer Science 4117, 131-141 (2006). MSC: 94A60 PDFBibTeX XMLCite \textit{O. Regev}, Lect. Notes Comput. Sci. 4117, 131--141 (2006; Zbl 1161.94425) Full Text: DOI
Hadas, Ofer; Henke, Anne; Regev, Amitai \(\mathbb Z_2\)-graded number theory. (English) Zbl 1109.20003 Commun. Algebra 34, No. 8, 3077-3095 (2006). Reviewer: Vyacheslav A. Artamonov (Moskva) MSC: 20C05 11A51 20C30 13A02 11N05 11N80 16W50 PDFBibTeX XMLCite \textit{O. Hadas} et al., Commun. Algebra 34, No. 8, 3077--3095 (2006; Zbl 1109.20003) Full Text: DOI
Azar, Yossi; Regev, Oded Combinatorial algorithms for the unsplittable flow problem. (English) Zbl 1092.68116 Algorithmica 44, No. 1, 49-66 (2006). MSC: 68W25 68W05 PDFBibTeX XMLCite \textit{Y. Azar} and \textit{O. Regev}, Algorithmica 44, No. 1, 49--66 (2006; Zbl 1092.68116) Full Text: DOI
Kempe, Julia; Kitaev, Alexei; Regev, Oded The complexity of the local Hamiltonian problem. (English) Zbl 1102.81032 SIAM J. Comput. 35, No. 5, 1070-1097 (2006). MSC: 81P68 68Q17 PDFBibTeX XMLCite \textit{J. Kempe} et al., SIAM J. Comput. 35, No. 5, 1070--1097 (2006; Zbl 1102.81032) Full Text: DOI