Title	The Backtracking Covering Proof Technique
Creator	Hendler, Danny
Publisher	Banff International Research Station for Mathematical Innovation and Discovery
Date Issued	2016-12-01T12:55
Description	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.
Extent	38.0
Subject	Mathematics; Computer science; Theoretical computer science
Type	Moving Image
File Format	video/mp4
Language	eng
Notes	Author affiliation: Ben-Gurion University of the Negev
Series	BIRS Workshop Lecture Videos (Oaxaca de Juárez (Mexico))
Date Available	2019-03-06
Provider	Vancouver : University of British Columbia Library
Rights	Attribution-NonCommercial-NoDerivatives 4.0 International
DOI	10.14288/1.0376632
URI	http://hdl.handle.net/2429/68485
Affiliation	Non UBC
Peer Review Status	Unreviewed
Scholarly Level	Faculty
Rights URI	http://creativecommons.org/licenses/by-nc-nd/4.0/
Aggregated Source Repository	DSpace

Open Collections

BIRS Workshop Lecture Videos