Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
Solving Random Parity Games in Polynomial Time
du 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