Structure vs. Randomness

ABSTRACT

The "structure vs. randomness" paradigm decomposes complex mathematical objects like graphs, functions, or sets into structured and random-like components. While this framework has been wildly successful in pure mathematics and extremal combinatorics, its broader application in computer science has historically been bottlenecked by quantitative efficiency. In my talk, I will present recent work that overcomes these traditional quantitative barriers, leading to near-exponential improvements in structure vs. randomness methods. I will discuss how novel techniques like "sifting" and "spectral positivity", originally developed to achieve breakthrough upper bounds for the classic Erdős-Turán problem on three-term arithmetic progressions (3APs), can be directly translated to the graph-theoretic setting. By adapting these methods, we unlock new results for fundamental computer science problems, including a quasipolynomial improvement for combinatorial triangle detection in graphs and a strong explicit separation between the power of randomized and deterministic multiparty communication protocols.

.

BIOGRAPHY

Zander Kelley is a Postdoctoral Member in the School of Mathematics at the Institute for Advanced Study. His research develops and applies the paradigm of structure versus randomness to fundamental problems in computer science and extremal combinatorics. His work has been recognized with a Frontiers of Science Award and an ACM Doctoral Dissertation Honorable Mention Award. Additionally, his research on 3-progressions received a FOCS Best Paper Award and was featured in Quanta Magazine's "2023 Biggest Breakthroughs in Math". He received his Ph.D. in Computer Science from the University of Illinois at Urbana-Champaign in 2024, where he was advised by Michael A. Forbes , and holds B.S. degrees in Computer Science and Mathematics from Texas A&M University.