  We study the problems of testing and learning high-dimensional discrete
convex sets. The simplest high-dimensional discrete domain where convexity is a
non-trivial property is the ternary hypercube, $\{-1,0,1\}^n$. The goal of this
work is to understand structural combinatorial properties of convex sets in
this domain and to determine the complexity of the testing and learning
problems. We obtain the following results.
  Structural: We prove nearly tight bounds on the edge boundary of convex sets
in $\{0,\pm 1\}^n$, showing that the maximum edge boundary of a convex set is
$\widetilde \Theta(n^{3/4}) \cdot 3^n$, or equivalently that every convex set
has influence $\widetilde{O}(n^{3/4})$ and a convex set exists with influence
$\Omega(n^{3/4})$.
  Learning and sample-based testing: We prove upper and lower bounds of
$3^{\widetilde{O}(n^{3/4})}$ and $3^{\Omega(\sqrt{n})}$ for the task of
learning convex sets under the uniform distribution from random examples. The
analysis of the learning algorithm relies on our upper bound on the influence.
Both the upper and lower bound also hold for the problem of sample-based
testing with two-sided error. For sample-based testing with one-sided error we
show that the sample-complexity is $3^{\Theta(n)}$.
  Testing with queries: We prove nearly matching upper and lower bounds of
$3^{\widetilde{\Theta}(\sqrt{n})}$ for one-sided error testing of convex sets
with non-adaptive queries.
