~~NOCACHE~~
/* DO NOT EDIT THIS FILE             */

[[en:seminaires:laag:index|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//
<button type="link" size="xs" collapse="b23-3824">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b23-3824" collapsed="true">
<well size="sm">
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]]
</well>
</collapse>


[[en:seminaires:laag:index|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//
<button type="link" size="xs" collapse="b23-3825">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b23-3825" collapsed="true">
<well size="sm">
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]]
</well>
</collapse>


[[en:seminaires:laag:index|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//
<button type="link" size="xs" collapse="b23-3826">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b23-3826" collapsed="true">
<well size="sm">
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]]
</well>
</collapse>


[[en:seminaires:laag:index|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)//
<button type="link" size="xs" collapse="b23-3827">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b23-3827" collapsed="true">
<well size="sm">
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]]
</well>
</collapse>


[[en:seminaires:laag:index|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//
<button type="link" size="xs" collapse="b23-3828">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b23-3828" collapsed="true">
<well size="sm">
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]]
</well>
</collapse>


[[en:seminaires:laag:index|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//
<button type="link" size="xs" collapse="b23-3829">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b23-3829" collapsed="true">
<well size="sm">
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]]
</well>
</collapse>


[[en:seminaires:laag:index|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//
<button type="link" size="xs" collapse="b23-3830">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b23-3830" collapsed="true">
<well size="sm">
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]]
</well>
</collapse>