Éva Tardos, the Jacob Gould Schurman Professor of Computer Science at Cornell University, is the winner of the 2023 Knuth Prize for her sustained contributions defining and shaping multiple areas of algorithms, including foundational work in combinatorial algorithms, approximation algorithms, and algorithmic game theory.
Combinatorial Algorithms: Tardos obtained the first strongly polynomial-time algorithm for min-cost network flow, as well as a generalization of this result to a large class of combinatorial linear programs, resolving major open problems in the field. This work bridged discrete optimization and efficient algorithms, and introduced a set of new techniques including a surprising connection to Diophantine approximations. For these contributions, she was awarded the Fulkerson Prize in 1988.
Approximation Algorithms: Tardos and co-authors introduced sophisticated techniques that led to new approaches for approximation algorithms, for problems including facility location, k-medians, clustering, routing, and social network analysis. With Plotkin and Shmoys, Tardos introduced new techniques using multiplicative weight updates, a form of Lagrangian relaxation that has found widespread application across many areas of computing. With Lenstra and Shmoys, she developed new structural rounding techniques that have since been applied to a broad range of problems. In work that has been cited almost 10,000 times so far, Kempe, Kleinberg, and Tardos used submodular function maximization to study the spread of influence in networks.
Algorithmic Game Theory: Tardos is credited with being one of the influential founders of algorithmic game theory. Roughgarden and Tardos started the game-theoretic analysis of network traffic with their paper on "selfish routing", which studies the efficiency of equilibria in network traffic. This became one of three foundational papers in algorithmic game theory awarded the Gödel Prize in 2012. Tardos' recent work has contributed to algorithmic game theory in dynamic settings.
In addition to these research contributions, Tardos has provided significant leadership in the field by co-authoring an influential textbook on algorithms, co-editing the main handbook used by the field of algorithmic game theory, serving as editor-in-chief of JACM and the SIAM Journal of Computing, and chairing the program committees of FOCS, SODA, and EC.
Prize Committee:
David Eppstein (UC Irvine)
Monika Henzinger (Chair, IST Austria)
Kurt Mehlhorn (Max Planck Institute)
Dana Randall (Georgia Tech)
Madhu Sudan (Harvard U.)
Moshe Vardi (Rice U.)