Alladi Ramakrishnan Hall

Exploring Size Complexity and Randomness in the Query Model

Yogesh Dahiya

IMSc, HBNI

Pre-synopsis seminar.
Rescheduled from Wed 6 Dec 2023.
Hybrid mode;
zoom.us/j/99018916192?pwd=WE9IbmkrTlk5M20zZTRuVEpndlg3QT09

Decision trees are one of the simplest and most basic models of computation. Given a computational task, in the decision tree model (query model) of computation, the task is computed by adaptively querying the input while striving to minimize the number of queries required. While the model is simple, it still remains a puzzle with many unresolved questions. In the decision tree model, there are two natural complexity measures of importance: the depth complexity (the worst-case number of queries asked by a query algorithm) and the size complexity (the space required to store the query algorithm). While significant attention has been devoted to the former, the latter remains relatively under-explored.

In this talk, we will investigate the relationship between size complexity and other complexity measures, and understand the advantages that randomness offers in the context of size complexity. We will 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. In the realm of search problems, a nuanced usage of randomness led to the concept of pseudo-deterministic mode of computation. Pseudo-deterministic algorithms are randomized algorithms that almost always yield the same solution for each input, addressing the variability common in randomized algorithms. Our discussion will explore how determinism, randomness, and pseudo-determinism interact in the query model, revealing new relations and separations.