Open Collections

The hardest halfspace

Banff International Research Station for Mathematical Innovation and Discovery

Pointwise (i.e., infinity-norm) approximation by polynomials has produced a treasure trove of efficient learning algorithms under arbitrary distributions for fundamental concept classes. A notable exception is the intersection of two halfspaces on {0,1}^n, shown 8 years ago (STOC 2010) to require a polynomial of the maximum possible degree, Omega(n), even for representation by sign (the weakest form of pointwise approximation). The proof was based on the probabilistic method, and the explicit construction of such an intersection of two halfspaces has remained an open problem. We solve this problem here, with an explicit construction of a halfspace h:{0,1}^n -> {-1,+1} such that the intersection of two copies of h cannot be represented by the sign of a polynomial of degree less than Omega(n). We further show that h by itself is the ``hardest'' of halfspaces for pointwise approximation by polynomials and rational functions, and determine the minimum error achievable by approximants of any given degree. This completes a line of work started by Myhill and Kautz (1961). We discuss applications to separating communication complexity classes. 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 are appear random modulo m in the sense of the discrete Fourier transform on Z/mZ.

Mathematics; Computer science; Fourier analysis; Theoretical computer science

video/mp4

Author affiliation: UCLA

2019-03-28

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/69314

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/