Optimizing Multilinear Polynomial Representations of Boolean Functions for Neural Network Synthesis
ACM Transactions on Design Automation of Electronic Systems · 31.03.2027 · 32 (2) · 1-66
DOI: 10.1145/3830474 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Design Automation of Electronic Systems, online erschienen am 13.11.2026. Verfasst von Joshua Russell und 3 weiteren Autor:innen. Die Arbeit nennt 49 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0).
Abstract (Originalsprache)
We consider the problem of obtaining a neural network (NN) representation of a Boolean network (BN), where each Boolean network (BN) vertex is a k -input Boolean function (BF) ( k≤ K ). A neural network (NN) representation can be constructed by mapping each Boolean function (BF) to its multilinear polynomial (MP) representation and then to a two-layer sub-NN; composing sub-NNs completes the representation. In this article, we show that structural properties (number of neurons/connections, neuron in-degree) of such a NN representation can be efficiently optimized while maintaining functional equivalence with the original BN ( lossless optimization). Our approach establishes a correspondence between multilinear polynomials (MPs) and their two-layer-NN representation, enabling sub-NN optimization by minimizing MPs under structural criteria. To accelerate optimization, we utilize criterion invariance under Negation-Permutation-Negation (NPN) transformations. This allows us to classify BFs into equivalence classes, optimize canonical representatives, and then derive optimal representations for remaining class members via Negation-Permutation-Negation (NPN) transformations. Since optimizing sub-NNs may affect the composed NN depth, we propose an algorithm for lossless optimization under depth constraints. Experimentally, across four control-oriented and cryptographic digital circuits, we achieve reductions of up to 59% in neurons and 69% in connections relative to non-optimized NNs. Under minimum-depth constraints, reductions of up to 23% in neurons and 50% in connections are obtained. We demonstrate minimization of mean and maximum in-degree, and that intermediate-depth solutions recover most of the size reduction. Our NPN-based acceleration reduces MP optimization time by up to 10.2× compared to a baseline caching solutions per BF. Overall, the proposed methods facilitate high-throughput BN simulation and neurosymbolic matrix-vector-multiplication architectures.
Zitieren
APA
Russell, J., Gavier, I., Rietman, E., & Siegelmann, H. (2027). Optimizing Multilinear Polynomial Representations of Boolean Functions for Neural Network Synthesis. ACM Transactions on Design Automation of Electronic Systems, 32(2), 1-66. https://doi.org/10.1145/3830474
Vancouver
Russell J, Gavier I, Rietman E, Siegelmann H. Optimizing Multilinear Polynomial Representations of Boolean Functions for Neural Network Synthesis. ACM Transactions on Design Automation of Electronic Systems. 2027;32(2):1-66. doi:10.1145/3830474
BibTeX
@article{Russell2027,
author = {Russell, Joshua and Gavier, Ignacio and Rietman, Edward and Siegelmann, Hava},
title = {Optimizing Multilinear Polynomial Representations of Boolean Functions for Neural Network Synthesis},
journal = {ACM Transactions on Design Automation of Electronic Systems},
year = {2027},
volume = {32},
number = {2},
pages = {1--66},
doi = {10.1145/3830474}
}
EUVIMED