On Time, and Space, and Width, and Depth

on YouTube ↗55m

" summary

Asserts that many resolution measures collapse into a small structural picture: up to log and quasi‑polynomial factors, log of resolution size is bounded by width, and Ben‑Sasson–Wigderson style separations show width ≠ tree‑like size; pebbling contradictions give concrete DAG formulas whose pebbling complexity lower bounds depth and force large refutations; introduces positive depth and shows examples with constant clause space but tree‑like size ≥ n^2. Tools: pebbling (including black‑white), algebraic polynomial calculus/monomial space, DNF‑resolution. Main open problems: separate clause/variable/monomial spaces from width and decide whether amortized (star) measures differ.

AI-written summary · about

" chapters (10)

1. 0:00Introduction and scope
2. 2:34Resolution proof measures
3. 7:56Tree-like resolution
4. 11:49Depth and hierarchy
5. 17:53Space complexity concepts
6. 24:02Space and monomial models
7. 29:40Amortized complexity
8. 34:25Advanced space models
9. 39:44Open problems and conclusion
10. 45:42Q&A and closing