Tata Institute of Fundamental Research
Parity Games are solvable in quasipolynomial time
STCS Student Seminar
Speaker:
Ashutosh Shankar
Organiser:
Sushant Vijayan
Date:
Friday, 18 Sep 2020, 17:15 to 18:15
Venue:
https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09
(Scan to add to calendar)
Abstract:
A longstanding open problem in computer science has been to show that parity games can be solved in polynomial time. In this talk, I will be presenting a quasipolynomial time algorithm due to Parys (2019) which is a modification of Zielonka's recursive algorithm (1998).
| Speaker: | Ashutosh Shankar |
| Organiser: | Sushant Vijayan |
| Date: | Friday, 18 Sep 2020, 17:15 to 18:15 |
| Venue: | https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09 |
(Scan to add to calendar)
Abstract:
A longstanding open problem in computer science has been to show that parity games can be solved in polynomial time. In this talk, I will be presenting a quasipolynomial time algorithm due to Parys (2019) which is a modification of Zielonka's recursive algorithm (1998).