Logic, automata, algebra and games
Wednesday May 22, 2019, 2:15PM, 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

Logic, automata, algebra and games
Wednesday May 15, 2019, 2:15PM, 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

Logic, automata, algebra and games
Wednesday April 17, 2019, 2:15PM, 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

Logic, automata, algebra and games
Wednesday April 10, 2019, 2:15PM, 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

Logic, automata, algebra and games
Wednesday April 3, 2019, 2:15PM, 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

Logic, automata, algebra and games
Wednesday March 27, 2019, 2:15PM, 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

Logic, automata, algebra and games
Wednesday March 20, 2019, 2:15PM, 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