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)
