Theoretical Computer Scientists Awarded the John von Neumann Theory Prize

Newswise — Computer Science Professors Christos Papadimitriou and Mihalis Yannakakis received the John von Neumann Theory Prize for their research in computational complexity theory that explores the boundaries of efficiently solving decision and optimization problems crucial to operations research and management sciences.

The recipients were presented with the prize at the 2023 INFORMS Annual Meeting in October in Phoenix, AZ. The Institute for Operations Research and the Management Sciences (INFORMS) first awarded the prize in 1975 to honor a body of work that has proven its lasting value in operations research and management sciences. Its criteria encompass significance, innovation, depth, and scientific excellence, allowing for a broad and comprehensive evaluation.

Papadimitriou and Yannakakis first started collaborating while Ph.D. students at Princeton University. They have published over 40 papers together, with 20 of those papers garnering more than 100 citations. Their 1988 paper, “Optimization, Approximation, and Complexity Classes,” introduced a range of new complexity classes and notions of approximation that continue to be studied today. 

Before Yannakakis joined Columbia Engineering in 2004, he spent a year teaching at Stanford University and worked in industry as the director of the computing principles research department at Bell Laboratories and the director of the computing principles research department at Avaya Laboratories. He earned his electrical engineering degree at the National Technical University of Athens and Ph.D. in computer science from Princeton. Yannakakis is a member of the National Academy of Engineering, the National Academy of Sciences, and Academia Europaea. He was awarded the seventh Knuth Prize and the EATCS Distinguished Achievements Award for his contributions to theoretical computer science, and he is a fellow of the Association for Computing Machinery, Bell Laboratories, and the American Academy of Arts and Sciences (AAAS).

Papadimitriou joined Columbia Engineering in 2017 and previously taught at Harvard University, MIT, the National Technical University of Athens, Stanford, the University of California-San Diego, and the University of California-Berkeley. He is the author of multiple textbooks, including Elements of the Theory of Computation, Computational Complexity, and Combinatorial Optimization: Algorithms and Complexity. A member of the National Academy of Sciences and the National Academy of Engineering, Papadimitriou also is a fellow of the American Academy of Arts and Sciences and the recipient of several awards, including the Knuth Prize, the Gödel prize, the EATCS award, IEEE’s John von Neumann Medal, and Technion's 2019 Harvey Prize. He received his B.S. in electrical engineering at Athens Polytechnic and Ph.D. in electrical engineering and computer science from Princeton.