Publication:
Combined weight and density bounds on the polynomial threshold function representation of Boolean functions

Placeholder

Institution Authors

Research Projects

Organizational Unit

Journal Title

Journal ISSN

Volume Title

Type

Article

Access

info:eu-repo/semantics/restrictedAccess

Publication Status

Published

Journal Issue

Abstract

In an earlier report it was shown that an arbitrary n-variable Boolean function f can be represented as a polynomial threshold function (PTF) with 0.75×2n or less number of monomials. In this report, we derive an upper bound on the absolute value of the (integer) weights of a PTF that represents f and still obeys the aforementioned density bound. To our knowledge this provides the best combined bound on the PTF density (number of monomials) and PTF weight (sum of the coefficient magnitudes) of general Boolean functions. For the special case of bent functions, it is found that any n-variable bent function can be represented with integer coefficients less than or equal to 2n with density no more than 0.75×2n, and for the case of m-sparse Boolean functions that are almost constant except for small (m≪2n) number of variable assignments, it is shown that they can be represented with small weight PTFs with density at most m+2n−1. In addition, tight PTF weight bounds with conformance to the density bound of 0.75×2n are numerically obtained for the general Boolean functions up to 6 variables.

Date

2022-08

Publisher

Elsevier

Description

Keywords

Citation

Collections


Page Views

0

File Download

0