Oded Regev (Hebrew: עודד רגב) is an Israeli-American

theoretical computer scientist computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumscribe the th ...

and mathematician. He is a professor of computer science at the

Courant institute The Courant Institute of Mathematical Sciences (commonly known as Courant or CIMS) is the mathematics research school of New York University (NYU), and is among the most prestigious mathematics schools and mathematical sciences research cente ...

New York University New York University (NYU) is a private research university in New York City. Chartered in 1831 by the New York State Legislature, NYU was founded by a group of New Yorkers led by then-Secretary of the Treasury Albert Gallatin. In 1832, the ...

. He is best known for his work in

lattice-based cryptography Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof. Lattice-based constructions are currently important candidates for pos ...

, and in particular for introducing the

learning with errors Learning with errors (LWE) is the computational problem of inferring a linear n-ary function f over a finite ring from given samples y_i = f(\mathbf_i) some of which may be erroneous. The LWE problem is conjectured to be hard to solve, and thus to ...

problem.

Biography

Oded Regev earned his B.Sc. in 1995, M.Sc. in 1997, and Ph.D. in 2001, all from

Tel Aviv University Tel Aviv University (TAU) ( he, אוּנִיבֶרְסִיטַת תֵּל אָבִיב, ''Universitat Tel Aviv'') is a public research university in Tel Aviv, Israel. With over 30,000 students, it is the largest university in the country. Locate ...

. He completed his Ph.D. at the age of 21, advised by Yossi Azar, with a thesis titled "Scheduling and Load Balancing." He held faculty positions at

and the

École Normale Supérieure École may refer to: * an elementary school in the French educational stages normally followed by secondary education establishments (collège and lycée) * École (river), a tributary of the Seine flowing in région Île-de-France * École, Savoi ...

before joining the Courant institute.

Work

Regev has done extensive work on lattices. He is best known for introducing the

problem (LWE), for which he won the 2018

Gödel Prize The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Inter ...

. 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 Cryptanalysis (from the Greek ''kryptós'', "hidden", and ''analýein'', "to analyze") refers to the process of analyzing information systems in order to understand hidden aspects of the systems. Cryptanalysis is used to breach cryptographic sec ...

of the GGH and

NTRU NTRU is an open-source public-key cryptosystem that uses lattice-based cryptography to encrypt and decrypt data. It consists of two algorithms: NTRUEncrypt, which is used for encryption, and NTRUSign, which is used for digital signatures. Unli ...

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 In mathematics, Minkowski's theorem is the statement that every convex set in \mathbb^n which is symmetric with respect to the origin and which has volume greater than 2^n contains a non-zero integer point (meaning a point in \Z^n that is not t ...

and exploring its applications in joint works with his student Noah Stephens-Davidowitz and his former postdoc Daniel Dadush. 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 Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Though ...

communication complexity In theoretical computer science, communication complexity studies the amount of communication required to solve a problem when the input to the problem is distributed among two or more parties. The study of communication complexity was first intro ...

hardness of approximation In computer science, hardness of approximation is a field that studies the algorithmic complexity of finding near-optimal solutions to optimization problems. Scope Hardness of approximation complements the study of approximation algorithms by pro ...

online algorithm In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an o ...

combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...

probability Probability is the branch of mathematics concerning numerical descriptions of how likely an Event (probability theory), event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and ...

, and

dimension reduction Dimensionality reduction, or dimension reduction, is the transformation of data from a high-dimensional space into a low-dimensional space so that the low-dimensional representation retains some meaningful properties of the original data, ideally ...

. He has also recently become interested in topics in biology, and particularly

RNA splicing RNA splicing is a process in molecular biology where a newly-made precursor messenger RNA (pre-mRNA) transcript is transformed into a mature messenger RNA (mRNA). It works by removing all the introns (non-coding regions of RNA) and ''splicing'' b ...

. Regev is an associate editor in chief of the journal ''

Theory of Computing ''Theory of Computing'' is a peer-reviewed open access scientific journal covering theoretical computer science. The journal was established in 2005 and is published by the Department of Computer Science of the University of Chicago. The edit ...

,'' and is a co-founder and organizer of the TCS+ online seminar series.

References

{{DEFAULTSORT:Regev, Oded Israeli computer scientists Israeli mathematicians Israeli cryptographers New York University Living people Tel Aviv University alumni Gödel Prize laureates Year of birth missing (living people) 20th-century American mathematicians 21st-century American mathematicians