On the weight and density bounds of polynomial threshold functions
This work addresses theoretical bounds in computational complexity and Boolean function analysis, offering incremental improvements to known results for researchers in these fields.
The paper tackles the problem of representing Boolean functions as polynomial threshold functions (PTFs) by establishing new bounds on the density (number of monomials) and weight (sum of coefficient magnitudes), showing that all n-variable Boolean functions can be represented with at most 0.75 × 2^n non-zero integer coefficients and providing an upper bound on coefficient absolute values.
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}$.