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.