Heuristic algorithms for obtaining
Polynomial Threshold Functions with low
densities
Can Eren Sezener1 and Erhan Oztop1

arXiv:1504.01167v1 [cs.CC] 5 Apr 2015

1

Ozyegin University, Istanbul, Turkey

In this paper we present several heuristic algorithms, including a Genetic Algorithm (GA), for obtaining polynomial threshold function (PTF) representations
of Boolean functions (BFs) with small number of monomials. We compare these
among each other and against the algorithm of Oztop [1] via computational experiments. The results indicate that our heuristic algorithms find more parsimonious
representations compared to the those of non-heuristic and GA-based algorithms.

1 Introduction
An n-variable Boolean function f : {−1, 1}n → {−1, 1} is said to be sign-represented by p(x)
if sign(p(x)) = f (x) for all x ∈ {−1, 1}n . In this case, we also say that BF f is realized
by a PTF. For a given BF f , there are infinitely many sign-representing polynomials which
can have different number of monomials. A PTF for a given BF can be obtained by various
algorithms; however, no known algorithms can guarantee a PTF with the minimum number
of monomials without conducting an exhaustive search. Oztop gave the first algorithm that
guarantees a PTF with 0.75 × 2n monomials or less [1]. Later, Amano showed that almost all
BFs can be sign-represented with less than 0.617 × 2n monomials [2]. Recently, Sezener and
Oztop proposed a heuristic algorithm that obtains very efficient sign-representations by taking
advantage of spectral coefficients [3]. In this study, we not only investigate the performance of
this algorithm but also propose a faster version of it, albeit with some increase in the number of
monomials found. Furthermore, we also investigate how genetic algorithms would perform in
searching for a parsimonious sign-representation. Finally, these three methods, are compared
with each other and with the non-heuristic algorithm of [1].

2 Algorithms for sign-representation
In this section, we give basic definitions and the algorithms for obtaining PTFs.

2.1 Representation of Boolean Functions:
For every BF f , it can be shown that there is a unique multilinear polynomial pf that exactly
2n
P
Q
represents f : pf (x1 , x2 , · · · , xn ) =
si
xk where Si runs over the powerset of {1,2,..,n}.
i=1

k∈Si

This representation is called the spectral representation of f , and the coefficients are called as
the spectral coefficients. With a fixed ordering over the monomials (i.e. the products appearing
in the expression of pf ), the spectrum (i.e., the collection of the spectral coefficients) can be
n
considered as a vector s ∈ R2 , and used to represent f . The spectrum can be obtained by
Lagrange Interpolation [4]. Note that the with this, we obtain two vector representations of a
given BF: one is the spectrum s and the other is the natural binary vector f that is obtained
by listing the function values for all variable assignments. Now, with the adoption of a suitable
ordering, this two representations can be related nicely: f = Dn s where Dn is the 2n × 2n
Sylvester-type Hadamard Matrix with columns representing the monomials evaluated at all
possible input assignments taken in the adopted assignment order.
Polynomial representation of Boolean functions naturally extends to sign-representation:
instead of requiring exact interpolation we ask only the sign of the polynomial to agree with
the function at each input combination. We say a polynomial p sign-represents a Boolean
function f , if and only if f (x1 , x2 , · · · , xn ) = sgn(p(x1 , x2 , · · · , xn )) for all xi ∈ {−1, 1}. In
vector notation this is equivalent to saying f = sgn(Dn a) where a is the coefficients of p ordered
as in the spectrum definition. It can be shown that for a given Boolean function f , all the
solutions (the coefficients of sign-representing polynomials) are of the form a = 2−n Dn Yf k
with arbitrary k > 0. From this one can obtain the following useful result ([3] and [1]):
Lemma 1. Let Qf = diag(f )Dn , and A, B be matrices made up from an arbitrary partition
of the columns of Qf . Then ∃k > 0 such that BT k = 0 if and only if a = [A0]T r with some
r > 0 is a solution for Qf a > 0. That is, if we can find a k > 0 such that BT k = 0, it means
that we can eliminate the monomials which correspond to the rows in B.
The minimum number of monomials that would be sufficient to represent a given BF f is
called the threshold density of f . A brute force algorithm to find this value is easy to give:
Algorithm 1: The brute-force algorithm for a n-variable BF

