Tata Institute of Fundamental Research
On Decision Tree Complexity of Boolean Functions
STCS Seminar
Speaker:
Swagato Sanyal (Indian Institute of Technology Kharagpur
Kharagpur, West Bengal)
Organiser:
Arkadev Chattopadhyay
Date:
Tuesday, 7 Jul 2020, 14:00 to 15:00
Venue:
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Swagato Sanyal (Indian Institute of Technology Kharagpur Kharagpur, West Bengal) |
| Organiser: | Arkadev Chattopadhyay |
| Date: | Tuesday, 7 Jul 2020, 14:00 to 15:00 |
| Venue: |
(Scan to add to calendar)
Abstract:
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.
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.