People of ACM - Éva Tardos

June 21, 2022

How did your PhD degree in mathematics from Eotvos University, Budapest, lead to a career in theoretical computer science?

Theoretical computer science is dealing with topics raised by computer systems but working on mathematical models with the goal of understanding how to design these systems. My PhD in mathematics was focusing on algorithms and was at the interface of mathematics and (theoretical) computer science. After a postdoc at Berkeley with the Mathematical Sciences Research Institute focusing on theoretical computer science, I found a natural home in the theoretical computer science community.

Your contributions in combinatorial optimization included introducing a new algorithm for the minimum cost flow problem. What is the minimum cost flow problem, and how did your algorithm break new ground in this area?

The classical maximum flow problem concerns designing transportation of goods in a network, aiming to get the goods from a source to a given destination obeying capacities on the edges. This formulation of the problem ignores that transportation has cost and using different routes will affect the cost of the resulting solution. The minimum cost flow problem is the natural extension of the maximum flow problem where the goal is to find a flow that has low cost. Maximum flow algorithms have running times that can be bounded by the size of the network. In contrast, before my work, algorithms for the minimum cost version worked directly with the digits of the numbers involved in either the costs or the capacities, and the running time grew as the numbers have more significant digits. My new algorithm is strongly polynomial, with a running time that depends on the size of the network only. It is one of the outstanding open problems in this area if such an algorithm is possible for the class of all linear programs.

Your work in selfish routing was recognized with the Gödel Prize. How was using game theoretic ideas helpful in this line of research?

I started working on selfish routing when spending the 1999–2000 academic year at Berkeley. Around this time, the importance of understanding large networked systems, where each component is optimizing on their own, came to the forefront. This was a major change of focus for the computer science community. Rather than designing algorithms for a particular task, we need to also think about how to design and manage large networked systems, like the Internet, where each participating component is optimizing its own part. The classical Braess’s paradox is one example to show that each part separately optimizing can lead to suboptimal global solutions. Understanding the outcomes as multiple participants interact, each optimizing for themselves, is what game theory has been studying for decades.

What algorithmic approaches have you employed to understand the spread of influence in social networks? Where is research in this area heading?

Our work on the spread of influence in social network has focused on understanding good models of how influence spreads in networks and in analyzing a simple greedy algorithm for selecting an influential group of nodes. My recent work in this area focuses on modeling and understanding different phenomena in social networks, including polarization in opinion dynamics, and adversarial interventions that can cause polarization and how to protect against it.

What is rewarding about being Editor-in-Chief of the Journal of the ACM?

The Journal of the ACM is perhaps the most influential and most respected publication venue of the community doing research on the principles of computing, broadly understood. Publishing carefully refereed outstanding papers is important for the health of the scientific community. I was honored to be asked to take on this very important job for the community. I also greatly enjoyed working with the editorial board as well as with authors in producing the best journal we could.