Overview

An n-variable Boolean function (BF) is given by its truth table on all possible input combinations of inputs. So with a canonical ordering a BF can be seen as a 2^n binary vector.

When the logic constants True and False are identified by -1 and +1, an n-variable BF can be uniquely represented by a polynomial that interpolates BF at all of its inputs. This polynomial in general may have 2^n terms (monomials).

The sign-representation framework relaxes the exact interpolation, and asks if we require the polynomial to produce the correct sign at each input combination, can we gain something? Currently, we are focusing on the number of terms that is needed. We have shown that it is always possible to represent any n-variable BF with 0.75*2^n terms (Oztop 2006, Oztop 2009). This bound is the best known so far. Even so, our more recent work showed that this bound is not tight enough. We showed that 5-variable BF functions can be always represented with 11 monomials (Sezener, Oztop 2015) which is much less than implied by the theoretical result of 24.

The study on sign-representation seems to be not so popular as it were 30 years ago; but we think important links to cryptography and even neuroscience can be established.

Key publications

Sezener E, Oztop E (2015) Minimal sign representation of Boolean functions: algorithms and exact results for low dimensions. Neural Computation 27(8):1796-823

Oztop E (2009) Sign representation of Boolean functions using a small number of monomials. Neural Networks 22: 938-948

Oztop E (2006) An upper bound on the minimum number of monomials required to separate dichotomies of {-1,1}^n . Neural Computation 18: 3119-3138