Aditya Prakash

Highlights Conference 2025 Conference Abstract

The 2-Token Theorem: Recognising History-Deterministic Parity Automata Efficiently

• Aditya Prakash

Highlights Conference 2024 Conference Abstract

2-Token Game characterises History-Determinism on [0, 2] Automata

• Aditya Prakash

A nondeterministic parity automaton is history-deterministic if the nondeterminism while reading a word can be resolved based on the prefix read so far. We show that 2-token games characterise history-determinism on parity automata whose priorities are in [0, 2] (following the min-even parity condition). This extends the 2-token game characterisation of history-determinism for Büchi automata (Bagnol, Kuperberg; 2018) and coBüchi automata (Boker, Kuperberg, Lehtinen, Skrzypczak; 2020), and results in a polynomial time procedure to recognise [0, 2]-parity automata. Based on ongoing work with Karoliina Lehtinen.

Highlights Conference 2023 Conference Abstract

Joker Games for checking History-Determinism

• Aditya Prakash

History-determinism is a property of models where the non-deterministic choices in the model are resolved `on-the-fly’ based on the input read so far. History-deterministic parity automata are known to be more succinct than their deterministic counterpart (Kuperberg, Skrzypczak 2015), and exhibit compositionality with games akin to deterministic automata (Henzinger, Piterman 2006), hence they’re also called good-for-games. The exact complexity of checking history-determinism for higher parity indices remains open despite significant efforts, and is only known to be polynomial time for the lower indices of Büchi and co-Büchi. The underlying technique for the recent polynomial time algorithms for these use two-token games: Finding the winner in the two-token game turns out to be equivalent to checking history-determinism when the parity automaton is a Büchi or co-Büchi automaton (Bagnol, Kuperberg 2018; Boker, Kuperberg, Lehtinen, Skrzypczak 2020). It is conjectured that two-token games characterise history-determinism for all parity automata as well, and this is known as the two-token or the G2 conjecture. We show that for Büchi automata, checking history-determinism is equivalent to solving the joker game. These were originally used by Kuperberg and Skrzypczak (2015) to give a polynomial-time algorithm for checking history-determinism of a co-Büchi automaton, but it is not known if joker games characterise history-determinism for co-Büchi automata. The arena of joker games is smaller than that of two-token games by a linear factor, and thus solving joker games is faster by a quadratic factor than solving two-token games for Büchi automata. Moreover, our result implies that two-token games characterise history-determinism for Büchi automata, and thus is an alternative proof of the two-token conjecture for the Büchi case. This leads us to propose the joker conjecture: Checking history-determinism on a parity automaton is equivalent to finding the winner in the joker game. This is a stronger version of the two-token conjecture. We also hope that our ongoing work on joker games could lead to insights that help us progress in discovering efficient algorithms for checking history-determinism, as well as towards the G2 conjecture. (Joint ongoing work with Udi Boker, Marcin Jurdziński and Karoliina Lehtinen) Contributed talk given by Aditya Prakash

NeurIPS Conference 2023 Conference Paper

Look Ma, No Hands! Agent-Environment Factorization of Egocentric Videos

• Matthew Chang
• Aditya Prakash
• Saurabh Gupta

The analysis and use of egocentric videos for robotics tasks is made challenging by occlusion and the visual mismatch between the human hand and a robot end-effector. Past work views the human hand as a nuisance and removes it from the scene. However, the hand also provides a valuable signal for learning. In this work, we propose to extract a factored representation of the scene that separates the agent (human hand) and the environment. This alleviates both occlusion and mismatch while preserving the signal, thereby easing the design of models for downstream robotics tasks. At the heart of this factorization is our proposed Video Inpainting via Diffusion Model (VIDM) that leverages both a prior on real-world images (through a large-scale pre-trained diffusion model) and the appearance of the object in earlier frames of the video (through attention). Our experiments demonstrate the effectiveness of VIDM at improving the in-painting quality in egocentric videos and the power of our factored representation for numerous tasks: object detection, 3D reconstruction of manipulated objects, and learning of reward functions, policies, and affordances from videos.