Christos H. Papadimitriou
Biography
Christos H. Papadimitriou is a leader in providing an understanding of how computational complexity can be used as a tool for understanding limits and solving problems within the broader scientific community, pioneering connections and collaborations between computer science and other disciplines. Papadimitriou has been the key player in the development of the understanding of "NP total search problems,” which are computational challenges where solutions are guaranteed to exist but may be hard to find. He has been very influential in developing algorithmic game theory, which involves the convergence of computer science and economic theory. His work on computing and determining the computational complexity of the Nash equilibrium has provided important insights for game theory and economics. He studied the algorithmic complexity of computing game-theoretic solutions to cooperative and noncooperative game scenarios, which has had important implications for economics and gauging the health of the Internet amid the risks caused by congestion. He defined the “price of anarchy,” which provides a measure of the degree of inefficiency of equilibrium in a game, and is important for quantifying loss due to uncoordinated behavior of selfish agents within networks such as the Internet. Papadimitriou has also demonstrated how computational complexity can be applied to natural processes such as biology, describing the algorithmic aspects of protein structure and providing a mixability theory for the role of sex in evolution. His novels Turing and Logicomix have been very successful in reaching the broader public and exposing many people to some of the fundamental principles and ideas of mathematics and computer science.
An IEEE member and member of the U.S. National Academy of Sciences, the National Academy of Engineering, the American Academy of Arts and Sciences, and an ACM Fellow, Papadimitriou is the C. Lester Hogan Professor of Electrical Engineering and Computer Science with the University of California, Berkeley, CA, USA.
