Invited Speakers

Fedor V. Fomin (University of Bergen)

Fedor V. Fomin is a professor in computer science at the University of Bergen, researching Algorithms and Combinatorics. In 2019 Fomin was named an EATCS (European Association for Theoretical Computer Science) Fellow for “his fundamental contributions in the fields of parameterized complexity and exponential algorithms”. He is elected member of the Norwegian Academy of Science and Letters, the Norwegian Academy of Technological Sciences, and the Academia Europaea.

Talk: Long cycles in graphs: Extremal Combinatorics meets Parameterized Algorithms

Abstract: We discuss recent algorithmic extensions of two classic results of extremal combinatorics about long paths in graphs. First, the theorem of Dirac from 1952 asserts that a 2-connected graph G with the minimum vertex degree d>1, is either Hamiltonian or contains a cycle of length at least 2d. Second, the theorem of Erdős-Gallai from 1959, states that a 2-connected graph G with the average vertex degree D>1, contains a cycle of length at least D. The proofs of these theorems are constructive, they provide polynomial-time algorithms constructing cycles of lengths 2d and D. We extend these algorithmic results by showing that each of the problems to decide whether a 2-connected graph contains a cycle of length at least 2d+k or of a cycle of length at least D+k, is fixed-parameter tractable parameterized by k. The talk is based on the joint works with Petr Golovach, Danil Sagunov, and Kirill Simonov.

Monika Henzinger (University of Vienna)

^{© University of Vienna/Barbara Mair}

Monika Henzinger is Professor at the University of Vienna, Austria, heading the research group of Theory and Applications of Algorithms. She received her PhD in 1993 from Princeton University and was an assistant professor at Cornell University, a researcher at Digital Equipment Corporation, the Director of Research at Google and a professor at EPFL, Switzerland, before moving to the University of Vienna. Professor Henzinger received a Dr. h. c. degree from the Technical University of Dortmund, Germany, two ERC Advanced Grants (2014 and 2021), the Carus Medal of the German Academy of Sciences, a SIGIR Test of Time Award, a Netidee SCIENCE Award of the Internet Foundation Austria, a European Young Investigator Award, an NSF CAREER Award, and a Top 25 Women on the Web Award. She is a fellow of the ACM and of the EATCS and a member of the Austrian Academy of Sciences and the German Academy of Sciences Leopoldina. She is an editor of the Journal of the ACM and the SIAM Journal on Computing and a member of the supervisory board of AMS OSRAM AG and of the Swiss Science Council. Her scientific work consists of over 200 scientific articles and over 80 patents.

Talk: Modern Dynamic Data Structures

Abstract: The goal in the design of data structures has traditionally been to minimize the use of resources such as time and space. However, in recent years a variety of applications have shown the need for additional requirements such as differential privacy and fairness. In this talk we give an overview of the state of the art of dynamic data structures under these constraints.

Thomas Henzinger (IST Austria)

Tom Henzinger has been President of the Institute of Science and Technology Austria (ISTA) since 2009. He holds a PhD from Stanford University (1991) and was Assistant Professor at Cornell University, Professor at the University of California, Berkeley, Director at the Max-Planck Institute in Saarbrucken, and Professor at EPFL in Lausanne, Switzerland. His research focuses on the theory of software systems, especially models, algorithms, and tools for the design and verification of reliable software systems. His HyTech tool was the first model checker for mixed discrete-continuous systems. He is a member of the US National Academy of Sciences, the American Academy of Arts and Sciences, Academia Europaea, the German Academy of Sciences (Leopoldina), and the Austrian Academy of Sciences. He is also a Fellow of the AAAS, the ACM, and the IEEE. He received the Robin Milner Award of the Royal Society, the EATCS Award of the European Association for Theoretical Computer Science, and the Wittgenstein Award of the Austrian Science Fund.

Talk: An Updated Survey of Bidding Games on Graphs

Abstract: A graph game is a two-player zero-sum game in which the players move a token throughout a graph to produce an infinite path, which determines the winner or payoff of the game. In bidding games, both players have budgets, and in each turn, we hold an “auction” (bidding) to determine which player moves the token. In this updated survey, we consider several bidding mechanisms and summarize the known results. This is joint work with Guy Avni and others.

Marta Kwiatkowska (University of Oxford)

