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.
