On the weight and density bounds of polynomial threshold functions
  In this report, we show that all n-variable Boolean function can be
represented as polynomial threshold functions (PTF) with at most $0.75 \times
2^n$ non-zero integer coefficients and give an upper bound on the absolute
value of these coefficients. To our knowledge this provides the best known
bound on both the PTF density (number of monomials) and weight (sum of the
coefficient magnitudes) of general Boolean functions. The special case of Bent
functions is also analyzed and shown that any n-variable Bent function can be
represented with integer coefficients less than $2^n$ while also obeying the
aforementioned density bound. Finally, sparse Boolean functions, which are
almost constant except for $m << 2^n$ number of variable assignments, are shown
to have small weight PTFs with density at most $m+2^{n-1}$.
