Fall 2018

The Hardest Halfspace

Monday, October 15th, 2018 9:30 am10:30 am

Add to Calendar


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.

PDF icon The Hardest Halfspace4.64 MB