Dieter van Melkebeek (University of Wisconsin, Madison):
Time-Space Lower Bounds for NP-Complete Problems - Part II
We continue the survey we started last week about lower bounds on the running time of algorithms for NP-complete problems like satisfiability that use a small amount of work space.