Alladi Ramakrishnan Hall

Exploring Size Complexity and Randomness in the Query Model

Yogesh Dahiya

IMSc, HBNI

(HBNI PhD thesis defense)

(Hybrid mode. In person in Alladi Hall. Online at
zoom.us/j/99598370034
Meeting ID: 995 9837 0034
Passcode: 941422)

Decision trees represent one of the simplest and most basic models of computation, where a computational task is performed by adaptively querying the input with the goal of minimizing the number of queries. Despite its simplicity, it still remains a puzzle with many unresolved questions. Key complexity measures in this model are the depth complexity (the worst-case number of queries) and the size complexity (the space required to store the query algorithm). While depth complexity has been extensively studied, size complexity remains relatively under-explored.

This thesis investigates the relationship between size complexity and other complexity measures, and the advantages that randomness offers in the context of size complexity. We also study size complexity and the role of randomness in more generalized variants of decision trees, where queries are allowed to be functions from specific classes rather than ordinary single-variable queries.

Additionally, we explore the concept of pseudo-deterministic algorithms —- randomized algorithms that almost always produce the same output for each input —- within the context of search problems. This exploration reveals how determinism, randomness, and pseudo determinism interplay in the query model, leading to new insights, relations, and separations.