Improved Approximation of Linear Threshold Functions

We prove two main results on how arbitrary linear threshold functions $f(x) = \sign(w\cdot x - \theta)$overthe$n$-dimensional Boolean hypercube can be approximated by simple threshold functions. Our first result shows that every $n$-variable threshold function $f$ is $\text{eps}$-close to a threshold function depending only on $\Inf(f)^2 \cdot \poly(1/\eps)$manyvariables,where$\Inf(f)$ denotes the total influence or average sensitivity of $f\mathrm{.}$ This is an exponential sharpening of Friedgut’s well-known theorem \cite{Friedgut:98}, which states that every Boolean function $f$ is $\text{eps}$-close to a function depending only on $2^{O(\text{Inf}(f)\mathrm{/}\text{eps})}$ many variables, for the case of threshold functions. We complement this upper bound by showing that $\mathrm{\Omega }(\text{Inf}(f{)}^2+1\mathrm{/}{ϵ}^2)$ many variables are required for $ϵ$-approximating threshold functions. Our second result is a proof that every $n$-variable threshold function is $\text{eps}$-close to a threshold function with integer weights at most $\poly(n) \cdot 2^{\tilde{O}(1/\eps^{2/3})}.$ This is a significant improvement, in the dependence on the error parameter $\text{eps}$, on an earlier result of \cite{Servedio:07cc} which gave a $\text{poly}(n)\cdot 2^{\tilde{O}(1\mathrm{/}{\text{eps}}^2)}$ 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 \cite{Servedio:07cc} result, and extends to give low-weight approximators for threshold functions under a range of probability distributions beyond just the uniform distribution.