Space-Bounded Computation Reading Group

Organizer	Sepehr Assadi
Meetings	We are currently meeting Wednesdays 10 to 11:30 am in MC 6483
Mailing list	Sign up to the mailing list for announcements and scheduling updates (only available to @uwaterloo.ca emails unfortunately)

Scope

Space-bounded computation is one of the oldest and most fundamental areas of theoretical computer science. At its core, it asks a very basic question:

how much memory is needed to solve a given computational problem?

This reading group focuses on some exciting recent frontiers in this area:

• Catalytic space: a new model that refines our understanding of space efficiency by allowing "borrowed" memory that must be returned unchanged.


• Space-bounded derandomization: randomness is a powerful resource in logspace, but is it truly necessary?


• Time-space tradeoffs: what is the inherent tension between limited memory and running time?

Topics

The following is a tentative list of the topics and papers that we will cover in this reading group (not in this particular order):

Catalytic Space

AM25	Bipartite Matching is in Catalytic Logspace, by Aryan Agarwala and Ian Mertz.
BC92	Computing Algebraic Formulas Using a Constant Number of Registers, by Michael Ben-Or and Richard Cleve.
BCKLS14	Computing with a full memory: Catalytic space, by Harry Buhrman, Richard Cleve, Michal Koucky, Bruno Loff, Florian Speelman.
CLMP25	The Structure of Catalytic Space: Capturing Randomness and Time via Compression, by James Cook, Jiatu Li, Ian Mertz, Edward Pyne.
CP25	Efficient Catalytic Graph Algorithms, by James Cook and Edward Pyne.
KMPS25	Collapsing Catalytic Classes, by Michal Koucky, Ian Mertz, Edward Pyne, Sasha Sami.
PSW25	Catalytic Communication, by Edward Pyne, Nathan S. Sheffield, William Wang.

Space Bounded Derandomization

CL24	Recursive Error Reduction for Regular Branching Programs, by Eshan Chattopadhyay and Jyun-Jie Liao.
DPTW25	When Connectivity Is Hard, Random Walks Are Easy with Non-determinism, by Dean Doron, Edward Pyne, Roei Tell, R. Ryan Williams.
N92	Pseudorandom generators for space-bounded computation, by Noam Nisan.
NW94	Hardness vs. Randomness, by Noam Nisan and Avi Wigderson.
PRZ23	Certified Hardness vs. Randomness for Log-Space, by Edward Pyne, Ran Raz, Wei Zhan.

Time-Space Tradeoffs

BBRS98	A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity, by Greg Barnes, Jonathan F. Buss, Walter L. Ruzzo, Baruch Schieber.
B89	A General Sequential Time-Space Tradeoff for Finding Unique Elements, by Paul Beame.
BSSV03	Time-Space Trade-Off Lower Bounds for Randomized Computation of Decision Problems, by Paul Beame, Michael Saks, Xiaodong Sun, Erik Vee.
BC82	A time-space tradeoff for sorting on a general sequential model of computation, by Allan Borodin, Stephen Cook.
CM24	Tree Evaluation Is in Space O(log n log log n), by James Cook and Ian Mertz.
EP95	A Nearly Optimal Time-Space Lower Bound for Directed st-Connectivity on the NNJAG Model, by Jeff Edmonds and Chung Keung Poon.
S01	Lower bounds on the complexity of recognizing SAT by Turing machines, by Rahul Santhanam.
W25	Simulating Time With Square-Root Space, by Ryan Williams.

Schedule

The schedule below is tentative and subject to change. We are currently meeting Wednesdays 10 to 11:30 am in MC 6483.

#	Date	Papers	Presenter
Part One: Catalytic Computation
1	Wednesday September 10	BC92: Computing Algebraic Formulas Using a Constant Number of Registers	Sepehr Assadi
2	Wednesday September 17	BCKLS14: Computing with a Full Memory: Catalytic Space	Sepehr Assadi
*	Wednesday September 24	No meeting
3	Wednesday October 1	CLMP25: The Structure of Catalytic Space: Capturing Randomness and Time via Compression KMPS25: Collapsing Catalytic Classes	Lap Chi Lau
4	Wednesday October 8	CP25: Efficient Catalytic Graph Algorithms	Aadila Ali Sabry & Max Jiang
5	Wednesday October 15	AM25: Bipartite Matching is in Catalytic Logspace	Chris Trevisan
6	Wednesday October 22	PSW25: Catalytic Communication	Parth Gupta

Resources

Some surveys and reading suggestions closely related to the topics of this reading group:

H22	Recent Progress on Derandomizing Space-Bounded Computation, by William Hoza (Bulletin of the EATCS 2022).
K16	Catalytic Computation, by Michal Koucky (Bulletin of the EATCS 2016).
M07	A Survey of Lower Bounds for Satisfiability and Related Problems, by Dieter van Melkebeek (Foundations and Trends in Theoretical Computer Science 2007).
M23	Reusing Space: Techniques and Open Problems, by Ian Mertz (Bulletin of the EATCS 2023).

Related Reading Groups or Courses

• Derandomization and its connections throughout complexity theory, by Roei Tell @ Rutgers (Winter 2022).
• Derandomizing Space-Bounded Computation, by William Hoza @ University of Chicago (Winter 2025).

Territorial Acknowledgement

The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is co-ordinated within the Office of Indigenous Relations.

---