EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-ND 4.0

Optimizing Multilinear Polynomial Representations of Boolean Functions for Neural Network Synthesis

Joshua Russell, Ignacio Gavier, Edward Rietman, Hava Siegelmann

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

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →