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. Currently he is a Senior Principal Scientist at

Amazon.com Amazon.com, Inc. ( ) is an American multinational technology company focusing on e-commerce, cloud computing, online advertising, digital streaming, and artificial intelligence. It has been referred to as "one of the most influential economi ...

Education and career

Goldberg did his undergraduate studies at the

Massachusetts Institute of Technology The Massachusetts Institute of Technology (MIT) is a private land-grant research university in Cambridge, Massachusetts. Established in 1861, MIT has played a key role in the development of modern technology and science, and is one of the ...

, graduating in 1982. After earning a master's degree at the

University of California, Berkeley The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California) is a public land-grant research university in Berkeley, California. Established in 1868 as the University of California, it is the state's first land-grant u ...

, 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'' supervised by

Charles E. Leiserson Charles Eric Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof. As part of this effort, he developed the Cilk multithreaded language. H ...

Career and research

After completing his PhD, Goldberg was on the faculty of

Stanford University Stanford University, officially Leland Stanford Junior University, is a private research university in Stanford, California. The campus occupies , among the largest in the United States, and enrolls over 17,000 students. Stanford is consider ...

and worked for NEC Research Institute, Intertrust STAR Laboratories, and Microsoft Research Silicon Valley Lab. He joined Amazon.com in 2014. 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 In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate. The maximum flow problem can be seen as a special case of more complex network flow problems, such ...

and

shortest path problem In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between tw ...

, including the discovery of the

push–relabel maximum flow algorithm In mathematical optimization, the push–relabel algorithm (alternatively, preflow–push algorithm) is an algorithm for computing maximum flows in a flow network. The name "push–relabel" comes from the two basic operations used in the algorithm. ...

. He also worked on

algorithmic game theory Algorithmic game theory (AGT) is an area in the intersection of game theory and computer science, with the objective of understanding and design of algorithms in strategic environments. Typically, in Algorithmic Game Theory problems, the input t ...

, where he was one of the first scientists to study worst-case mechanism design.

Selected publications

Awards and honors

Goldberg holds a number of awards, including a Hertz Fellowship in 1985, the 1988 A.W. Tucker Prize of the

Mathematical Optimization Society The Mathematical Optimization Society (MOS), known as the Mathematical Programming Society until 2010,National Science Foundation The National Science Foundation (NSF) is an independent agency of the United States government that supports fundamental research and education in all the non-medical fields of science and engineering. Its medical counterpart is the National I ...

(NSF) Presidential Young Investigator Award, 1991 ONR Young Investigator Award, and 2011

INFORMS The Institute for Operations Research and the Management Sciences (INFORMS) is an international society for practitioners in the fields of operations research (O.R.), management science, and analytics. It was established in 1995 with the merger of ...

Optimization Society Farkas Prize. In 2012–2013, Goldberg was a Founding Faculty Fellow of the

Skolkovo Institute of Science and Technology The Skolkovo Institute of Science and Technology, or Skoltech, is a private institute located in Moscow, Russia. Skoltech was established in 2011 as part of a multi-year partnership with the Massachusetts Institute of Technology (MIT) Globally ...

. Goldberg was nominated a

Fellow A fellow is a concept whose exact meaning depends on context. In learned or professional societies, it refers to a privileged member who is specially elected in recognition of their work and achievements. Within the context of higher education ...

of the

Association for Computing Machinery The Association for Computing Machinery (ACM) is a US-based international learned society for computing. It was founded in 1947 and is the world's largest scientific and educational computing society. The ACM is a non-profit professional member ...

(ACM) in 2009 "for contributions to fundamental theoretical and practical problems in the design and analysis of algorithms." In 2013, he became a fellow of the

Society for Industrial and Applied Mathematics Society for Industrial and Applied Mathematics (SIAM) is a professional society dedicated to applied mathematics, computational science, and data science through research, publications, and community. SIAM is the world's largest scientific socie ...

References

{{DEFAULTSORT:Goldberg, Andrew V. 1960 births Living people American computer scientists Russian computer scientists Massachusetts Institute of Technology alumni Place of birth missing (living people) University of California, Berkeley alumni Stanford University faculty Fellows of the Society for Industrial and Applied Mathematics 2009 Fellows of the Association for Computing Machinery