Heuristic algorithms for obtaining Polynomial Threshold Functions with low densities

2015/04/05 by Can Eren Sezener, Sezener, Can Eren, Erhan Öztop +1
Computer Science · Engineering · #Advanced Control Systems Optimization #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Neural and Evolutionary Computing (cs.NE) #Polynomial and algebraic computation #Rough Sets and Fuzzy Logic

paper · pdf · doi:10.48550/arxiv.1504.01167

openalex publication_date 2015/04/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 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.

Related

• On the weight and density bounds of polynomial threshold functions
• Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness
• Polynomial Threshold Functions of Bounded Tree-Width: Some Explainability and Complexity Aspects
• Polynomial Representations of Threshold Functions and Algorithmic Applications
• A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates