Exploring Size Complexity and Randomness in the Query Model [HBNI Th245]

Abstract

A central goal of computer science is to understand the capabilities and limitations of various computational devices. To understand various computational devices we formalize them using mathematical models called "models of computation". Examples of models of computation include Turing Machines, Quantum Machines, Formulas & Circuits, Communication Protocols, Proof Systems, and Decision Trees. Among various models, some find practical, physical implementations, while others are more like abstract constructs that help us explore many avatars of computation