BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

The Backtracking Covering Proof Technique Hendler, Danny


Covering arguments are often used to derived space complexity lower bounds in the shared memory model, but it is often much more difficult to use them for obtaining time complexity lower bounds. The backtracking covering technique, introduced by Ellen, Hendler and Shavit in 2005 and used a few times since then, allows obtaining time lower bounds in some such situations. In this talk, I will describe the technique and will go through an extended example that shows how it is applied.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International