Tata Institute of Fundamental Research

Exploring Size Complexity in Decision Trees

STCS Seminar
Speaker: Yogesh Dahiya (IMSc Chennai)
Organiser: Arkadev Chattopadhyay
Date: Friday, 1 Dec 2023, 16:00 to 17:00
Venue: via Zoom in A201

(Scan to add to calendar)

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. Many significant breakthroughs in recent  years have been intricately tied to exploring various facets of the  query model. Discovery of new connections between proof complexity and  query complexity and the development of query-to-communication lifting  theorems have played a pivotal role in getting new results in proof  complexity, boolean circuit complexity, and communication complexity.  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.  When the computation task is a search problem, a nuanced usage of  randomness by Gat and Goldwasser (ECCC-11) led to the beautiful notion  of pseudo-deterministic mode of computation. Pseudo-deterministic  algorithms are randomized algorithms that solve search problems by  almost always providing the same canonical solution (per each input).  They aim to address the inherent variability observed in randomized  algorithms, which often produce different correct results across  multiple runs. We will explore the interplay between determinism,  randomness, and pseudo-determinism concerning size complexity in the  decision tree model. Additionally, we will discuss more generalized  variants of decision trees, where queries are allowed to be functions  from specific classes rather than ordinary single-variable queries.