Exploring Size Complexity and Randomness in the Query Model
Material type:
TextLanguage: English Publication details: Chennai The Institute of Mathematical Sciences 2024Description: xxii, 205pSubject(s): Mathematics | MathematicsOnline resources: Click here to access online Dissertation note: Ph.D HBNI 2024 Summary: 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.
THESIS & DISSERTATION
| Current library | Home library | Collection | Call number | Materials specified | URL | Status | Date due | Barcode |
|---|---|---|---|---|---|---|---|---|
| IMSc Library IN PROCESS | IMSc Library IN PROCESS | IMSc Thesis | HBNI Th245 (Browse shelf (Opens below)) | Link to resource | Not for loan | 78044 |
Ph.D HBNI 2024
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.
There are no comments on this title.