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.
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.
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.
Joshua Brakensiek (UC Berkeley)
Algorithmic List Decoding of Reed-Solomon Codes up to Capacity
In coding theory, the list-decoding problem asks to find all codewords of a given code which are sufficiently close to a received message. In this talk, I'll present the classical algorithms of Sudan and Guruswami-Sudan for list-decoding Reed-Solomon codes up to the Johnson radius. I will also describe a new technique which allows for the efficient decoding of many Reed-Solomon codes up to capacity.
Joint work with Yeyuan Chen, Aaron Putterman, Zihan Zhang, and Kai Zhe Zheng.
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.
Jordan Docter (Stanford University)
Title TBD
Noam Ringach (Cornell University)
Title TBD