LFCS Seminar: Tuesday, 27th May: Swagato Sanyal

Title: On the composition question for randomized query complexity.

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.