Search for: All records

Abstract We study the approximation of halfspaces $$h:\{0,1\}^n\to\{0,1\}$$ h : { 0 , 1 } n → { 0 , 1 } in theinfinity 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 boundsthat 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 achievesessentially the largest possible separation, of O(n) versus $$2^{-\Omega(n)}$$ 2 - Ω ( n ) ,between the sign-rank and discrepancy. Equivalently, our problem exhibitsa gap of log n versus $$\Omega(n)$$ Ω ( n ) between the communication complexitywith unbounded versus weakly unbounded error, improvingquadratically on previous constructions and completing a line of workstarted by Babai, Frankl, and Simon (FOCS 1986). Our results furthergeneralize to the k -party number-on-the-forehead model, where weobtain an explicit separation of log n versus $$\Omega(n/4^{n})$$ Ω ( n / 4 n ) for communication with unbounded versus weakly unbounded error.