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