Logique, automates, algèbre et jeux Mercredi 22 mai 2019, 14 heures 15, 3052 Uri Zwick (Blavatnik School of Computer Science) Games on Graphs and Linear Programming Abstractions, Part 7/7: Lower bounds for Random-Facet and Random-Edge In this lecture we present sub-exponential lower bounds for Random-Facet (the randomized algorithm considered in Lecture 3) and Random-Edge. https://www.irif.fr/_media/actualites/ressources/zwick_program.pdf Logique, automates, algèbre et jeux Mercredi 15 mai 2019, 14 heures 15, 3052 Uri Zwick (Blavatnik School of Computer Science) Games on Graphs and Linear Programming Abstractions, Part 6/7: Lower bounds for Policy Iteration Policy Iteration, introduced in the first lecture, is a very natural class of algorithms for solving TBSGs. Policy Iteration algorithms work very well in practice. However, we now know that their worst-case complexity is exponential. We will present such lower bounds. https://www.irif.fr/_media/actualites/ressources/zwick_program.pdf Logique, automates, algèbre et jeux Mercredi 17 avril 2019, 14 heures 15, 3052 Uri Zwick (Blavatnik School of Computer Science) Games on Graphs and Linear Programming Abstractions, Part 5/7: Parity Games In this lecture we consider Parity Games (PGs), a very special case of MPGs, with many relations to automata on infinite words and to automatic verification. In a recent breakthrough Calude et al. obtained a quasi-polynomial time algorithm for solving PGs. We will describe one of the existing variants of their algorithm. https://www.irif.fr/_media/actualites/ressources/zwick_program.pdf Logique, automates, algèbre et jeux Mercredi 10 avril 2019, 14 heures 15, 3052 Uri Zwick (Blavatnik School of Computer Science) Games on Graphs and Linear Programming Abstractions, Part 4/7: Acyclic Unique Sink Orientations (AUSOs) In this lecture we consider Acyclic Unique Sink Orientations (AUSOs) an abstraction related to linear programming that also captures the games we are interested in. We present algorithms for finding the sink of an AUSOs, which directly translate to algorithms for solving games. https://www.irif.fr/_media/actualites/ressources/zwick_program.pdf Logique, automates, algèbre et jeux Mercredi 3 avril 2019, 14 heures 15, 3052 Uri Zwick (Blavatnik School of Computer Science) Games on Graphs and Linear Programming Abstractions, Part 3/7: Randomized sub-exponential time algorithm In this talk we present an elegant randomized algorithm that solves all the games we consider in sub-exponential time. This is currently the fastest known algorithm for TBSGs, and also for MPGs and EGs, when there is no restriction on the edge costs. The algorithm is an adaptation of a randomized algorithms of Kalai and Matousek, Sharir and Welzl for solving linear programs. We also mention relations to abstractions of Linear Programming abstractions. https://www.irif.fr/_media/actualites/ressources/zwick_program.pdf Logique, automates, algèbre et jeux Mercredi 27 mars 2019, 14 heures 15, 3052 Uri Zwick (Blavatnik School of Computer Science) Games on Graphs and Linear Programming Abstractions, Part 2/7: Mean Payoff games and Energy Games In this talk we consider non-stochastic versions of the games introduced in the first lecture, namely Mean Payoff Games (MPGs) and Energy Games (EGs). We show reductions between these two games. We then describe a pseudo-polynomial time algorithm of Brim et al. for EGs, and hence also MPGs https://www.irif.fr/_media/actualites/ressources/zwick_program.pdf Logique, automates, algèbre et jeux Mercredi 20 mars 2019, 14 heures 15, 3052 Uri Zwick (Blavatnik School of Computer Science) Games on Graphs and Linear Programming Abstractions, Part 1/7: Two-player Turn-based Stochastic Games In the first lecture we define the two-player Turn-Based Stochastic Games (TBSGs), the most general games considered in this lecture series. We define the objectives of the two players, the strategies that they can use, and define the values of the games. We then consider algorithms for finding the values and optimal strategies, first in one-player games and then in two-player games. While for one-player games polynomial time algorithms are known, for most two-player games no polynomial time algorithms are currently known. https://www.irif.fr/_media/actualites/ressources/zwick_program.pdf