Evènement pour le groupe Séminaire Méthodes Formelles


Date 2020-10-20  14:00-15:00
TitreSolving Random Parity Games in Polynomial Time 
RésuméWe consider the problem of solving random parity games. We prove that parity games exibit a phase transition threshold so that when the degree of the graph that defines the game has a degree large enough then there exists a polynomial time algorithm that solves the game with high probability when the number of nodes goes to infinity. We further propose the SWCP (Self-Winning Cycles Propagation) algorithm and show that, when the degree is large enough, SWCP solves the game with high probability. Furthermore, the complexity of SWCP is polynomial. The design of SWCP is based on the threshold for the appearance of particular types of cycles in the players' respective subgraphs. We further show that non-sparse games can be solved in polynomial time with high probability. This is a joint work with Mickael Touati. More information at https://arxiv.org/abs/2007.08387 
LieuOnline 
OrateurRichard Combes 
EmailRichard.Combes@centralesupelec.fr 
UrlSupelec 



Aucun document lié à cet événement.

Retour
Retour à l'index