We are happy to present Aditya Prakash’s talk titled “The 2-Token Theorem”.
A nondeterministic parity automaton is said to be history deterministic if there is a resolver that capable of resolving the nondeterminism while reading an input word, based on the prefix read so far. The exact complexity of deciding history determinism for parity automata has remained open since 2006, with the problem only being known to be solvable in polynomial time for Büchi and coBüchi automata, until very recently.
In this talk, I will present some recent progress on this problem, where we extend this polynomial-time decidability procedure to parity automata with a fixed number of priorities. This is achieved by positively resolving the 2-token conjecture of Bagnol and Kuperberg, which had remained open since 2018. This talk is based on joint work with Karoliina Lehtinen that will appear in STOC 2025.
Aditya is a fourth-year PhD student at the University of Warwick, where he is working with Marcin Jurdzinski on automata and games, especially those on infinite words. During his PhD, his research has been focused on history-determinism, particularly on parity automata.