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)
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) |