  A classical result in learning theory shows the equivalence of PAC
learnability of binary hypothesis classes and the finiteness of VC dimension.
Extending this to the multiclass setting was an open problem, which was settled
in a recent breakthrough result characterizing multiclass PAC learnability via
the DS dimension introduced earlier by Daniely and Shalev-Shwartz. In this work
we consider list PAC learning where the goal is to output a list of $k$
predictions. List learning algorithms have been developed in several settings
before and indeed, list learning played an important role in the recent
characterization of multiclass learnability. In this work we ask: when is it
possible to $k$-list learn a hypothesis class? We completely characterize
$k$-list learnability in terms of a generalization of DS dimension that we call
the $k$-DS dimension. Generalizing the recent characterization of multiclass
learnability, we show that a hypothesis class is $k$-list learnable if and only
if the $k$-DS dimension is finite.
