Oded Regev (computer scientist)

Oded Regev earned his B.Sc. in 1995, M.Sc. in 1997, and Ph.D. in 2001, all from Tel Aviv University. He completed his Ph.D. at the age of 21, advised by Yossi Azar, with a thesis titled "Scheduling and Load Balancing."{{Cite web|url=https://www.cs.tau.ac.il/thesis/ |title=School of Computer Science Thesis Repository |author= |website=Tel Aviv University - Dept. of Computer Science |access-date=2024-01-16}}{{cite web | title=Scheduling and Load Balancing | last=Regev |first=Oded | website= Tel Aviv University |url=https://primage.tau.ac.il/libraries/theses/exeng/free/1509397_abe.pdf | access-date=2024-01-16}} He held faculty positions at Tel Aviv University and the École Normale Supérieure before joining the Courant institute.{{Cite web|url=https://www.simonsfoundation.org/people/oded-regev/|title=Oded Regev|author= |date=October 5, 2014|website=Simons Foundation}}

Regev has done extensive work on lattices. He is best known for introducing the learning with errors problem (LWE), for which he won the 2018 Gödel Prize.{{cite web | last=Chita | first=Efi | title=2018 Gödel Prize | website=European Association for Theoretical Computer Science (EATCS) | url=https://eatcs.org/index.php/component/content/article/1-news/2670-2018-godel-prize | access-date=2024-01-16}} As the citation reads:

Regev’s work has ushered in a revolution in cryptography, in both theory and practice. On the theoretical side, LWE has served as a simple and yet amazingly versatile foundation for nearly every kind of cryptographic object imaginable—along with many that were unimaginable until recently, and which still have no known constructions without LWE. Toward the practical end, LWE and its direct descendants are at the heart of several efficient real-world cryptosystems.

Regev's most influential other work on lattices includes cryptanalysis of the GGH and NTRU signature schemes in joint work with Phong Q. Nguyen, for which they won a best paper award at Eurocrypt 2006; introducing the ring learning with errors problem in joint work with Chris Peikert and Vadim Lyubashevsky; and proving a converse to Minkowski's theorem and exploring its applications in joint works with his student Noah Stephens-Davidowitz and his former postdoc Daniel Dadush.

{{Cite web|url=https://www.iacr.org/cryptodb/data/bestpapers.php|title=IACR Publication Awards|author= |website=International Association for Cryptologic Research}}

{{cite journal|last1=Nguyen|first1=Phong Q.|last2=Regev|first2=Oded|title=Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures|journal=Journal of Cryptology|volume=22|issue=2|year=2008|pages=139–160|issn=0933-2790|doi=10.1007/s00145-008-9031-0|s2cid=2164840|doi-access=free}}

{{cite book|last1=Lyubashevsky|first1=Vadim|last2=Peikert|first2=Chris|last3=Regev|first3=Oded|title=Advances in Cryptology – EUROCRYPT 2010|chapter=On Ideal Lattices and Learning with Errors over Rings|series=Lecture Notes in Computer Science|volume=6110|year=2010|pages=1–23|issn=0302-9743|doi=10.1007/978-3-642-13190-5_1|isbn=978-3-642-13189-9}}

{{citation

| author1-link =

| last1 = Regev | first1 = Oded

| last2 = Stephens-Davidowitz | first2 = Noah

| title = A reverse Minkowski theorem

| series = Annual ACM SIGACT Symposium on Theory of Computing

| year = 2017

| pages = 941–953

| place = Montreal, Quebec, Canada

| arxiv = 1611.05979

}}

{{cite book|last1=Dadush|first1=Daniel|last2=Regev|first2=Oded|title=2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)|chapter=Towards Strong Reverse Minkowski-Type Inequalities for Lattices|year=2016|pages=447–456|doi=10.1109/FOCS.2016.55|arxiv=1606.06913|isbn=978-1-5090-3933-3|s2cid=16828584}}

In addition to his work on lattices, Regev has also done work in a large number of other areas in theoretical computer science and mathematics. These include quantum computing, communication complexity, hardness of approximation, online algorithms, combinatorics, probability, and dimension reduction. He has also recently become interested in topics in biology, and particularly RNA splicing.{{Cite web|url=https://cims.nyu.edu/~regev/.|title = Oded Regev|author= |website=Courant Institute of Mathematical Sciences }}{{Cite web|url=https://scholar.google.com/citations?user=3-gk0ioAAAAJ&hl=en&oi=ao|title=Oded Regev|website=scholar.google.com}}

Regev is an associate editor in chief of the journal Theory of Computing,{{cite web

| url = https://theoryofcomputing.org/editors.html

| title = Editors

| website =Theory of Computing

| access-date =2024-01-16

}} and is a co-founder and organizer of the TCS+ online seminar series.{{Cite web|url=https://sites.google.com/site/plustcs/|title=TCS+|website=sites.google.com}}

In August 2023 Regev published a preprint{{cite arXiv |last=Regev |first=Oded |date=2023 |title=An Efficient Quantum Factoring Algorithm |eprint=2308.06572|class=quant-ph}}{{Cite report |url=https://www.science.org/content/article/surprising-and-supercool-quantum-algorithm-offers-faster-way-hack-internet-encryption |title='Surprising and super cool.' Quantum algorithm offers faster way to hack internet encryption |date=2023-09-19 |doi=10.1126/science.adk9418 |language=en}}{{Cite web |last=Brubaker |first=Ben |date=2023-10-17 |title=Thirty Years Later, a Speed Boost for Quantum Factoring |url=https://www.quantamagazine.org/thirty-years-later-a-speed-boost-for-quantum-factoring-20231017/ |access-date=2023-10-18 |website=Quanta Magazine |language=en}} describing an algorithm to factor integers with $\backslash sim\; O(n^\{3/2\})$ quantum gates which would be more efficient than Shor's algorithm which uses $\backslash sim\; O(n^\{2\})$, but would require more qubits $\backslash sim\; O(n^\{3/2\})$ of quantum memory against Shor's $\backslash sim\; O(n)\backslash$. A variant has been proposed{{Cite arXiv |last1=Ragavan |first1=Seyoon |last2=Vaikuntanathan |first2=Vinod |date=2023 |title=Optimizing Space in Regev's Factoring Algorithm |eprint=2310.00899|class=quant-ph}} that could reduce the space to around the same amount.

{{Reflist}}

{{Authority control}}

{{DEFAULTSORT:Regev, Oded}}

Category:Israeli computer scientists

Category:Israeli mathematicians

Category:Israeli cryptographers

Category:New York University faculty

Category:Silver professors

Category:Living people

Category:Tel Aviv University alumni

Category:Gödel Prize laureates

Category:Year of birth missing (living people)

Category:20th-century American mathematicians

Category:21st-century American mathematicians