TCS+

The next TCS+ talk (and first of the season!) will take place this coming Wednesday, September 16th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Tselil Schramm from Stanford University will give a survey talk about “10 years of the low-degree framework in average-case complexity” (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: The low-degree framework is a method for studying the computational complexity of average-case (planted) problems. The framework emerged 10 years ago in the context of sum-of-squares lower bounds, and has since been influential in TCS and beyond. In this survey talk I will introduce the framework, then highlight a few results that have emerged in this decade of study.

The next TCS+ talk will take place this coming Wednesday, May 20th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Shyamal Patel from Columbia University will speak about “Learning Functions of Halfspaces” (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: Learning halfspaces is one of the most basic and fundamental problems in learning theory. While we have a good understanding of the problem, simple generalizations such as learning an intersection of halfspaces appear much more challenging. While learning an intersection of halfspaces can be done efficiently if we assume our data is drawn from a uniform or log-concave distribution, there are large gaps in our understanding when we make no assumptions on the background distribution. In particular, even for learning an intersection of two halfspaces, we have no non-trivial learning algorithms and no evidence that the problem requires super-polynomial time.
In this talk, we’ll describe a sub-exponential time algorithm for learning an intersection of halfspaces and more generally for learning an arbitrary function of halfspaces (joint work with Josh Alman and Rocco Servedio).

The next TCS+ talk will take place this coming Wednesday, April 22th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Yichuan Wang from UC Berkeley will speak about “Superquadratic Lower Bounds for Depth-2 Linear Threshold Circuits” (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: Proving lower bounds against depth-2 linear threshold circuits (a.k.a. THR ◦ THR) is one of the frontier questions in complexity theory. Despite tremendous effort, our best lower bounds for THR ◦ THR only hold for sub-quadratic number of gates, which was proven a decade ago by Tamaki (ECCC TR16) and Alman, Chan, and Williams (FOCS 2016) for a hard function in E^NP.

In this work, we prove that there is a function f in E^NP that requires -size THR ◦ THR circuits for any . We obtain our new results by designing a new non-trivial algorithm for estimating the acceptance probability of an XOR of two -size THR ◦ THR circuits, and apply Williams’ algorithmic method to obtain the desired lower bound.

The next TCS+ talk will take place this coming Wednesday, April 8th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Rahul Ilango from MIT will speak about “Gödel in Cryptography: Zero-Knowledge Proofs With No Interaction, No Setup, and Perfect Soundness” (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: Gödel showed that there are true but unprovable statements. This was bad news for Hilbert, who hoped that every true statement was provable. In this talk, I’ll describe why Gödel’s result is, in fact, good news for cryptography.

Specifically, Gödel’s result allows for the following strange scenario: a cryptographic system S is insecure, but it is impossible to prove that S is insecure. As I will explain, in this scenario (defined carefully), S is secure for nearly all practical purposes.

Leveraging this idea, we effectively construct — under longstanding assumptions — a classically-impossible cryptographic dream object: “zero-knowledge proofs for NP with no interaction, no setup, and perfect soundness” (I won’t assume you know what this means!). As an application, our result lets one give an ordinary mathematical proof that a Sudoku puzzle is solvable without revealing how to solve it. Previously, it was not known how to do this.

Paper link: https://eccc.weizmann.ac.il/report/2025/095/

“The next TCS+ talk will take place this coming Wednesday, March 18th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 18:00 Central European Time, 17:00 UTC). Chris Gartland from UNC Charlotte will speak about “”-Distortion of EMD over Grids“” (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: The Earth Mover Distance (EMD) is a popular metric used in the comparison of probability distributions over a metric space, and low-distortion embeddings of this metric into is a commonly used approximation tool. We will discuss a general technique of using Sobolev-type inequalities to prove lower bounds for the -distortion of EMD. While the main focus will be on describing the specific Sobolev-type inequality for the planar grid , we will also mention results for the higher dimensional grids , . Based on joint work with Mikhail Ostrovskii, Yuval Rabani, and Robert Young.

“

It hath begun 🎉! The first TCS+ talk of 2026 will take place next week, Wednesday, March 4th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Sophie Huiberts from CNRS will speak about “Analyzing the Simplex Method by the Book” (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: The simplex method is an algorithm for linear programming, and this algorithm is much faster than theory is able to explain. In this talk I will describe a new theoretical framework we introduced to address this question. Under this framework we prove strong running time guarantees, using new mathematical assumptions taken from LP software user manuals. I will discuss which features of real-world software and LP’s we have managed to theoretically capture for this purpose, and what will come next.

The next (and last of the season!) TCS+ talk will take place this coming Wednesday, December 3rd at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Natalie Collina from U Penn will speak about “Swap regret and correlated equilibria beyond normal-form games ” (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: Swap regret is a notion that has proven itself to be central to the study of general-sum normal-form games, with swap-regret minimization leading to convergence to the set of correlated equilibria and guaranteeing non-manipulability against a self-interested opponent. However, the situation for more general classes of games – such as Bayesian games and extensive-form games – is less clear-cut, with multiple candidate definitions for swap-regret but no known efficiently minimizable variant of swap regret that implies analogous non-manipulability guarantees. In this paper, we present a new variant of swap regret for polytope games that we call “profile swap regret”, with the property that obtaining sublinear profile swap regret is both necessary and sufficient for any learning algorithm to be non-manipulable by an opponent (resolving an open problem of Mansour et al., 2022). Although we show profile swap regret is NP-hard to compute given a transcript of play, we show it is nonetheless possible to design efficient learning algorithms that guarantee at most O(√T) profile swap regret. Finally, we explore the correlated equilibrium notion induced by low-profile-swap-regret play, and demonstrate a gap between the set of outcomes that can be implemented by this learning process and the set of outcomes that can be implemented by a third-party mediator (in contrast to the situation in normal-form games).

A guest post by the General Chair of FOCS 2025, Clément Canonne.

FOCS 2025 is less than a month away, with an early bird deadline coming up on November 21, and the summer sun already shining in Sydney. Below are a few important announcements, not necessarily only relevant to attendees (though we do hope you will attend!):

Graduating Bits (afternoon, Sunday – Day 1): Following the (now) long-standing tradition initiated at ITCS, graduating PhD students and postdoctoral researchers will give short 2-minute presentations introducing themselves, their research interests and plans. Many of these junior researchers will be looking for positions in the upcoming year. Please see 🔗 this page to register as a presenter, and for their slides and information after the event.

Job Openings Spreadsheet (asynchronous): The 🔗 Job Openings page has a spreadsheet with information about job openings in Theoretical CS, to help graduating students and junior researchers. If your group plans to hire a postdoc, or a researcher (e.g., in industry), you can use the following form to provide information about the position: https://forms.gle/JSCaHfV5pVGCLXhM7.

Job Applicants Form: To complement the above two initiatives, If you are on the job market, you can provide your information at this form: https://forms.gle/ipAQg4cmBsmj3gwu6 . This will not be made public, and only shared with the FOCS 2025 sponsors and relevant parties/attendees for them to contact you during FOCS.

Visa: if you need a visa letter (esp. as a presenter), please reach out to the general chair ASAP for a letter: [email protected]. You can check how to obtain a visa, and which visa to apply to (including ETA for American citizens) on this government website.

Childcare support: To reduce barriers to attendance, we will try to facilitate childcare for the duration of the conference. We have some limited funding, thanks to our Australian sponsors, to provide partial childcare support to attendees, with as little red tape or administrative overhead on your end as possible: see this page for details

Satellite events: there will be two free “unaffiliated” satellite events, both held at the University of Sydney, prior and after the conference: “A Celebration of TCS,” December 11–13, and “Trends in Approximation and Online Algorithms,” December 18–19. See this page for more details.

The next TCS+ talk will take place this coming Wednesday, November 19th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Haotian Jiang from U Chicago will speak about “Beck-Fiala and Komlós Bounds Beyond Banaszczyk” (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: The Beck-Fiala Conjecture asserts that any set system of n elements with degree k has combinatorial discrepancy . A substantial generalization is the Komlós Conjecture, which states that any m by n matrix with columns of unit Euclidean length has discrepancy O(1).

In this talk, we describe an bound for the Komlós problem, improving upon the bound due to Banaszczyk from 1998. We will also see how these ideas can be used to resolve the Beck-Fiala Conjecture for , and give a bound for smaller k, which improves upon Banaszczyk’s bound. These results are based on a new technique of “Decoupling via Affine Spectral Independence” in designing rounding algorithms, which might also be useful in other contexts.

This talk is based on joint work with Nikhil Bansal (University of Michigan).

The next TCS+ talk will take place this coming Wednesday, November 5th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Aparna Gupte from MIT will speak about “Quantum One-Time Programs, Revisited” (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: One-time programs (Goldwasser, Kalai and Rothblum, CRYPTO 2008) are functions that can be run on any single input of a user’s choice, but not on a second input. Classically, they are unachievable without trusted hardware, but the destructive nature of quantum measurements seems to provide a quantum path to constructing them. Unfortunately, Broadbent, Gutoski and Stebila showed that even with quantum techniques, a strong notion of one-time programs, similar to ideal obfuscation, cannot be achieved for any non-trivial quantum function. On the positive side, Ben-David and Sattath (Quantum, 2023) showed how to construct a one-time program for a certain (probabilistic) digital signature scheme, under a weaker notion of one-time program security.

There is a vast gap between achievable and provably impossible notions of one-time program security, and it is unclear what functionalities are one-time programmable under the achievable notions of security.In this work, we present new, meaningful, yet achievable definitions of one-time program security for probabilistic classical functions. We show how to construct one time programs satisfying these definitions for all functions in the classical oracle model and for constrained pseudorandom functions in the plain model. Finally, we examine the limits of these notions: we show a class of functions which cannot be one-time programmed in the plain model, as well as a class of functions which appears to be highly random given a single query, but whose one-time program must leak the entire function, even in the oracle model.

This is joint work with Jiahui Liu, Justin Raizes, Bhaskar Roberts, and Vinod Vaikuntanathan.