Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SMALL-BIAS COMMUNICATION:
Reports tagged with small-bias communication:
TR19-016 | 5th February 2019
Alexander A. Sherstov

#### The hardest halfspace

We study the approximation of halfspaces $h:\{0,1\}^n\to\{0,1\}$ in the infinity 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 bounds that match the trivial upper bounds achievable for all ... more >>>

ISSN 1433-8092 | Imprint