TCS+

And that’s a wrap for this season of TCS+! As usual, you can watch the recordings of the talks, and peruse the slides, on our website and YouTube channel.

2025/03/05: Prasanna Ramakrishnan, “How to Appease a Voter Majority”
2025/03/19: Tom Gur, “A Zero-Knowledge PCP Theorem”
2025/04/09: Or Zamir, “Optimality of Frequency Moment Estimation”
2025/04/23: Ryan Williams, “Simulating Time With Square-Root Space”
2025/05/07: Palak Jain, “Enforcing Demographic Coherence: A Harms-Aware Framework for Reasoning about Private Data Release”
2025/06/04: Irit Dinur, “Agreement Tests: Local Consistency, Global Structure”

Thanks to our speakers and audience for yet another great season! See you in a couple months… and in the meantime, subscribe to our newsletter to stay informed, and do suggest talks!

The next TCS+ talk (and the last of the season!) will take place this coming Wednesday, June 4th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC: check your timezone here). Irit Dinur from the IAS will speak about “Agreement Tests: Local Consistency, Global Structure” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: Suppose you are given a noisy collection of partial views of an object — how much can you recover just by checking how often these views agree with each other? Agreement testing theorems show that under certain conditions, remarkably, local consistency can guarantee the existence of a coherent global object.

These agreement tests (also known as direct product tests) are central tools in the proofs of PCP theorems, low-degree tests, and more general locally testable codes. In this talk, I will describe recent advances in agreement testing on high-dimensional expanders — powerful combinatorial structures that provide robust frameworks for local-to-global inference — and show how they open new doors for constructing efficient, highly resilient systems.

The next TCS+ talk will take place this coming Wednesday, May 7th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Palak Jain from Boston University will speak about “Enforcing Demographic Coherence: A Harms Aware Framework for Reasoning about Private Data Release” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: Our work introduces demographic coherence enforcement, a framework for reasoning about privacy which is purposefully designed with socio-technical usability in mind. It contains sufficient formalism to enable rigorous analysis and provable realisation, all while keeping tangible harms compellingly salient. The framework also lends itself to natural experimental evaluation, which could help build practical intuition and support tangible assessment of risks.

In this talk, I will present our approach, which characterises the adversary as a predictive model and reframes the question of privacy loss in terms of potential inferential harms to vulnerable groups. I will then define demographic coherence enforcement, a property that we argue is necessary for privacy-preserving data curation. Finally, I will briefly touch on the connections between our framework and some existing privacy tools.

Based on joint work with Mark Bun, Marco Carmisino, Gabe Kaptchuk, and Satchit Sivakumar.

Speaker Bio: Palak Jain is a Ph.D. candidate in Theoretical Computer Science at Boston University advised by professors Adam Smith and Mayank Varia.  Their work focuses on bringing robust data protections into practice through the lenses of cryptography, differential privacy, and ML. More information about them is available on their website (https://thepalakjain.com).

The next TCS+ talk will take place this coming Wednesday, April 23rd at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Ryan Williams from MIT will speak about “Simulating Time With Square-Root Space” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: We show that for all functions , every multitape Turing machine running in time can be simulated in space only . This is a substantial improvement over Hopcroft, Paul, and Valiant’s simulation of time in space from 50 years ago [FOCS 1975, JACM 1977]. Among other results, our simulation implies that bounded fan-in circuits of size can be evaluated on any input in only space, and that there are explicit problems solvable in space which require at least time on a multitape Turing machine for all , thereby making a little progress on the versus problem.

Our simulation reduces the problem of simulating time-bounded multitape Turing machines to a series of implicitly-defined Tree Evaluation instances with nice parameters, leveraging the remarkable space-efficient algorithm for Tree Evaluation recently found by Cook and Mertz [STOC 2024].

The third TCS+ talk of the season will take place on Wednesday, April 9th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC: check your time zone here). Or Zamir from Tel Aviv University will speak about “Optimality of Frequency Moment Estimation” (abstract below).

(Note that the talk is on April 9th, not April 2nd, to accommodate the FOCS deadline.)

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: Estimating the second frequency moment of a stream up to (1±ε) multiplicative error requires at most O(log n / ε²) bits of space, due to a seminal result of Alon, Matias, and Szegedy. It is also known that at least Ω(log n + 1/ε²) space is needed. We prove a tight lower bound of Ω(log(nε²) / ε²) for all ε = Ω(1/√n). Notably, when ε > n^(-1/2 + c), where c > 0, our lower bound matches the classic upper bound of AMS. For smaller values of ε, we also introduce a revised algorithm that improves the classic AMS bound and matches our lower bound. Our lower bound also applies to the more general problem of p-th frequency moment estimation for the range of p in (1, 2], providing a tight bound in the only remaining range to settle the optimal space complexity of estimating frequency moments.

