A nondeterministic parity automaton is history-deterministic if there is a resolver that can resolve the nondeterminism on the fly while reading a word, based on the prefix read so far. The notion of history-determinism has been studied extensively over the recent years, yet the complexity of deciding history-determinism for parity automata has remained open since 2006.

In this talk, I will present some recent progress we have made on this problem. This is based on part published and part ongoing works, together with Rohan Acharya, Marcin Jurdziński, and Karoliina Lehtinen.