This course is on advanced topics in computational complexity. The current semester will be an introduction to space-bounded computation, through the perspective of computing with full memory. The first half will cover classic results in space complexity, while the second half will focus on the recent catalytic computing model.
No prior experience with space or complexity is needed, aside from some familiarity with Turing machines and mathematical maturity.
course description
homework & exam
A problem set will be posted in the coming weeks. The exam details will also be announced later in the course.
topics
| LECTURE 1 | basics of space complexity | [1] | Turing machines, configuration graphs, time and space, reversibility |
| LECTURE 2 | time versus space | [2-3] | TIME[$t$] $\subseteq$ SPACE[$t/\log t$], pebbling, reduction to Tree Evaluation |
| LECTURE 3-4 | non-deterministic and randomization | [4-7] | NSPACE[$s$] $\subseteq$ coNSPACE[$s$], BPSACE[$s$] $\subseteq$ SPACE[$s^2$] |
| LECTURE 5 | time-space tradeoffs | [8-9] | multiplication requires $TS \geq n^2$ |
| LECTURE 6 | catalytic computing | [10] | catalytic Turing machines, CL, CL $\subseteq$ ZPP |
| LECTURE 7-8 | technique I: arithmetic reversibility | [10-13] | Barrington's Theorem, CL $\subseteq$ TC$^1$, Tree Evaluation bounds |
| LECTURE 9-10 | technique II: compress-or-random | [14-16] | Match $\in$ CL, CLP $=$ CL $\cap$ P, NCL/BPCL $=$ CL |
| LECTURE 11 | catalytic algorithms | [17] | CL algorithms for connectivity, random walks |
Note: there may or may not be notes produced for this course later. In any event, I highly recommend recent lecture notes by Sepehr Assadi and Ramprasad Saptharishi, which should cover most topics in the course in depth.
course references
[1] Lange, McKenzie, & Tapp. Reversible Space Equals Determinstic Space. JCSS, 2000.
[2] Hopcroft, Paul, & Valiant. On Time Versus Space. JACM, 1977.
[3] Williams. Simulating Time With Square-Root Space. STOC, 2025.
[4] Savitch. Relationships Between Nondeterministic and Deterministic Tape Complexities. JCSS, 1970.
[5] Immerman. Nondeterministic space is closed under complementation. SICOMP, 1988.
[6] Szelepscenyi. The method of forced enumeration for nondeterministic automata. Acta Informatica, 1988.
[7] Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 1992.
[8] Borodin & Cook. A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation. SICOMP, 1982.
[9] Abrahamson. Time-Space Tradeoffs For Branching Programs Contrasted With Those For Straight-Line Programs. FOCS, 1986.
[10] Buhrman et al. Computing With a Full Memory: Catalytic Computing. STOC, 2014.
[11] Barrington. Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC1. JCSS, 1989.
[12] Ben-Or & Cleve. Computing Algebraic Formulas Using a Constant Number of Registers. SICOMP, 1992.
[13] Cook & Mertz. Tree Evaluation is In Space O(log n · log log n). SICOMP, 2025.
[14] Agarwala & Mertz. Bipartite Matching is in Catalytic Logspace. FOCS, 2025.
[15] Cook et al. The Structure of Catalytic Space: Capturing Randomness and Time via Compression. STOC, 2025.
[16] Koucký et al. Collapsing Catalytic Classes. FOCS, 2025.
[17] Cook & Pyne. Efficient Catalytic Graph Algorithms. ITCS, 2026.
general/useful references
- Assadi. Space Bounded Computation. Lecture notes, 2026.
- Saptharishi. Computational Complexity. Lecture notes, 2026.
- Koucký. Catalytic Computation. BEATCS, 2016.
- Mertz. Reusing Space: Techniques and Open Problems. BEATCS, 2023.
further reading
- Reingold. Undirected ST-Connectivity in Log-Space. JACM, 2008.
- Saks & Zhou. BPSACE(S) \subseteq DSPACE(S^3/2). JCSS, 1999.
- Raz. Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning. JACM, 2019.
- Beame. A General Sequential Time-Space Tradeoff for Finding Unique Elements. SICOMP, 1991.
- Barnes et al. A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity. SICOMP, 1998.