Improved Approximation of Linear Threshold Functions

Original · EN

We prove two main results on how arbitrary linear threshold functions f(x) = (w· x - θ) over the n-dimensional Boolean hypercube can be approximated by simple threshold functions. Our first result shows that every n-variable threshold function f is -close to a threshold function depending only on (f)² · (1/) many variables, where (f) denotes the total influence or average sensitivity of f. This is an exponential sharpening of Friedgut's well-known theorem Friedgut:98, which states that every Boolean function f is -close to a function depending only on 2O((f)/) many variables, for the case of threshold functions. We complement this upper bound by showing that Ω((f)² + 1/ε²) many variables are required for ε-approximating threshold functions. Our second result is a proof that every n-variable threshold function is -close to a threshold function with integer weights at most (n) · 2O(1/²/³). This is a significant improvement, in the dependence on the error parameter, on an earlier result of Servedio:07cc which gave a (n) · 2O(1/²) bound. Our improvement is obtained via a new proof technique that uses strong anti-concentration bounds from probability theory. The new technique also gives a simple and modular proof of the original Servedio:07cc result, and extends to give low-weight approximators for threshold functions under a range of probability distributions beyond just the uniform distribution.