School of Technology and Computer Science Seminars

Randomized Sabotage Complexity

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

Friday, July 29, 2016 from to (Asia/Kolkata)
at A-201 (STCS Seminar Room)
Description
One of the famous open problems in randomized query complexity is the composition question: Is R(f o g) = Omega(R(f)R(g)) for all boolean functions f and g. Shalev Ben-David and Robin Kothari recently showed that this is true for a restricted case, where R(f o h o g) = Omega(R(f)R(h)R(g)) for some fixed h. To do so, they introduced randomized sabotage complexity. This complexity measure has several nice properties.

In this talk, I will present the randomized sabotage complexity measure, go through some of its properties and present the proof of the restricted composition theorem. Most of this will just be through making simple observations, almost no background is required.