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, where he first solved 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]
Due to their similarity as HSP problems, Shor discovered a related factoring problem (Shor's algorithm) that same week for which 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]
Robert Endre Tarjan is an American computer scientist and mathematician. He is the discoverer of several graph theory algorithms, including his strongly connected components algorithm, and co-inventor of both splay trees and Fibonacci heaps. Tarjan is currently the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University.
Madhu Sudan is an Indian-American computer scientist. He has been a Gordon McKay Professor of Computer Science at the Harvard John A. Paulson School of Engineering and Applied Sciences since 2015.
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 and winner of the Turing Award in 2012. She is the RSA Professor of Electrical Engineering and Computer Science at Massachusetts Institute of Technology; a professor of mathematical sciences at the Weizmann Institute of Science, Israel; 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.
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 the late Daniel Lewin in 1998. Leighton discovered a solution to free up web congestion using applied mathematics and distributed computing.
É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.
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.
Umesh Virkumar Vazirani is an Indian–American academic who is the Roger A. Strauch Professor of Electrical Engineering and Computer Science at the University of California, Berkeley, and the director of the Berkeley Quantum Computation Center. His research interests lie primarily in quantum computing. He is also a co-author of a textbook on algorithms.
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.
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.
Cynthia Dwork is an American computer scientist best known for her contributions to cryptography, distributed computing, and algorithmic fairness. She is one of the inventors of differential privacy and proof-of-work.
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.
Noam Nisan is an Israeli computer scientist, a professor of computer science at the Hebrew University of Jerusalem. He is known for his research in computational complexity theory and algorithmic game theory.
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.