Based on a joint work with Mark Braverman.

The second TCS+ talk of the semester will take place this coming Wednesday, March 19th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 18:00 Central European Time, 17:00 UTC). Tom Gur from the University of Cambridge will speak about “A Zero-Knowledge PCP Theorem” (abstract below).

Looking ahead, after Tom Gur we will have talks by Or Zamir (April 9th, on “Optimality of Frequency Moment Estimation”) and Ryan Williams (April 23rd, on “Simulating Time With Square-Root Space”), with a hiatus on April 2nd due to the FOCS deadline.

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: We show that every language in NP admits a probabilistically checkable proof (PCP) of polynomial length, which can be verified by only reading O(1) bits while revealing no information other than the correctness of the statement. This can be viewed as a zero-knowledge version of the PCP theorem, resolving a problem that was open since the seminal work of Kilian, Petrank and Tardos (STOC 1997).

Based on STOC 2024 and STOC 2025 papers, joint with Jack O’Connor and Nicholas Spooner.

To kick of the new season of TCS+, the first talk of the semester will take place this coming Wednesday, March 5th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Prasanna Ramakrishnan from Stanford University will tell us “How to Appease a Voter Majority” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: In 1785, Condorcet established a frustrating property of elections and majority rule: it is possible that, no matter which candidate you pick as the winner, a majority of voters will prefer someone else. You might have the brilliant idea of picking a small set of winners instead of just one, but how do you avoid the nightmare scenario where a majority of the voters prefer some other candidate over all the ones you picked? How many candidates suffice to appease a majority of the voters? In this talk, we will explore this question. Along the way, we will roll some dice — both because the analysis involves randomness and because of a connection to the curious phenomenon of intransitive dice, that has delighted recreational and professional mathematicians alike ever since Martin Gardner popularized it in 1970.

Based on joint work with Moses Charikar, Alexandra Lassota, Adrian Vetta, and Kangning Wang.

The next TCS+ talk (and the last of 2024!) will take place this coming Wednesday, December 4th at 10:30 AM Eastern Time (7:30 AM Pacific Time, 16:30 Central European Time, 15:30 UTC — note the unusual time). Martín Costa from University of Warwick will speak about “Vizing’s Theorem in Near-Linear Time” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: Vizing’s theorem states that any -vertex -edge graph of maximum degree can be edge colored using at most different colors [Vizing, 1964]. Vizing’s original proof is algorithmic and shows that such an edge coloring can be found in time. This was improved to time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985].

Very recently, independently and concurrently, this runtime bound was further improved to by [Assadi, 2024] and by [Bhattacharya, Carmon, Costa, Solomon and Zhang, 2024] (and subsequently to time by [Bhattacharya, Costa, Solomon and Zhang, 2024]).

In this talk, we present an algorithm that computes a -edge coloring in near-linear time — in fact, only time — giving a near-optimal algorithm for this fundamental problem.

The next TCS+ talk will take place this coming Wednesday, November 20th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Divyarthi Mohan from Boston University will speak about “Optimal Stopping with Interdependent Values” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: We study online selection problems in both the prophet and secretary settings, when arriving agents have interdependent values. In the interdependent values model, introduced in the seminal work of Milgrom and Weber [1982], each agent has a private signal and the value of an agent is a function of the signals held by all agents. Results in online selection crucially rely on some degree of independence of values, which is conceptually at odds with the interdependent values model. For prophet and secretary models under the standard independent values assumption, prior works provide constant factor approximations to the welfare. On the other hand, when agents have interdependent values, prior works in Economics and Computer Science provide truthful mechanisms that obtain optimal and approximately optimal welfare under certain assumptions on the valuation functions. We bring together these two important lines of work and provide the first constant factor approximations for prophet and secretary problems with interdependent values. We consider both the algorithmic setting, where agents are non-strategic (but have interdependent values), and the mechanism design setting with strategic agents. All our results are constructive and use simple stopping rules.

Joint work with Simon Mauras and Rebecca Reiffenhäuser.

Bio: Divyarthi Mohan is a postdoctoral researcher at Boston University hosted by Prof. Kira Goldner. Previously, she was a postdoc at Tel Aviv University with Prof. Michal Feldman. She obtained her PhD in Computer Science at Princeton University in July 2021 advised by Prof. Matt Weinberg. Divya’s research interest broadly lies at the intersection of computer science and economics, with a focus on algorithmic mechanism design, social learning and strategic communication. She was awarded the class of 2021 Siebel Scholarship and the Simons-Berkeley Research Fellowship for Fall 2022.