TY  - BOOK
AU  - Dahiya, Yogesh 
TI  - Exploring Size Complexity and Randomness in the Query Model 
PY  - 2024///
CY  - Chennai
PB  - The Institute of Mathematical Sciences
KW  - Mathematics
N2  - Decision trees, also known as query models, are 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 and have been
central to significant breakthroughs in recent years. These advancements include new
connections between proof complexity and query complexity, and the development
of query-to-communication lifting theorems, which have yielded new insights 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
UR  - https://dspace.imsc.res.in/xmlui/handle/123456789/881
ER  -