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 Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International