  The well-known Kruskal-Katona theorem in combinatorics says that (under mild
conditions) every monotone Boolean function $f: \{0,1\}^n \to \{0,1\}$ has a
nontrivial "density increment." This means that the fraction of inputs of
Hamming weight $k+1$ for which $f=1$ is significantly larger than the fraction
of inputs of Hamming weight $k$ for which $f=1.$
  We prove an analogous statement for convex sets. Informally, our main result
says that (under mild conditions) every convex set $K \subset \mathbb{R}^n$ has
a nontrivial density increment. This means that the fraction of the radius-$r$
sphere that lies within $K$ is significantly larger than the fraction of the
radius-$r'$ sphere that lies within $K$, for $r'$ suitably larger than $r$. For
centrally symmetric convex sets we show that our density increment result is
essentially optimal.
  As a consequence of our Kruskal-Katona type theorem, we obtain the first
efficient weak learning algorithm for convex sets under the Gaussian
distribution. We show that any convex set can be weak learned to advantage
$\Omega(1/n)$ in $\mathsf{poly}(n)$ time under any Gaussian distribution and
that any centrally symmetric convex set can be weak learned to advantage
$\Omega(1/\sqrt{n})$ in $\mathsf{poly}(n)$ time. We also give an
information-theoretic lower bound showing that the latter advantage is
essentially optimal for $\mathsf{poly}(n)$ time weak learning algorithms. As
another consequence of our Kruskal-Katona theorem, we give the first nontrivial
Gaussian noise stability bounds for convex sets at high noise rates. Our
results extend the known correspondence between monotone Boolean functions over
$ \{0,1\}^n$ and convex bodies in Gaussian space.
