COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Logic and Semantics Seminar (Computer Laboratory) > Quasi-polynomial solutions for parity games and other problems

## Quasi-polynomial solutions for parity games and other problemsAdd 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
- Computer Laboratory talks
- Computing and Mathematics
- FW26
- Interested Talks
- Logic and Semantics Seminar (Computer Laboratory)
- School of Technology
- Trust & Technology Initiative - interesting events
- bld31
- yk373's list
Note that ex-directory lists are not shown. |
## Other listsCulture of Scientific Research Type the title of a new list here seminars## Other talksRole of Mitogen Activated Protein Kinase cascade during light and submergence signaling in plants Image analysis for cancer treatment CAN HIGH TECHNOLOGY PRODUCTS BE SUSTAINABLE? PhrenCam Nature’s engines – powering life VIRTUAL REALITY: WIDEN YOUR FIELD OF VIEW WITH A LOOK THROUGH A LENS TO THE PAST, PRESENT AND FUTURE. |