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.
