TCS+

@tcsplus.bsky.social

426 Followers 10 Following

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

2026/05/20: Shyamal Patel, "Learning Functions of Halfspaces" 2026/04/22: Yichuan Wang, "Super-quadratic Lower Bounds for Depth-2 Linear Threshold Circuits" 2026/04/08: Rahul Ilango, "Gödel in Cryptography: Zero-Knowledge Proofs With No Interaction, No Setup, and Perfect Soundness" 2026/03/18: Christopher Gartland, "L1-distortion of Earth Mover Distances and Transportation Cost Spaces on High Dimensional Grids" 2026/03/04: Sophie Huiberts, "Analyzing the Simplex Method by the Book"
2026/04/08: Rahul Ilango, "Gödel in Cryptography: Zero-Knowledge Proofs With No Interaction, No Setup, and Perfect Soundness" 2026/03/18: Christopher Gartland, "L1-distortion of Earth Mover Distances and Transportation Cost Spaces on High Dimensional Grids" 2026/03/04: Sophie Huiberts, "Analyzing the Simplex Method by the Book"
4 Mar, Wed 1pm TCS+ Talk: Sophie Huiberts (CNRS) 18 Mar, Wed 1pm TCS+ Talk: Christopher Gartland (UNC Charlotte) 8 Apr, Wed 1pm TCS+ Talk: Rahul Ilango (MIT) 22 Apr, Wed 1pm TCS+ Talk: Yichuan Wang (UC Berkeley)
2025/12/03: Natalie Collina, "Swap regret and correlated equilibria beyond normal-form games" 2025/11/19: Haotian Jiang, "Beck-Fiala and Komlós Bounds Beyond Banaszczyk" 2025/11/05: Aparna Gupte, "Quantum One-Time Programs, Revisited" 2025/10/22: Ian Mertz, "A Random Walk Down Full Memory Lane" 2025/10/08: Janani Sundaresan, "Distributed Triangle Detection is Hard in Few Rounds"
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).
- 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)
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"
The TCS+ calendar: Tom Gur on March 19 Or Zamir on April 9 Ryan Williams on April 23 Palak Jain on May 7