iiinova — where your digital self keeps evolving

TCS+

@tcsplus.bsky.social

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: www.tcsplus.org

Posts Replies Media

TCS+ @tcsplus.bsky.social · 21/05/2026

And that's a wrap for the semester! All the talks of the season are now available on our website: sites.google.com/view/tcsplus... and YouTube channel: www.youtube.com/@TCSplusSemi... Thank you to all attendees, and to our wonderful speakers—and see you in the Fall! #TCSSky #TheoreticalCS

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"

084

TCS+ @tcsplus.bsky.social · 14/04/2026

The recordings of the first 3 talks of the season have been uploaded, and the videos are available on our website and YouTube channel! sites.google.com/view/tcsplus... www.youtube.com/@TCSplusSemi...

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"

072

TCS+ @tcsplus.bsky.social · 24/02/2026

The schedule for the upcoming talks (stay tuned for the May speakers!) can be found on our website: exciting times ahead! sites.google.com/view/tcsplus/

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)

0144

TCS+ @tcsplus.bsky.social · 09/01/2026

The recordings (and slides when provided) of the previous season of TCS+ are now available! Website: www.tcsplus.org/welcome/past... YouTube: www.youtube.com/@TCSplusSemi...

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"

0103

TCS+ @tcsplus.bsky.social · 17/10/2025

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).

000

TCS+ @tcsplus.bsky.social · 27/09/2025

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)

040

TCS+ @tcsplus.bsky.social · 08/06/2025

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"

0105

TCS+ @tcsplus.bsky.social · 16/03/2025

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

1104