Andrew Goldberg | |
---|---|
Born | Andrew Vladislav Goldberg 1960 (age 62–63) |
Alma mater | Massachusetts Institute of Technology (BS, PhD) University of California, Berkeley (MS) |
Awards | ACM Fellow (2009) |
Scientific career | |
Institutions | Amazon Stanford University |
Thesis | Efficient graph algorithms for sequential and parallel computers (1987) |
Doctoral advisor | Charles E. Leiserson [1] |
Doctoral students | Edith Cohen [1] |
Website | avglab |
Andrew Vladislav Goldberg (born 1960) is an American computer scientist working primarily on design, analysis, and experimental evaluation of algorithms. He also worked on mechanism design, computer systems, and complexity theory. [2] Currently he is a Senior Principal Scientist at Amazon.com.
Goldberg did his undergraduate studies at the Massachusetts Institute of Technology, graduating in 1982. After earning a master's degree at the University of California, Berkeley, he returned to MIT with funding from a prestigious Hertz Fellowship, finishing his doctorate there in 1987 with a thesis on the Efficient graph algorithms for sequential and parallel computers [3] supervised by Charles E. Leiserson. [G87] [1]
After completing his PhD, Goldberg was on the faculty of Stanford University and worked for NEC Research Institute, Intertrust STAR Laboratories, and Microsoft Research Silicon Valley Lab. He joined Amazon.com in 2014.[ citation needed ]
Goldberg is best known for his research in the design and analysis of algorithms for graphs and networks, and particularly for his work on the maximum flow problem [GT88] [CG97] [GR98] and shortest path problem, [CGR96] [GH05] including the discovery of the push–relabel maximum flow algorithm. [GT88] He also worked on algorithmic game theory, where he was one of the first scientists to study worst-case mechanism design.
G87. | Goldberg, Andrew V. (1987), Efficient graph algorithms for sequential and parallel computers (Thesis), DSpace@MIT, hdl:1721.1/14912 . |
GT88. | Goldberg, Andrew V.; Tarjan, Robert E. (1988), "A new approach to the maximum-flow problem", Journal of the ACM , 35 (4): 921–940, doi:10.1145/48014.61051, MR 1072405, S2CID 52152408 . |
CGR96. | Cherkassky, Boris V.; Goldberg, Andrew V.; Radzik, Tomasz (1996), "Shortest paths algorithms: theory and experimental evaluation", Mathematical Programming, Series A, 73 (2): 129–174, doi:10.1016/0025-5610(95)00021-6, MR 1392160 . |
CG97. |
GR98. | Goldberg, Andrew V.; Rao, Satish (1998), "Beyond the flow decomposition barrier", Journal of the ACM , 45 (5): 783–797, doi:10.1145/290179.290181, MR 1668151, S2CID 96030 . |
GH05. | Goldberg, Andrew V.; Harrelson, Chris (2005), "Computing the shortest path: A* search meets graph theory", Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '05), pp. 156–165, ISBN 9780898715859 . |
Goldberg holds a number of awards, including a Hertz Fellowship in 1985, the 1988 A.W. Tucker Prize of the Mathematical Optimization Society, [4] 1988 National Science Foundation (NSF) Presidential Young Investigator Award, 1991 ONR Young Investigator Award, and 2011 INFORMS Optimization Society Farkas Prize. [5] In 2012–2013, Goldberg was a Founding Faculty Fellow of the Skolkovo Institute of Science and Technology.
Goldberg was nominated a Fellow of the Association for Computing Machinery (ACM) in 2009 "for contributions to fundamental theoretical and practical problems in the design and analysis of algorithms." [6] In 2013, he became a fellow of the Society for Industrial and Applied Mathematics. [7]
Stephen Arthur Cook is an American-Canadian computer scientist and mathematician who has made significant contributions to the fields of complexity theory and proof complexity. He is a university professor at the University of Toronto, Department of Computer Science and Department of Mathematics.
Robert Endre Tarjan is an American computer scientist and mathematician. He is the discoverer of several graph algorithms, including Tarjan's 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.
Richard Manning Karp is an American computer scientist and computational theorist at the University of California, Berkeley. He is most notable for his research in the theory of algorithms, for which he received a Turing Award in 1985, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto Prize in 2008.
Professor Sartaj Kumar Sahni is a computer scientist based in the United States, and is one of the pioneers in the field of data structures. He is a distinguished professor in the Department of Computer and Information Science and Engineering at the University of Florida.
Éva Tardos is a Hungarian mathematician and the Jacob Gould Schurman Professor of Computer Science at Cornell University.
Vijay Virkumar Vazirani is an Indian American distinguished professor of computer science in the Donald Bren School of Information and Computer Sciences at the University of California, Irvine.
Ravindran Kannan is a Principal Researcher at Microsoft Research India, where he leads the algorithms research group. He is also the first adjunct faculty of Computer Science and Automation Department of Indian Institute of Science.
Mihalis Yannakakis is professor of computer science at Columbia University. He is noted for his work in computational complexity, databases, and other related fields. He won the Donald E. Knuth Prize in 2005.
Kurt Mehlhorn is a German theoretical computer scientist. He has been a vice president of the Max Planck Society and is director of the Max Planck Institute for Computer Science.
Michael Ralph Fellows AC HFRSNZ MAE is a computer scientist and the Elite Professor of Computer Science in the Department of Informatics at the University of Bergen, Norway as of January 2016.
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.
Dimitri Panteli Bertsekas is an applied mathematician, electrical engineer, and computer scientist, a McAfee Professor at the Department of Electrical Engineering and Computer Science in School of Engineering at the Massachusetts Institute of Technology (MIT), Cambridge, Massachusetts, and also a Fulton Professor of Computational Decision Making at Arizona State University, Tempe.
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.
Nimrod Megiddo is a mathematician and computer scientist. He is a research scientist at the IBM Almaden Research Center and Stanford University. His interests include combinatorial optimization, algorithm design and analysis, game theory, and machine learning. He was one of the first people to propose a solution to the bounding sphere and smallest-circle problem.
Nathan (Nati) Linial is an Israeli mathematician and computer scientist, a professor in the Rachel and Selim Benin School of Computer Science and Engineering at the Hebrew University of Jerusalem, and an ISI highly cited researcher.
Michel Xavier Goemans is a Belgian-American professor of applied mathematics and the RSA Professor of Mathematics at MIT working in discrete mathematics and combinatorial optimization at CSAIL and MIT Operations Research Center.
Mohammad Taghi Hajiaghayi is a computer scientist known for his work in algorithms, game theory, social networks, network design, graph theory, and big data. He has over 200 publications with over 185 collaborators and 10 issued patents.
Daniel Mier Gusfield is an American computer scientist, Distinguished Professor of Computer Science at the University of California, Davis. Gusfield is known for his research in combinatorial optimization and computational biology.
The Tucker Prize for outstanding theses in the area of optimization is sponsored by the Mathematical Optimization Society (MOS). Up to three finalists are presented at each (triennial) International Symposium of the MOS. The winner will receive an award of $1000 and a certificate. The Albert W. Tucker Prize was established by the Society in 1985, and was first awarded at the Thirteenth International Symposium on Mathematical Programming in 1988.
Baruch M. Schieber is a Professor of the Department of Computer Science at the New Jersey Institute of Technology (NJIT) and Director of the Institute for Future Technologies.