TCS+ talk *this week*: Wednesday, October 22, Ian Mertz, Charles University
Clement Canonne
This is a reminder that the next TCS+ talk is taking place this week, Wednesday, October 22nd at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). The speakers' slides will be made available at https://sites.google.com/view/tcsplus/welcome/past-talks after the talk.
If you’d like to join the Zoom talk, please sign up using the form at https://sites.google.com/view/tcsplus/welcome/next-tcs-talk. The talk will also be recorded and posted shortly afterwards on our YouTube channel, here: http://www.youtube.com/user/TCSplusSeminars.
Hoping to see you all there,
The organizers
-------------------------------
Speaker: Ian Mertz (Charles University)
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).