5

Enumerate all the column submatrices of Q as Q1 , Q2 , ...Q22n ;
Set S as {};
n
for i = 1..22 do
if YQi a > 0 is satisfiable then
store (# of columns of Qi ) in S;

6

return min(S)

1
2
3
4

Although, the satisfiability check in Line 4 can be done efficiently (e.g. by using Linear Programming methods), due to the super-exponential growth (with respect to n) of the number of
column submatrices, the brute-force solution is not feasible for investigating threshold densities
of BFs with 4 or more variables. It is worth noting that as each column of Qi corresponds
to a monomial, Lemma 1 tells us that the satisfiability of YQi a > 0 can also be shown by
finding a positive vector that is orthogonal to the monomials not appearing in Qi . In the
following section this property is used and instead of talking about satisfiability we talk about
elimination of monomials by inner product with a positive vector.

2.2 Heuristic algorithms for sign-representation
Recently, Sezener and Oztop proposed a fast heuristic algorithm to obtain sign-representations
with a very few number of monomials [3]. The heuristic (see Algorithm 2) is based on the
intuition that some monomials are ‘easier’ to eliminate and the algorithm first attempts to
eliminate the ‘easy’ monomials and then moves on to the harder ones. It does a single pass
over the 2n monomials and therefore is very efficient compared to the brute-force method which
n
searches the power set of monomials (of cardinality 22 ) for solutions.
Algorithm 2: L-Heuristic
1
2
3
4
5
6
7

m=1, E={};
Sort the monomials using their spectral coefficients as the sorting key;
while m < 2n do
if monomials from 1 to m that are not included in E can be eliminated then
add m to E;
m = m + 1;
return m

We propose a modification to this algorithm which increases its speed. The idea is to change
m (which controls how many monomials are included in the elimination list E) somewhat
similar to binary search, rather than incrementing it by one at each trial (2n many increments
in total). With this change, the subroutine that checks for eliminability (e.g. a LP routine)
would be called log2 2n = n times in the worst case as opposed to 2n times.
Algorithm 3: B-Heuristic

7

lo = 1, hi = 2n − 1;
while lo ≤ hi do
m = f loor((hi + lo)/2);
if first m monomials can be eliminated then
lo = m + 1;
else
hi = m − 1;

8

return m

1
2
3
4
5
6

2.3 Genetic Algorithms for sign-representation
We can cast the problem of finding the threshold density of a BF f as an optimization problem.
Let b be an indicator binary vector of length 2n to uniquely identify a submatrix Qb of Q for
elimination by having a 1 at position i to pick the ith column of Q (b in fact represents the
elimination set E in Algorithms 1 and 2). Now, our goal is to find the b with the maximum
number of 1’s that indicates a Qb that can be eliminated, thus ensures a solution due to
Lemma 1. Genetic Algorithms (GAs) at the onset, seem to be suitable for obtaining signrepresentations as there are multiple global minima, and the relation among the monomials (i.e.
relation among the columns of Q), suggests that the cross-over operation of GA may do a good
job at reaching better solutions from the existing solutions. In the current implementation, we
used a simple binary GA [5]. TheP
GA searches for genotypes (i.e. b vectors) with higher fitness
n
values, which is simply defined as 2i=1 bi if isEliminable(Qb ) else 0, where isEliminable checks

whether the columns of its argument can be annihilated by a positive vector. The results of GA
for sign representation (we used 16 chromosomes with 0.01 mutation rate for 100 generations)
is given in the next section, together with other algorithms.

3 Results
We found PTFs for 4-variable BFs using the aforementioned algorithms. Table 1 shows the
average number of monomials and the average computation durations (for a standard PC). It
Algorithm
3-Quarters
L-Heuristic
B-Heuristic
GA

Avg. # monomials
8.2720
4.9678
5.8115
7.9941

Avg. computation time (s)
0.0007
0.0654
0.0199
4.2678

Table 1: Result comparison

is also useful to see the distribution of densities. Figure 1 shows the number of monomials
in PTFs obtained by the four algorithms for the first half of 4-variable BFs. For example, it
can be seen that the B-Heuristic solved approximately 103 of the problems with 4 monomials.
As an example, Table 2 gives the solutions found by the algorithms compared for one of the
hardest 4-variable BFs to sign-represent [3].

Figure 1: Distribution of the number of monomials to represent 4-variable BFs (log-lin scale)

Algorithm
3-Quarters
L-Heuristic
B-Heuristic
GA

Polynomial representation
−2 · x0 − 2 · x1 · x0 − 2 · x2 · x0 + 2 · x2 · x1 · x0 − 3 · x3 + 3 · x3 · x0 − 3 · x3 · x1
+3 · x3 · x1 · x0 − 3 · x3 · x2 + 3 · x3 · x2 · x0 + 3 · x3 · x2 · x1 − 3 · x3 · x2 · x1 · x0
−x1 · x0 − x2 · x0 + x2 · x1 · x0 − x3 · x1 + x3 · x1 · x0 − x3 · x2
+x3 · x2 · x0 + x3 · x2 · x1 − x3 · x2 · x1 · x0
−2 · x1 · x0 − x2 − x2 · x0 + 2 · x2 · x1 − x3 + 2 · x3 · x0 − x3 · x1 − 2 · x3 · x2
+x3 · x2 · x0 + x3 · x2 · x1
−2 · x0 − 3 · x1 − 2 · x2 − x2 · x0 − 2 · x3 − 2 · x3 · x1 + x3 · x1 · x0 − 3 · x3 · x2
+2 · x3 · x2 · x0 − 2 · x3 · x2 · x1 · x0

Table 2: PTF representations of f = [−1, −1, −1, −1, −1, −1, 1, 1, −1, 1, −1, 1, −1, 1, 1, −1]

4 Conclusion
From the computations carried out it can be seen that the L-Heuristic finds representations
with the least number of monomials among the studied four algorithms. The B-Heuristic gets
very close to the L-Heuristic, which is an impressive performance considering the reduced computation time. Therefore, the B-Heuristic seems to be a good choice studying high dimensional
BFs. It is surprising that GAs that perform very well in a wide range of search problems fail
to produce good results for the minimal sign-representation problem. The 3-Quarters algorithm performs comparable to the GA in terms of number of monomials found; however, the
3-Quarters uses a fraction of the time the GA uses as it is not based on a search heuristic. It
is an interesting open problem in evolutionary computation to come up with domain specific
crossover and mutation parameters to improve the performance of GAs for sign-representation.

References
[1] Erhan Oztop. Sign-representation of boolean functions using a small number of monomials.
Neural Networks, 22(7):938–948, September 2009.
[2] Kazuyuki Amano. New upper bounds on the average ptf density of boolean functions. In
Otfried Cheong, Kyung-Yong Chwa, and Kunsoo Park, editors, Algorithms and Computation, volume 6506 of Lecture Notes in Computer Science, pages 304–315. Springer Berlin
Heidelberg, 2010.
[3] Can Eren Sezener and Erhan Oztop. Minimal sign representation of boolean functions:
algorithms and exact results for low dimensions. Neural Computation, In Press.
[4] Erhan Oztop. An upper bound on the minimum number of monomials required to separate
dichotomies of {-1, 1}n . Neural Computation, 18(12):3119–3138, 2006.
[5] Randy L. Haupt and Sue Ellen Haupt. The Binary Genetic Algorithm, pages 27–50. John
Wiley & Sons, Inc., 2004.

