Uploaded May 2026 | Updated September 2026, 3 weeks ago
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.
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.
