Abstract
We study the infinity-norm approximation of halfspaces h:{0,1}^n->{0,1} by polynomials and rational functions. We determine the minimum error to which approximants of any given degree can approximate the worst-case halfspace, and construct this "hardest" halfspace explicitly. As an application, we construct a communication problem with the largest possible gap between sign-rank and discrepancy (or equivalently, communication complexity with unbounded versus weakly bounded error), improving quadratically on previous constructions. The proof features elements of approximation theory, random walks, and number theory. Our starting point is the construction, due to Ajtai et al. (1990), of a set of O(log m) of integers that appear random modulo m in the sense of the discrete Fourier transform on Z/mZ.