Marta Kwiatkowska is Professor of Computing Systems and Fellow of Trinity College, University of Oxford. She is known for fundamental contributions to the theory and practice of model checking for probabilistic systems, focusing on automated techniques for verification and synthesis from quantitative specifications. She led the development of the PRISM model checker (www.prismmodelchecker.org), the leading software tool in the area and winner of the HVC Award 2016. Probabilistic model checking has been adopted in diverse fields, including distributed computing, wireless networks, security, robotics, healthcare, systems biology, DNA computing and nanotechnology, with genuine flaws found and corrected in real-world protocols. Kwiatkowska is the first female winner of the Royal Society Milner Award, and was awarded the BCS Lovelace Medal, Van Wijngaarden Award and an honorary doctorate from KTH Royal Institute of Technology in Stockholm. She won two ERC Advanced Grants, VERIWARE and FUN2MODEL, and is a coinvestigator of the EPSRC Programme Grant on Mobile Autonomy and the EPSRC Prosperity Partnership FAIR. Kwiatkowska is a Fellow of the Royal Society, Fellow of ACM, EATCS and BCS, and Member of Academia Europea.

Talk: Probabilistic model checking for strategic equilibria-based decision making

Abstract: Software faults have plagued computing systems since the early days, leading to the development of methods based on mathematical logic, such as proof assistants or model checking, to ensure their correctness. The rise of AI calls for automated decision making that incorporates strategic reasoning and coordination of behaviour of multiple autonomous agents acting concurrently and in presence of uncertainty. Traditionally, game-theoretic solutions such as Nash equilibria are employed to analyse strategic interactions between multiple independent entities, but model checking tools for scenarios exhibiting concurrency, stochasticity and equilibria have been lacking. This lecture will focus on a recent extension of probabilistic model checker PRISM-games (www.prismmodelchecker.org/games/), which supports quantitative reasoning and strategy synthesis for concurrent multiplayer stochastic games against temporal logic that can express coalitional, zero-sum and equilibria-based properties. Game-theoretic models arise naturally in the context of autonomous computing infrastructure, including user-centric networks, robotics and security. Using illustrative examples, this lecture will give an overview of recent progress in probabilistic model checking for stochastic games and highlight challenges and opportunities for the future.

Vijay Vazirani (University of California)

Vijay Vazirani got his undergraduate degree from MIT in 1979 and his PhD from the University of California, Berkeley in 1983. He is currently a Distinguished Professor at the University of California, Irvine.

Vazirani has made fundamental contributions to several areas of the theory of algorithms, including algorithmic matching theory, approximation algorithms and algorithmic game theory, as well as to complexity theory, in which he established, with Les Valiant, the hardness of unique solution instances of NP-complete problems. Over the last four years, he has been working on algorithms for matching markets.

In 2001 he published Approximation Algorithms, which is widely regarded as the definitive book on the topic. In 2007, he published the co-edited book Algorithmic Game Theory. Another co-edited book, Online and Matching-Based Market Design, will be published by Cambridge University Press in early 2022; see its flyer: https://www.ics.uci.edu/~vazirani/flyer.pdf

Talk: Online Bipartite Matching and Adwords

Abstract: Over the last three decades, the online bipartite matching (OBM) problem has emerged as a central problem in the area of Online Algorithms. Perhaps even more important is its role in the area of Matching-Based Market Design. The resurgence of this area, with the revolutions of the Internet and mobile computing, has opened up novel, path- breaking applications, and OBM has emerged as its paradigmatic algorithmic problem. In a 1990 joint paper with Richard Karp and Umesh Vazirani, we gave an optimal algorithm, called RANKING, for OBM, achieving a competitive ratio of (1 – 1/e); however, its analysis was difficult to comprehend. Over the years, several researchers simplified the analysis.

We will start by presenting a “textbook quality” proof of RANKING. Its simplicity raises the possibility of extending RANKING all the way to a generalization of OBM called the adwords problem. This problem is both notoriously difficult and very significant, the latter because of its role in the AdWords marketplace of Google. We will show how far this endeavor has gone and what remains. We will also provide a broad overview of the area of Matching-Based Market Design and pinpoint the role of OBM.

Based on: https://arxiv.org/pdf/2107.10777.pdf

Contact: Stefan Szeider (mfcs2022@ac.tuwien.ac.at)