Improved Approximation of Linear Threshold Functions

Ilias Diakonikolas, RoccoA. Servedio

Research output: Contribution to journalArticlepeer-review

Abstract

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 ϵ -close to a threshold function depending only on Inf(f)2 ⋅ poly(1/ϵ) 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 (Friedgut in Combinatorica 18(1):474–483, 1998), which states that every Boolean function f is ϵ -close to a function depending only on 2O(Inf(f)/ϵ) 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 ϵ -close to a threshold function with integer weights at most poly(n)⋅2O ~ (1/ϵ 2/3) . This is an improvement, in the dependence on the error parameter ϵ , on an earlier result of Servedio (Comput Complex 16(2):180–209, 2007) which gave a poly(n)⋅2 O ~ (1/ϵ 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 result of Servedio (Comput Complex 16(2):180–209, 2007) and extends to give low-weight approximators for threshold functions under a range of probability distributions other than the uniform distribution.
Original languageEnglish
Pages (from-to)623-677
Number of pages55
JournalComputational complexity
Volume22
Issue number3
DOIs
Publication statusPublished - 2013

Keywords

  • Threshold functions
  • total influence
  • average sensitivity
  • integer-weight approximation
  • juntas
  • 68R99

Fingerprint

Dive into the research topics of 'Improved Approximation of Linear Threshold Functions'. Together they form a unique fingerprint.

Cite this