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
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
tcsplus.bsky.social
And that's a wrap for this season of TCS+ 🎉! You can watch the recordings of the talks, and peruse the slides, on our website and YouTube channel:
🔗 sites.google.com/view/tcsplus...
📽️ www.youtube.com/@TCSplusSemi...

See you in a couple months... do suggest talks!
📋 sites.google.com/view/tcsplus...
2025/06/04: Irit Dinur, "Agreement Tests: Local Consistency, Global Structure" 2025/05/07: Palak Jain, "Enforcing Demographic Coherence: A Harms-Aware Framework for Reasoning about Private Data Release" 2025/04/23: Ryan Williams, "Simulating Time With Square-Root Space" 2025/04/09: Or Zamir, "Optimality of Frequency Moment Estimation" 2025/03/19: Tom Gur, "A Zero-Knowledge PCP Theorem" 2025/03/05: Prasanna Ramakrishnan, "How to Appease a Voter Majority"
June 8, 2025 at 12:53 PM
tcsplus.bsky.social
Bob* your calendar, as they say!

*Mark?
The TCS+ calendar: Tom Gur on March 19 Or Zamir on April 9 Ryan Williams on April 23 Palak Jain on May 7
March 16, 2025 at 7:57 PM