School of Technology and Computer Science Seminars

A Composition Theorem for Randomized Query Complexity

by Suhail Sherif (School of Technology and Computer Science, TIFR)

Friday, June 9, 2017 from to (Asia/Kolkata)
at A-201 (STCS Seminar Room)
Description
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)