Tata Institute of Fundamental Research
On the composition question for randomized query complexity.
STCS Seminar
Speaker:
Swagato Sanyal (Indian Institute of Technology, Kharagpur)
Organiser:
Raghuvansh Saxena
Date:
Tuesday, 17 Sep 2024, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
A query algorithm (also known as a decision tree) that computes a Boolean function f on n variables, queries various bits of an input to f, possibly in an adaptive fashion and using randomness. It eventually produces a bit as an output, which is supposed to equal the value of f on that input with high probability. The complexity measure of such an algorithm is the number of queries that it makes in the worst case. This talk considers the query complexity of a class of Boolean function called 'composed functions'. Composition of two Boolean functions f and g is, informally speaking, the Boolean function (say h) obtained by successive applications of g and f. The composition question, instantiated for query complexity, asks whether there exists a query algorithm that computes h that is significantly more efficient than what the definition of h suggests: first compute g and then compute f. The question has been the centre of a lot of research, and stands open to this day. In this work we present some results in relation to this question. The talk is based on a work that was accepted to STACS 2024.
Short Bio:
Swagato Sanyal is an Assistant Professor at the Department of Computer Science and Engineering, IIT Kharagpur. Prior to this, he was a post-doctoral research fellow at NTU and NUS, Singapore. He obtained is PhD degree from STCS, TIFR in 2017. He is interested broadly in computational complexity theory, and more specifically in query and communication complexity and Boolean function analysis.
| Speaker: | Swagato Sanyal (Indian Institute of Technology, Kharagpur) |
| Organiser: | Raghuvansh Saxena |
| Date: | Tuesday, 17 Sep 2024, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
A query algorithm (also known as a decision tree) that computes a Boolean function f on n variables, queries various bits of an input to f, possibly in an adaptive fashion and using randomness. It eventually produces a bit as an output, which is supposed to equal the value of f on that input with high probability. The complexity measure of such an algorithm is the number of queries that it makes in the worst case. This talk considers the query complexity of a class of Boolean function called 'composed functions'. Composition of two Boolean functions f and g is, informally speaking, the Boolean function (say h) obtained by successive applications of g and f. The composition question, instantiated for query complexity, asks whether there exists a query algorithm that computes h that is significantly more efficient than what the definition of h suggests: first compute g and then compute f. The question has been the centre of a lot of research, and stands open to this day. In this work we present some results in relation to this question. The talk is based on a work that was accepted to STACS 2024.
Short Bio:
Swagato Sanyal is an Assistant Professor at the Department of Computer Science and Engineering, IIT Kharagpur. Prior to this, he was a post-doctoral research fellow at NTU and NUS, Singapore. He obtained is PhD degree from STCS, TIFR in 2017. He is interested broadly in computational complexity theory, and more specifically in query and communication complexity and Boolean function analysis.