Learning convex bodies is hard
  We show that learning a convex body in $\RR^d$, given random samples from the
body, requires $2^{\Omega(\sqrt{d/\eps})}$ samples. By learning a convex body
we mean finding a set having at most $\eps$ relative symmetric difference with
the input body. To prove the lower bound we construct a hard to learn family of
convex bodies. Our construction of this family is very simple and based on
error correcting codes.
