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.
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.
Noam Ringach (Cornell University)
Title TBD
Itay Cohen (Tel Aviv University)
Title TBD
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.
Jordan Docter (Stanford University)
Title TBD
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.