  We prove various theorems on approximation using polynomials with integer
coefficients in the Bernstein basis of any given order. In the extreme, we draw
the coefficients from $\{ \pm 1\}$ only. A basic case of our results states
that for any Lipschitz function $f:[0,1] \to [-1,1]$ and for any positive
integer $n$, there are signs $\sigma_0,\dots,\sigma_n \in \{\pm 1\}$ such that
$$\left |f(x) - \sum_{k=0}^n \sigma_k \, \binom{n}{k} x^k (1-x)^{n-k} \right |
\leq \frac{C (1+|f|_{\mathrm{Lip}})}{1+\sqrt{nx(1-x)}} ~\mbox{ for all } x \in
[0,1].$$ More generally, we show that higher accuracy is achievable for
smoother functions: For any integer $s\geq 1$, if $f$ has a Lipschitz
$(s{-}1)$st derivative, then approximation accuracy of order $O(n^{-s/2})$ is
achievable with coefficients in $\{\pm 1\}$ provided $\|f \|_\infty < 1$, and
of order $O(n^{-s})$ with unrestricted integer coefficients, both uniformly on
closed subintervals of $(0,1)$ as above. Hence these polynomial approximations
are not constrained by the saturation of classical Bernstein polynomials. Our
approximations are constructive and can be implemented using feedforward neural
networks whose weights are chosen from $\{\pm 1\}$ only.
