Uploaded June 2026 | Updated November 2026, 7 hours ago
Constantin Kogler, Member in the School of Mathematics (2025–26), explores "random walks"—a mathematical concept foundational to physics, finance, and even neural networks. He also reflects on the feeling of working in the place where founding IAS Professor Albert Einstein authored his closely related paper on Brownian motion.
Institute Instances is a collection of 1–2 minute video snapshots of scholars, administrators, and visitors to the Institute for Advanced Study answering a question (or two) about their work at IAS. Viewed individually, these clips allow audiences to get to know the people who are, in the words of founding IAS Director Abraham Flexner, "pushing beyond the present limits of human knowledge" through advancements in science and the humanities. Taken together, these "instances" of Institute life are designed to show how everyone can play a role in actualizing discovery, and to celebrate a community devoted to excellence in scholarship.
Find out more about Institute Instances: https://www.ias.edu/institute-instances
Constantin Kogler, Member in the School of Mathematics (2025–26), explores "random walks"—a mathematical concept foundational to physics, finance, and even neural networks. He also reflects on the feeling of working in the place where founding IAS Professor Albert Einstein authored his closely related paper on Brownian motion.
Institute Instances is a collection of 1–2 minute video snapshots of scholars, administrators, and visitors to the Institute for Advanced Study answering a question (or two) about their work at IAS. Viewed individually, these clips allow audiences to get to know the people who are, in the words of founding IAS Director Abraham Flexner, "pushing beyond the present limits of human knowledge" through advancements in science and the humanities. Taken together, these "instances" of Institute life are designed to show how everyone can play a role in actualizing discovery, and to celebrate a community devoted to excellence in scholarship.
Find out more about Institute Instances: https://www.ias.edu/institute-instances
![An Average-Degree Bound for Hamming Hypergraphs, with Applications to Optimal PAC...- Nataly Brukhim
Computer Science/Discrete Mathematics Seminar II
10:30am|Simonyi 101 and Remote Access
Topic: An Average-Degree Bound for Hamming Hypergraphs, with Applications to Optimal PAC Learning
Speaker: Nataly Brukhim
Affiliation: Institute for Advanced Study
Date: May 26, 2026
I will describe recent breakthrough results in multiclass PAC learning that characterize the optimal sample complexity. The talk will discuss recent work of Chirag Pabbaraju, as well as work of Steve Hanneke, Qinglin Meng, Shay Moran, and Amirreza Shaeiri.
Determining the optimal sample complexity reduces to a structural question about the Hamming-graph representation of the hypothesis class. These are hypergraphs whose vertices lie in [k]^n, where each set of vertices that agree on all coordinates except one forms an edge. It has been shown that bounding the average degree of these hypergraphs yields bounds on the sample complexity of learning. A long-standing conjecture was that this average degree can be controlled by the Daniely–Shalev-Shwartz dimension, a combinatorial dimension introduced in 2014.
The DS dimension is a natural generalization of the VC dimension, and was shown to bound the sample complexity of multiclass PAC learning in joint work with Carmon, Dinur, Moran, and Yehudayoff (2022). However, the correct dependence on the dimension remained open, with a polynomial gap between the upper and lower bounds. The recent work of Pabbaraju closes this gap by resolving the average-degree conjecture. The proof is based on a simple linear-algebraic method, which I will describe in the talk. An Average-Degree Bound for Hamming Hypergraphs, with Applications to Optimal PAC...- Nataly Brukhim](https://i.ytimg.com/vi/g_wp-OhFxeU/mqdefault.jpg)









