Heuristic algorithms for obtaining Polynomial Threshold Functions with low densities

Can Eren Sezener, Erhan Öztop

Abstract

Representing Boolean functions (BFs) as sparse Polynomial Threshold Functions (PTFs) is a critical task in neural network theory and hardware optimization. However, finding the parsimonious representation with the minimum number of monomials is computationally expensive. This paper evaluates two new heuristic algorithms—L-Heuristic and B-Heuristic—designed to find low-density PTFs efficiently. Our findings show that these heuristics significantly outperform traditional Genetic Algorithms (GAs) in both speed and sparsity, with the B-Heuristic offering a particularly effective trade-off for high-dimensional applications.

Introduction

A Boolean function $f: \{0,1\}^n \to \{-1, 1\}$ can be represented by a Polynomial Threshold Function (PTF) such that $f(x) = \text{sgn}(P(x))$, where $P(x)$ is a polynomial. The "density" of a PTF is defined by the number of non-zero coefficients (monomials) in $P(x)$. Minimizing this density is highly desirable for simplifying hardware implementations and reducing computational overhead. Since exhaustive search for the minimal PTF is intractable for larger $n$, heuristic methods are required to find sparse representations within reasonable timeframes.

Methodology

We compared four distinct algorithmic approaches for generating sparse PTFs:

  1. 3-Quarters Algorithm: A deterministic method providing a theoretical upper bound of $0.75 \cdot 2^n$ monomials.
  2. L-Heuristic (Linear): A greedy approach that sorts monomials by their spectral coefficients and attempts to eliminate them sequentially.
  3. B-Heuristic (Binary): An optimized version of the L-Heuristic that uses a binary search strategy to eliminate groups of monomials simultaneously, reducing the number of solver calls from $O(2^n)$ to $O(n)$.
  4. Genetic Algorithm (GA): An evolutionary search strategy utilizing crossover and mutation to navigate the space of possible monomial combinations.

The heuristics leverage spectral coefficients as a guide, prioritizing the elimination of terms that contribute least to the function's output.

Experimental Results

The algorithms were benchmarked using 4-variable Boolean functions. The performance metrics focused on the average number of monomials (sparsity) and the average computation time.

Comparison of average sparsity and computation time across different algorithms.

As shown in the results, the L-Heuristic achieved the best overall sparsity, averaging approximately 4.97 monomials. However, the B-Heuristic proved to be the most efficient in terms of the speed-to-sparsity ratio, running roughly three times faster than the L-Heuristic while maintaining a low average monomial count of 5.81.

Distribution of the number of functions versus the number of monomials for each algorithm.

The distribution analysis reveals that while the 3-Quarters algorithm and GA often result in higher density, the L-Heuristic and B-Heuristic consistently shift the distribution toward fewer monomials. Notably, the Genetic Algorithm performed poorly, likely due to a rugged fitness landscape that hinders standard evolutionary operators.

Discussion and Conclusion

The study demonstrates that spectral-guided heuristics are far more effective than general-purpose evolutionary algorithms for PTF minimization. The L-Heuristic is preferred when absolute sparsity is required, whereas the B-Heuristic is ideal for scenarios where computational resources are limited or the number of variables is large. Future research will explore the scalability of the B-Heuristic for $n > 10$ and its direct application in optimizing threshold logic gates for specialized hardware.

Summary updated

BibTeX
@inproceedings{sezener2015heuristic,
  author = {Can Eren Sezener and Erhan Öztop},
  title = {{Heuristic algorithms for obtaining Polynomial Threshold Functions with low densities}},
  booktitle = {Cologne},
  year = {2015},
}
Figure