TCS+
LightNews LightNews
tcsplus.bsky.social
TCS+
@tcsplus.bsky.social
360 followers 7 following 59 posts
TCS+ is the original online seminar in theoretical computer science, committed to the carbon-free dissemination of ideas across the globe since 2013. Talks from the cutting edge of research in TCS, for a wide audience: https://www.tcsplus.org
Posts Replies Media Videos
tcsplus.bsky.social
Ian's talk will be a survey on catalytic computation: see abstract below.

tcsplus.wordpress.com/2025/10/17/t...
Title: A Random Walk Down Full Memory Lane Abstract: Can full memory be an asset to computation? This is the question underlying catalytic computing (Buhrman et al. 2014), a recent paradigm in which a space-bounded machine has access to additional read-write catalytic memory, which is much larger than the regular work tape but whose initial contents must be reset by the computation. We survey major techniques and results in the field by proving BPL is contained in CL, i.e. how to estimate random walk distributions using a catalytic tape. We will see three distinct proofs: 1) compression-based (Dulek 2015) 2) arithmetic reversibility (Buhrman et al. 2014); and 3) a simple algorithm using ideas from both (Cook-Pyne 2025).
October 17, 2025 at 7:50 PM