A Composition Theorem for Randomized Query Complexity

Suhail Sherif
Friday, 9 Jun 2017, 17:15 to 18:15
A-201 (STCS Seminar Room)
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)