A Composition Theorem for Randomized Query Complexity



Friday, 9 June 2017, 17:15 to 18:15


Around a week ago, a group of researchers* proved that the randomized query complexity of f composed with g is lower bounded by the product of the randomized query complexities of f and g, albeit with suboptimal parameters. This proof of theirs is quite simple and so I wish to give a decently good exposition of it.

In this talk, I plan to:

- introduce query complexity
- show Yao's lemma and how it simplifies dealing with randomized algorithms
- present the proof from the paper

* Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha and Swagato Sanyal, in their paper "A Composition Theorem for Randomized Query Complexity" (arXiv:1706.00335)