Polynomial Threshold Functions for Decision Lists
share
For S ⊆{0,1}^n a Boolean function f S →{-1,1} is a polynomial threshold function (PTF) of degree d and weight W if there is an integer polynomial p of degree d and with sum of absolute coefficients W such that f(x) = sign p(x) for all x ∈ S. We study representation of decision lists as PTFs over Boolean cube {0,1}^n and over Hamming ball {0,1}^n_≤ k. As our first result we show that for all d = O( ( n/log n)^1/3) any decision list over {0,1}^n can be represented by a PTF of degree d and weight 2^O(n/d^2). This improves the result by Klivans and Servedio by a log^2 d factor in the exponent of the weight. Our bound is tight for all d = O( ( n/log n)^1/3) due to the matching lower bound by Beigel. For decision lists over a Hamming ball {0,1}^n_≤ k we show that the upper bound on the weight above can be drastically improved to n^O(√(k)) for d = Θ(√(k)). We also show that similar improvement is not possible for smaller degree by proving the lower bound W = 2^Ω(n/d^2) for all d = O(√(k)).
READ FULL TEXT