Quasi-polynomial solutions for parity games and other problems

Add to your list(s) Download to your calendar using vCal

• Karoliina Lehtinen, Christian-Albrechts University of Kiel
• Friday 14 September 2018, 14:00-15:00
• FW26.

If you have a question about this talk, please contact Victor Gomes.

Parity games are infinite two-player games, which are used in verification, automata theory, and reactive synthesis. Solving parity games—that is, deciding which player has a winning strategy—is one of the few problems known to be in both UP and co-UP yet not known to be in P. So far, the quest for a polynomial algorithm has lasted over 25 years. Last year, a major breakthrough occurred: parity games are solvable in quasi-polynomial time.

From an automata-perspective, solving parity games can be done by transforming alternating parity word automata into alternating weak automata. From a logician’s perspective, solving parity games can be done by finding a mu-calculus formula that recognises the winning region of a player in the parity game. Then, the size blow-up of the automaton in the first case, and the complexity of the formula in the second case, determine the complexity of the consequent algorithm for solving parity games.

In this talk, I present a quasi-polynomial solution for all three problems, based on playing parameterised games on parity-game arenas.

This talk is based on “A modal mu perspective on solving parity games in quasi-polynomial time”, presented at LICS ’18 and subsequent work with Udi Boker on weak automata.

This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Computing and Mathematics
• Department of Computer Science and Technology talks and seminars
• FW26
• Interested Talks
• Logic and Semantics Seminar (Computer Laboratory)
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• tcw57’s list
• yk373's list

Note that ex-directory lists are not shown.