Teaching and compressing for low VC-dimension
  In this work we study the quantitative relation between VC-dimension and two
other basic parameters related to learning and teaching. Namely, the quality of
sample compression schemes and of teaching sets for classes of low
VC-dimension. Let $C$ be a binary concept class of size $m$ and VC-dimension
$d$. Prior to this work, the best known upper bounds for both parameters were
$\log(m)$, while the best lower bounds are linear in $d$. We present
significantly better upper bounds on both as follows. Set $k = O(d 2^d \log
\log |C|)$.
  We show that there always exists a concept $c$ in $C$ with a teaching set
(i.e. a list of $c$-labeled examples uniquely identifying $c$ in $C$) of size
$k$. This problem was studied by Kuhlmann (1999). Our construction implies that
the recursive teaching (RT) dimension of $C$ is at most $k$ as well. The
RT-dimension was suggested by Zilles et al. and Doliwa et al. (2010). The same
notion (under the name partial-ID width) was independently studied by Wigderson
and Yehudayoff (2013). An upper bound on this parameter that depends only on
$d$ is known just for the very simple case $d=1$, and is open even for $d=2$.
We also make small progress towards this seemingly modest goal.
  We further construct sample compression schemes of size $k$ for $C$, with
additional information of $k \log(k)$ bits. Roughly speaking, given any list of
$C$-labelled examples of arbitrary length, we can retain only $k$ labeled
examples in a way that allows to recover the labels of all others examples in
the list, using additional $k\log (k)$ information bits. This problem was first
suggested by Littlestone and Warmuth (1986).
