Eva Tardos

Biography

Eva Tardos has reshaped and renewed the foundations of algorithm design with long-term vision, creativity, and technical strength that is benefitting the Internet through improved resource allocation, network formation, routing and congestion control, and electronic commerce. During a career spanning more than thirty years, Tardos is most known for her work on network-flow algorithms, approximation algorithms, and quantifying the efficiency of selfish routing through the lens of algorithmic game theory. Her solo work on strongly polynomial algorithms was a breakthrough, having resolved a major open problem in the field; in particular, she showed that the minimum-cost flow problem (one of the basic problems in network flow that models the efficient transport of goods through a network) could be solved in strongly polynomial time, with a running time depending only on the number of nodes and edges of the network, not on the magnitudes of its capacities or costs. She then played a pivotal role in establishing the modern use of linear programming in algorithm design to advance the field of approximation algorithms. She has developed approximation algorithms for fundamental problems in a wide range of application areas, including facility location, routing, clustering, classification, and social network analysis.

Tardos’ work has been one of the pillars of algorithmic game theory, a burgeoning field that brings theoretical computer science and economics together to develop algorithmic foundations for our highly connected digital world. Algorithmic game theory is concerned with algorithms designed in the presence of self-interested agents, governed by incentives and economic constraints. Her pioneering work with Tim Roughgarden demonstrated how game-theoretic ideas could quantify the performance gaps between centrally managed network traffic and the flow of traffic directed by self-interested agents. This innovation provided the tools by which computer scientists can analyze the behavior of rational entities in computerized systems and has sparked an enormous amount of further research.

Tardos was born in Budapest, Hungary in 1957. She graduated from Eötvös University with a bachelor’s in mathematics, and a doctorate in 1984. Tardos held several postdoctoral fellowships and visiting positions at the University of Bonn, the Mathematical Sciences Research Institute in Berkeley, at Eötvös University, and MIT. Since 1989, she joined the faculty at Cornell, where she served as chair of the Department of Computer Science 2006-2010 and is currently Senior Associate Dean of Computing and Information Science. A member of the U.S. National Academy of Engineering, National Academy of Sciences, and the American Academy of Arts and Sciences. She was the program committee chair of the IEEE Annual Symposium on Foundations of Computer Science in 2005. She was editor in chief of SIAM Journal of Computing 2003-09 and the editor of Journal of the ACM and Combinatorica.