TCS+
LightNews LightNews
tcsplus.bsky.social
TCS+
@tcsplus.bsky.social
360 followers 6 following 55 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
Reposted by TCS+
tcsplus.bsky.social
More details (including abstract): tcsplus.wordpress.com/2025/09/27/t...
TCS+ talk: Wednesday, October 8 — Janani Sundaresan, University of Waterloo
We’re back! The very first TCS+ talk of the season will take place on Wednesday, October 8th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Janani Su…
tcsplus.wordpress.com
September 27, 2025 at 9:43 PM
tcsplus.bsky.social
More details (including abstract): tcsplus.wordpress.com/2025/09/27/t...
TCS+ talk: Wednesday, October 8 — Janani Sundaresan, University of Waterloo
We’re back! The very first TCS+ talk of the season will take place on Wednesday, October 8th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Janani Su…
tcsplus.wordpress.com
September 27, 2025 at 9:43 PM
tcsplus.bsky.social
As* foretold
September 27, 2025 at 10:19 AM
tcsplus.bsky.social
And as a teaser, here are the first 3 talks of the season! #TCSSky
- Janani Sundaresan, on her #FOCS2025 result showing hardness of distributed triangle detection
- Ian Mertz, with a survey talk on catalytic computing
- Aparna Gupte, on her #STOC2025 result on quantum one-time programs
- 8 Oct, Wed, 1pm TCS+ Talk: Janani Sundaresan (U Waterloo) - 22 Oct, Wed, 1pm TCS+ Talk: Ian Mertz (Charles University) - 5 Nov, Wed, 1pm TCS+ Talk: Aparna Gupte (MIT) (Times are Eastern time)
September 27, 2025 at 1:52 AM