Optimizing Multilinear Polynomial Representations of Boolean Functions for Neural Network Synthesis

We consider the problem of obtaining a neural network (NN) representation of a Boolean network (BN), where each BN vertex is a k -input Boolean function (BF) ( k ≤ K ). A NN representation can be constructed by mapping each BF to its multilinear polynomial (MP) representation and then to a two-layer sub-NN; composing sub-NNs completes the representation. In this paper, 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 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 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.