Author
Öztop, Erhan, Asada, M.
Publication Date
2022-08
Publication Place
-
Elsevier
Subject
Bent function, Boolean function, Polynomial sign representation, Polynomial threshold function, Sparse function
Type
Periodical
Language
English
Digital
Yes
Manuscript
No
Library
Özyeğin University
Library Asset ID
0012-365X
Record ID
5d156e90-f981-41b0-98be-1d2071eab8c7
Library Location
Computer Science
Date
2022-08
Notes
Osaka University
Sample Text
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.
DOI
10.1016/j.disc.2022.112912
Cilt
345
