A Better Upper Bound on Weights of Exact Threshold Functions

摘要

A Boolean function is called an exact threshold function if it decides whether the input vector x ∈ {0,1}~n is on a hyperplane ω~Tχ = t (ω ∈ Z~n,t ∈Z). In this paper we study the upper bound of elements in w required to represent any exact threshold function. Let k be the dimension of the linear subspace spanned by Boolean points on ω~T χ = t. We first give an upper bound O(n~k) for constant k, which matches the lower bound in [2]. Then we prove an upper bound O(k~O~(k~2)n~k) for general cases, improving the result min{n~(2~k) ,n~(n/2+1)} in [2].