Sign-representation of Boolean functions using a small number of monomials

This paper presents a deterministic algorithm that can construct a higher-order neuron representation for an arbitrary nn-variable Boolean function with a fan-in less than 0.75×2n0.75×2n, and provides related theoretical results. When the logic constants True and False are identified by +1 and −1, an nn-variable Boolean function is identified by a unique dichotomy of the nn-dimensional hypercube. With this equivalence, all nn-variable Boolean functions can be uniquely represented by linear combinations of monomials, the products of input variables. A polynomial function whose sign matches the truth table of a given Boolean function is said to sign-represent that Boolean function. The artificial neural units that implement this sign-representation scheme are often called higher-order neurons or polynomial threshold units. This paper investigates the freedom provided by the sign-representation framework in terms of the fan-in of these artificial neural units. In particular, we look for sign-representations with a small number of monomials. Although there are methods developed for finding a reduced set of monomials to represent Boolean functions, there are no deterministic algorithms for computing non-trivial solutions with guarantees on the number of monomials in the found sign-representations. This work fills this gap by providing deterministic algorithms which are guaranteed to find solutions with fewer than 0.75×2n0.75×2n monomials for nn-variable Boolean functions. Although the algorithms presented here are computationally costly, it is expected that several research directions can be spawned from the current study, such as reducing the 0.75×2n0.75×2n bound and devising efficient algorithms for finding sign-representations with a small number of monomials.