2009/10/19 by Ilias Diakonikolas, Rocco A. Servedio, Diakonikolas, Ilias +1 · 2 citations
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.0910.3719
openalex publication_date 2009/10/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We prove two main results on how arbitrary linear threshold functions f(x) = \sign(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 \eps-close to a threshold function depending only on \Inf(f)2 ⋅ \poly(1/\eps) many variables, where \Inf(f) denotes the total influence or average sensitivity of f. This is an exponential sharpening of Friedgut's well-known theorem \citeFriedgut:98, which states that every Boolean function f is \eps-close to a function depending only on 2O(\Inf(f)/\eps) many variables, for the case of threshold functions. We complement this upper bound by showing that Ω(\Inf(f)2 + 1/ε2) many variables are required for ε-approximating threshold functions. Our second result is a proof that every n-variable threshold function is \eps-close to a threshold function with integer weights at most \poly(n) ⋅ 2^O(1/\eps2/3). This is a significant improvement, in the dependence on the error parameter \eps, on an earlier result of \citeServedio:07cc which gave a \poly(n) ⋅ 2^O(1/\eps2) 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 \citeServedio:07cc result, and extends to give low-weight approximators for threshold functions under a range of probability distributions beyond just the uniform distribution.