Convex Set Disjointness, Distributed Learning of Halfspaces, and LP
  Feasibility
  We study the Convex Set Disjointness (CSD) problem, where two players have
input sets taken from an arbitrary fixed domain~$U\subseteq \mathbb{R}^d$ of
size $\lvert U\rvert = n$. Their mutual goal is to decide using minimum
communication whether the convex hulls of their sets intersect (equivalently,
whether their sets can be separated by a hyperplane).
  Different forms of this problem naturally arise in distributed learning and
optimization: it is equivalent to {\em Distributed Linear Program (LP)
Feasibility} -- a basic task in distributed optimization, and it is tightly
linked to {\it Distributed Learning of Halfdpaces in $\mathbb{R}^d$}. In
{communication complexity theory}, CSD can be viewed as a geometric
interpolation between the classical problems of {Set Disjointness} (when~$d\geq
n-1$) and {Greater-Than} (when $d=1$).
  We establish a nearly tight bound of $\tilde \Theta(d\log n)$ on the
communication complexity of learning halfspaces in $\mathbb{R}^d$. For Convex
Set Disjointness (and the equivalent task of distributed LP feasibility) we
derive upper and lower bounds of $\tilde O(d^2\log n)$ and~$\Omega(d\log n)$.
These results improve upon several previous works in distributed learning and
optimization.
  Unlike typical works in communication complexity, the main technical
contribution of this work lies in the upper bounds. In particular, our
protocols are based on a {\it Container Lemma for Halfspaces} and on two
variants of {\it Carath\'eodory's Theorem}, which may be of independent
interest. These geometric statements are used by our protocols to provide a
compressed summary of the players' input.
