  We study the approximation of halfspaces $h:\{0,1\}^n\to\{0,1\}$ in the
infinity norm by polynomials and rational functions of any given degree. Our
main result is an explicit construction of the "hardest" halfspace, for which
we prove polynomial and rational approximation lower bounds that match the
trivial upper bounds achievable for all halfspaces. This completes a lengthy
line of work started by Myhill and Kautz (1961).
  As an application, we construct a communication problem that achieves
essentially the largest possible separation, of $O(n)$ versus $2^{-\Omega(n)},$
between the sign-rank and discrepancy. Equivalently, our problem exhibits a gap
of $\log n$ versus $\Omega(n)$ between the communication complexity with
unbounded versus weakly unbounded error, improving quadratically on previous
constructions and completing a line of work started by Babai, Frankl, and Simon
(FOCS 1986). Our results further generalize to the $k$-party
number-on-the-forehead model, where we obtain an explicit separation of $\log
n$ versus $\Omega(n/4^{n})$ for communication with unbounded versus weakly
unbounded error. This gap is a quadratic improvement on previous work and
matches the state of the art for number-on-the-forehead lower bounds.
