Career
After being awarded his PhD by MIT, he spent one year as a postdoctoral researcher at the University of California, Berkeley, and then accepted a position at Bell Labs in New Providence, New Jersey. It was there he developed Shor's algorithm. This development was inspired by Simon's problem. Shor first found an efficient quantum algorithm for the discrete log problem (which relates point-finding on a hypercube to a torus) and,
"Later that week, I was able to solve the factoring problem as well. There’s a strange relation between discrete log and factoring." [17]
Both of these problems are examples of the HSP. For his work discovering the efficient quantum algorithms for factoring and discrete logarithm he was awarded the Nevanlinna Prize at the 23rd International Congress of Mathematicians in 1998 [18] [19] and the Gödel Prize in 1999. [20] In 1999, he was awarded a MacArthur Fellowship. [21] In 2017, he received the Dirac Medal of the ICTP and for 2019 the BBVA Foundation Frontiers of Knowledge Award in Basic Sciences. [22]
Shor began his MIT position in 2003. Currently, he is the Henry Adams Morss and Henry Adams Morss, Jr. Professor of Applied Mathematics in the Department of Mathematics at MIT. [23] He also is affiliated with CSAIL. [24]
He received a Distinguished Alumni Award from Caltech in 2007. [15]
On October 1, 2011, he was inducted into the American Academy of Arts and Sciences. [25] [26] He was elected as an ACM Fellow in 2019 "for contributions to quantum-computing, information theory, and randomized algorithms". [27] He was elected as a member of the National Academy of Sciences in 2002. [28] In 2020, he was elected a member of the National Academy of Engineering for pioneering contributions to quantum computation. [29]
In an interview published in Nature on October 30, 2020, Shor said that he considers post-quantum cryptography to be a solution to the quantum threat, although a lot of engineering effort is required to switch from vulnerable algorithms. [30]
Along with three others, Shor was awarded the 2023 Breakthrough Prize in Fundamental Physics for "foundational work in the field of quantum information." [9]
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 Interest Group on Algorithms and Computational Theory. The award is named in honor of Kurt Gödel. Gödel's connection to theoretical computer science is that he was the first to mention the "P versus NP" question, in a 1956 letter to John von Neumann in which Gödel asked whether a certain NP-complete problem could be solved in quadratic or linear time.
Shafrira Goldwasser is an Israeli-American computer scientist. A winner of the Turing Award in 2012, she is the RSA Professor of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology; a professor of mathematical sciences at the Weizmann Institute of Science; the director of the Simons Institute for the Theory of Computing at the University of California, Berkeley; and co-founder and chief scientist of Duality Technologies.
Johan Torkel Håstad is a Swedish theoretical computer scientist most known for his work on computational complexity theory. He was the recipient of the Gödel Prize in 1994 and 2011 and the ACM Doctoral Dissertation Award in 1986, among other prizes. He has been a professor in theoretical computer science at KTH Royal Institute of Technology in Stockholm, Sweden since 1988, becoming a full professor in 1992. He is a member of the Royal Swedish Academy of Sciences since 2001.
Jon Michael Kleinberg is an American computer scientist and the Tisch University Professor of Computer Science and Information Science at Cornell University known for his work in algorithms and networks. He is a recipient of the Nevanlinna Prize by the International Mathematical Union.
Silvio Micali is an Italian computer scientist, professor at the Massachusetts Institute of Technology and the founder of Algorand, a proof-of-stake blockchain cryptocurrency protocol. Micali's research at the MIT Computer Science and Artificial Intelligence Laboratory centers on cryptography and information security.
Frank Thomson "Tom" Leighton is an American mathematician who is the CEO of Akamai Technologies, the company he co-founded with Daniel Lewin in 1998, and a professor of applied mathematics at the Massachusetts Institute of Technology (MIT). He is a member of the Computer Science and Artificial Intelligence Laboratory (CSAIL) at MIT.
Éva Tardos is a Hungarian mathematician and the Jacob Gould Schurman Professor of Computer Science at Cornell University.
László "Laci" Babai is a Hungarian professor of computer science and mathematics at the University of Chicago. His research focuses on computational complexity theory, algorithms, combinatorics, and finite groups, with an emphasis on the interactions between these fields.
Aleksandr Aleksandrovich Razborov, sometimes known as Sasha Razborov, is a Soviet and Russian mathematician and computational theorist. He is Andrew McLeish Distinguished Service Professor at the University of Chicago.
ACM SIGACT or SIGACT is the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory, whose purpose is support of research in theoretical computer science. It was founded in 1968 by Patrick C. Fischer.
Noga Alon is an Israeli mathematician and a professor of mathematics at Princeton University noted for his contributions to combinatorics and theoretical computer science, having authored hundreds of papers.
Avi Wigderson is an Israeli computer scientist and mathematician. He is the Herbert H. Maass Professor in the school of mathematics at the Institute for Advanced Study in Princeton, New Jersey, United States of America. His research interests include complexity theory, parallel algorithms, graph theory, cryptography, and distributed computing. Wigderson received the Abel Prize in 2021 for his work in theoretical computer science. He also received the 2023 Turing Award for his contributions to the understanding of randomness in the theory of computation.
Daniel Alan Spielman has been a professor of applied mathematics and computer science at Yale University since 2006. As of 2018, he is the Sterling Professor of Computer Science at Yale. He is also the Co-Director of the Yale Institute for Network Science, since its founding, and chair of the newly established Department of Statistics and Data Science.
The ACM Symposium on Principles of Distributed Computing (PODC) is an academic conference in the field of distributed computing organised annually by the Association for Computing Machinery.
Gábor Tardos is a Hungarian mathematician, currently a professor at Central European University and previously a Canada Research Chair at Simon Fraser University. He works mainly in combinatorics and computer science. He is the younger brother of Éva Tardos.
Nir Shavit is an Israeli computer scientist. He is a professor in the Computer Science Department at Tel Aviv University and a professor of electrical engineering and computer science at the Massachusetts Institute of Technology.
Constantinos Daskalakis is a Greek theoretical computer scientist. He is a professor at MIT's Electrical Engineering and Computer Science department and a member of the MIT Computer Science and Artificial Intelligence Laboratory. He was awarded the Rolf Nevanlinna Prize and the Grace Murray Hopper Award in 2018.
Richard Ryan Williams, known as Ryan Williams, is an American theoretical computer scientist working in computational complexity theory and algorithms.
Leonard J. Y. Schulman is professor of computer science in the Computing and Mathematical Sciences Department at the California Institute of Technology. He is known for work on algorithms, information theory, coding theory, and quantum computation.
Oded Regev is an Israeli-American theoretical computer scientist and mathematician. He is a professor of computer science at the Courant institute at New York University. He is best known for his work in lattice-based cryptography, and in particular for introducing the learning with errors problem.
