Talk will be held on Zoom.
Abstract: The decision tree model, also known as the query model, is a simple model of computation. Besides having an intuitive appeal, and offering a natural paradigm for algorithm design, it is often possible to theoretically nail down the exact complexity of many interesting algorithmic tasks using currently available methods, completely and unconditionally; for more complex models of computation such an aspiration is currently a distant dream. In this talk we will first introduce and motivate query model, and then present a recent work of ours on the query complexity of an important subclass of problems, called composed functions. The latter part is based on joint work with Dmitry Gavinsky, Troy Lee and Miklos Santha which has appeared in ICALP 2019.
