Normal view MARC view ISBD view

Dahiya, Yogesh

Exploring Size Complexity and Randomness in the Query Model - Chennai The Institute of Mathematical Sciences 2024 - xxii, 205p.



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.

Subjects--Topical Terms:
Mathematics

Universal Decimal Class. No.: HBNI / Th245