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

Name: Combined weight and density bounds on the polynomial threshold function representation of Boolean functions
Author: Öztop, Erhan, Asada, M.

İsim	Combined weight and density bounds on the polynomial threshold function representation of Boolean functions
Yazar	Öztop, Erhan, Asada, M.
Basım Tarihi:	2022-08
Basım Yeri	- Elsevier
Konu	Bent function, Boolean function, Polynomial sign representation, Polynomial threshold function, Sparse function
Tür	Süreli Yayın
Dil	İngilizce
Dijital	Evet
Yazma	Hayır
Kütüphane:	Özyeğin Üniversitesi
Demirbaş Numarası	0012-365X
Kayıt Numarası	5d156e90-f981-41b0-98be-1d2071eab8c7
Lokasyon	Computer Science
Tarih	2022-08
Notlar	Osaka University
Örnek Metin	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

Kaynağa git Özyeğin Üniversitesi

Aramaya Dön

Özyeğin Üniversitesi

Kaynağa git

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

Yazar Öztop, Erhan, Asada, M.

Basım Tarihi 2022-08

Basım Yeri - Elsevier

Konu Bent function, Boolean function, Polynomial sign representation, Polynomial threshold function, Sparse function

Tür Süreli Yayın

Dil İngilizce

Dijital Evet

Yazma Hayır

Kütüphane Özyeğin Üniversitesi

Demirbaş Numarası 0012-365X

Kayıt Numarası 5d156e90-f981-41b0-98be-1d2071eab8c7

Lokasyon Computer Science

Tarih 2022-08

Notlar Osaka University

Örnek Metin 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