Time: Thursdays, typically 12:00pm to 1:00pm. Lunch is served at 12:00pm; the talk starts at 12:30pm.
Location: Theory lunch is typically in CoDa E160. Make sure to subscribe to the mailing list (details below) for announcements with updated location information. This term, some of the lunches will be in Gates 403.
Mailing list: thseminar@cs.stanford.edu. You can add or remove yourself from the list using this link.
Contact: Sílvia Casacuberta (scasac [at] stanford [dot] edu). Send questions, comments, or requests to speak.
To hear about upcoming talks, join the mailing list! For previous quarter talks see the theory lunch archives.
Mohit Gurumukhani (Cornell University)
A Resolution of Friedgut's Conjecture on Influential Coalitions
In Friedgut'04, the following conjecture was proposed: For any monotone Boolean function on [0,1]^n, there exists a coalition of o(n) coordinates and a target output b in {0, 1} such that after the remaining coordinates are sampled uniformly and independently, the coalition can choose its values to make the output of f equal to b with probability at least 0.99. We resolve this conjecture, showing that for any f, there exists such a coalition of size O(n / sqrt(log n)), biasing it towards some output.
In collective coin flipping, our result gives the first sublinear bound on the number of bad players that can bias any one-round coin flipping protocol with independent uniform messages, regardless of the message length. In pseudorandomness, this shows that deterministically extracting from NOSF sources with O(n / sqrt(log n)) bad coordinates is impossible.
A key ingredient in our proof is an encoding that lets us relate the influence of a function on a product space to the p-biased influence of the encoded function. We then rely on a structure theorem of Hatami'12 for functions with small p-biased influence to bias the encoded function.
Based on joint work with Eshan Chattopadhyay.
Jesse Goodman (UC Berkeley)
Title TBD
Jordan Docter (Stanford University)
Title TBD
Aniket Das (Stanford University)
Reaching the Algorithmic Threshold for Tensor PCA via Local Markov Chains
We study the tensor principal component analysis (tensor PCA problem) in the spiked tensor model, where the task is to recover an unknown vector on the signed hypercube {±1}N or the sphere 𝕊N−1(√N) from a noisy observation of its k-th tensor power, for some fixed k ≥ 3. This is a canonical planted problem in average case complexity, which exhibits a well-studied information-computation gap: global algorithms such as spectral methods and sum-of-squares work above an algorithmic threshold, below which we know matching lower bounds (against these and some other restricted models of computation).
In contrast, local algorithms such as Markov chains were only known to succeed from a random initialization at a polynomially larger signal-to-noise ratio, and were believed to be inferior to global algorithms for tensor PCA.
We show that two canonical local Markov chains, Glauber dynamics on the hypercube and Langevin dynamics on the sphere, once supplemented with annealing and ergodic averaging, achieve polynomial-time strong recovery above the algorithmic threshold from a uniformly random initialization. Our results demonstrate that algorithms based on local Markov chains can succeed all the way down to the algorithmic threshold for planted average-case problems, even from an uninformative cold start.
Based on joint works with Tselil Schramm.
Addison Prairie (Stanford University)
Title TBD
Itay Cohen (Tel Aviv University)
Good Quantum Locally Testable Codes from Lossless Cubical Complexes
We show that certain lossless four-dimensional cubical complexes yield quantum locally testable codes with constant rate, linear distance, and constant soundness. The key ingredient is a local-to-global theorem connecting lossless expansion of directional graphs to small-set coboundary expansion of the associated level chain complex. Constructing such cubical complexes remains open.
Joint work with Itai Leigh, Assaf Reiner, Amnon Ta-Shma, and Elad Tzalik.
Noam Ringach (Cornell University)
Two sided product expansion via Rademacher matrices: the case for analyzing random codes over the reals
Random codes over finite fields have been immensely useful in coding theory as both a benchmark of what is possible, indicating what constructions should strive to achieve, and as gadgets in explicit constructions themselves. As an example of the latter case, beginning with the work of Dinur, Lin, and Vidick (FOCS, 2024), tensor codes with constant product expansion have been foundational to recent advances in quantum locally testable codes (qLTCs) based on cubical complexes. Kalachev and Panteleev (FOCS, 2025) showed that these tensor codes can be taken as the product of random linear codes.
However, while most properties of random codes are easy to show via the standard probabilistic method, showing a random tensor code has good product expansion is quite difficult. Indeed, [KP’25] require the use of explicit good locally testable codes (c3-LTCs) for their existential proof. As a consequence, their proof technique is inflexible and cannot generalize to other settings where the component codes of the tensor code are required to have large automorphism groups or the code isn’t exactly the tensor product of individual codes.
In this talk, I will overview how we manage to give a purely existential proof of product expansion by analyzing random codes generated by real matrices with Rademacher random variable entries. To avoid using c3-LTCs, we develop several new techniques that we view as interesting in their own right. Surprisingly, we show that the problem reduces to a nice combinatorial problem involving counting closed walks on bipartite graphs where each edge is traversed an even number of times.
Due to our techniques not relying on explicit c3-LTCs, we believe that they form a promising starting point towards showing the existence of product expanding tensor codes where the component codes have non-trivial automorphism groups and coboundary expanding codes that could be used as the local codes of non-cubical complexes, such as simplicial complexes. Overall, we offer a different random model and novel techniques for studying the product expansion of random linear codes.
This is joint work with Eshan Chattopadhyay and Nick Spooner.
Theory faculty (Stanford University)
Theory of CS: a discussion with the Theory faculty
The remarkable progress of AI models in recent months is impacting everyone in the Theory of Computer Science (TCS) community. Please join us at this theory lunch for an open discussion with the theory faculty on the state of TCS, and how it will evolve in the coming years.
Rahul Saha and Alan Li (UT Austin)
New Bounds on the Grothendieck Constant via Long Horizon AI Assisted Research
The Grothendieck constant (K_G) is a fundamental quantity measuring the worst-case gap between a particular class of integer quadratic optimization problem and its efficiently solvable semidefinite programming relaxation. It has found diverse applications in fields such as functional analysis, combinatorial optimization, theoretical computer science, and quantum information theory.
Its value has remained open since its introduction by Alexander Grothendieck over 70 years ago, despite sustained interest from the mathematical community. Our work determines the tenths digit for the first time, proving (6π/11 < K_G < π/(2log(1+√2)) - 10^−4). We will describe the technical details of these improvements, which relies on conceptually new approaches to both sides of the problem: new asymptotic rounding schemes for the upper bound, and a lower-bound method based on proving fundamental limitations of entire classes of rounding schemes rather than constructing individual hard instances.
We will describe the AI research system we built, and the roles played by both AI and human researchers throughout the process. Finally, we will discuss what this experience suggests about the importance of human research judgement and the future of human-AI collaboration.
Aviad Rubinstein (Stanford University)
Secretary problem: recent (and not so recent) advances
I will try to cover recent advances in choose-many variants of the secretary problem, including general downward closed constraints (based on my joint work with Sahil Singla) and matroid constraints (Sahil's breakthrough from 2 weeks ago).
George Li (CMU)
Bellman-Ford in Almost-Linear Time
We consider the single-source shortest paths problem on a directed graph with real-valued (possibly negative) edge weights and solve this problem in m^{1+o(1)} time.