Optimizing Neural Network Representations of Boolean Networks
Authors: Joshua Russell
Ignacio Gavier
Devdhar Patel
Edward Rietman
Hava T Siegelmann
Venue: ICLR 2025 Poster (2025)
Keywords: Neural Networks
Boolean Networks
Lossless Optimization
Integer Linear Programming
NPN Classification
Primary area: optimization

Abstract: Neural networks are known to be universal computers for Boolean functions. Recent advancements in hardware have significantly reduced matrix multiplication times, making neural network simulation both fast and efficient. Consequently, functions defined by complex Boolean networks are increasingly viable candidates for simulation through their neural network representation. Prior research has introduced a general method for deriving neural network representations of Boolean networks. However, the resulting neural networks are often suboptimal in terms of the number of neurons and connections, leading to slower simulation performance. Optimizing them while preserving functional equivalence --lossless optimization-- is an NP-hard problem, and current methods only provide lossy solutions. In this paper, we present a deterministic algorithm to optimize such neural networks in terms of neurons and connections while preserving functional equivalence. Moreover, to accelerate the compression of the neural network, we introduce an objective-aware algorithm that exploits representations that are shared among subproblems of the overall optimization. We demonstrate experimentally that we are able to reduce connections and neurons by up to 70% and 60%, respectively, in comparison to state-of-the-art. We also find that our objective-aware algorithm results in consistent speedups in optimization time, achieving up to 34.3x and 5.9x speedup relative to naive and caching solutions, respectively. Our methods are of practical relevance to applications such as high-throughput circuit simulation and placing neurosymbolic systems on the same hardware architecture.

Published as a conference paper at ICLR 2025
OPTIMIZING NEURAL NETWORK REPRESENTATIONS OF BOOLEAN NETWORKS
Joshua Russell Ignacio Gavier Devdhar Patel
Edward Rietman
Hava T. Siegelmann
University of Massachusetts Amherst
(jgrussel1, igavier, devviarrdevdaapptteelll erietman, hava @umass edu
ABSTRACT
Neural networks known to be universal computers for Boolean functions. Recent advancements hardware have significantly reduced matrix multiplication times, making neural network simulation both fast and efficient. Consequently, functions defined by complex Boolean networks are increasingly viable candidates for simulation through their neural network representation. Prior research has introduced a general method for deriving neural network representations of Boolean networks. However, the resulting neural networks are often suboptimal in terms of the number of neurons and connections, leading to slower simulation performance. Optimizing them while preserving functional equivalence -lossless optimization- is an NP-hard problem, and current methods only provide lossy solutions. In this paper, we present deterministic algorithm to optimize such neural networks in terms of neurons and connections while preserving functional equivalence. Moreover, to accelerate the compression of the neural network, we introduce objective-aware algorithm that exploits representations that are shared among subproblems of the overall optimization. We demonstrate experimentally that we are able to reduce connections and neurons by up to 70% and 60%. respectively, in comparison to state-of-the-an results in consistent speedups in optimization time, achieving up 34.3x and 5.9x speedup relative to naive and caching solutions, respectively. Our methods are of practical relevance applications such high-throughput circuit simulation and placing neurosymbolic systems on the same hardware architecture.
We also find that our objective-aware algorithm
INTRODUCTION
Universal approximation theorems (Hornik al., 1989) and Sontag, 1992) provide the theoretical foundation for implementing computable functions with neural networks (NNs). At present, the predominant methods for implementing functions with NNs bauning-based techniques, which rely on optimization algorithms, data, and compute to clicit function of interest (LeCun al., 2015). While these techniques provide solution for obtaining functions that are difficult to programmatically specify, they come at the cost of unsustainable energy usage (Strubell al., 2019), ever-longer training times, and safety concerns due the current lack of understanding surrounding functions derived from learning based techniques (Qi et al., 2023).
(Siegelmann &
Another much less prevalent implementation method for NNs synthesize a network from known functional specification. The specification may be in the form of an explicit construction, detailing the network structure, neurons, and connections (Hewitt al., 2020; Karuvally et al., 2024), or may be provided in a programming language, requiring method to convert the specification into resulting NN (Siegelmann, 1994; Gruau et al., 1995; Neto et al., 2003). These implementation methods generally require significantly less time and energy in comparison provide guarantees on NN functionality which are critical for safety and security.
baaming-basedd techniques and
One such programmatic implementation method is that of ba-based technology mapping (Patel et al., 2022; Gavier et al., 2023), the problem finding a NN that is functionally equivalent to a Boolean network (BN) (i.e., V E 10, 1)", NN: BN (2:)) This method holds significant potential for

---

Published as a conference paper at ICLR 2025
Objective landecape
AN;
N
NNj
Lossless region 2
Shortout learned optimizing
region,
Obyective- subproblem acoe leratertor
NNj
NNVY
NON
Neural Network representation Boolean Network, a composition lao-layer subnewworks
Subprablem
Figure 1: Summary of our optimization problem. A neural network (NN) representing a Boolean network (BN) can be constructed composition of two-layer sub-NNs N N; (left). Optimizing the size of the NN is performed by optimizing each sub-NN NN; (top right). To maintain functional equivalence of the original NN, necessary that each subproblem solution lies within its lossless region. Subproblems can be accelerated for sub-NNs NN, that have shared representation with (i.e., are the same class as) already optimized sub-NNs N N; (bottom and top right).
applications the integrated circuits industry and for neurosymbolic hardware architectures; however, the current state-of-the-art (SOTA) solution of Gavier al. (2023) faces significant drawbacks: (1) the resulting NNs are often suboptimal in terms of neurons and connections, and (2) slow execution time makes the technique less appealing for industrial settings.
In light of these shortcomings in the SOTA, our first goal is to develop a technique for optimizing NN size while maintaining functional equivalence. compression techniques, such pruning and quantization, have been extensively researched under the learning based paradigm (Liang et al., 2021; al., 2023). However, in general. pruning techniques are lossy and do not guarantee preservation of functional equivalence (Vadera & Ameen, 2022). Moreover, since optimal bit widths for parameters and activations can calculated analytically following NN-based technology mapping, further quantization cannot be applied as it would break functional equivalence. While lossless compression techniques that maintain functional equivalence have been presented for ReLU (Serra al., 2020) and mongle-hidden-lee -ayer hyperbolic tangent (Sussmann, 1992; Farrugia-Roberts, 2024) NNs, they are not applicable to the Heaviside threshold NNs we investigate in this work.
Figure (left) depicts the representation of sition of two-layer sub-NNs. Optimizing the size of the NN can be thought of as the aggregation of subproblems, one for each sub-NN, shown in Figure (top right). Our second goal is to develop an algorithm that exploits shared representations among these subproblems to accelerate the NN optimization process, which key for dealing with the large-scale BNs faced in industrial applications.
proposed by Gavier et al. (2023); compo-
Summary: The SOTA solution for NN-based technology mapping does not effectively optimize the resulting NN representation. Since existing NN compression techniques are either lossy or inapplicable, the challenge of efficiently optimizing representations of remains open.
Contributions.
We introduce a practical methodology to overcome these challenges:
We propose lossless technique for optimizing two-layer NN representation of a Boolean function (see 3.1). We present two objectives that correlate with minimizing neurons or connections.
propose an objective-aware optimization algorithm based on Vegation-Permutaaio Negation (NPN) classification, exploiting shared representations among the two-layer sub-NNs (see $ 3.2). We show that our algorithm consistently accelerates optimization time, achieving up to 34.3x and 5.9x speedup relative naive and caching solutions, respectively (see Figure 6).
We propose architecture-awwe
lossless optimization algorithm that selects which two- layer sub-NNs to minimize (see $ 3.3). We demonstrate experimentally that connections and neurons can be reduced by up 70% and 60% in comparison SOTA (see Figure 5).
2

---

Published as a conference paper at ICLR 2025
2 BACKGROUND
In this section we introduce the necessary definitions and background for NN-based technology map- ping and optimization algorithms. The essential notions are covered here, while comprehensive treatment provided in the appendix.
2.1 DEFINITIONS
Notation. We denote the set of binary numbers 1B (0, 1). the of natural numbers (including
0) as No = {0, 1, .. and the set of integers as ž = {..., 1...,,22, -2 - 2,
Definition 2.1 (Boolean function). A k-input, (single-output) Boolean function (RF) is function
f: B + I8, x + f(x), where a = (Fi,..., 2x) is bit vector representing the k input variables
32 E I, -
Definition 2.2 (Truth table representation of a BF). The truth table representation is an expansion of BF f: RB - basis of indicator functions (()) Eass* f(a) (az), where la BB -
defined as (x)
and 0 otherwise. The truth table vector f B²" of f is the vector of coordinates (a) in such a basis. F.g., the truth table vector of s(a, b) = a V b is f = [0, 1, 1, Definition 2.3 (Multilinear polynomial representation of BF). The multilinear polynomial (MP) representation is an expansion of BF f 1B - B, extended to 2 + Z. in the basis (o'Donell,, 2014) of logical AND functions p(æ) = Esc(I....)) (()) where Xs 2 - 2 is defined
if
as Xs (x Ilis Zj and S S (1,...,,k) f(S) in such basis. E.g., if [a, b) = a b then p(a, b) Definition 2.4 (Boolean network). A Boolean network (BN) GF (V, E) is directed-acyclic graph (DAG), with vertex labeling function va + F, that represents an n-input, m--utput BF are primary inputs (PI). and vertices with outdegree zero are primary outputs (PO). The labeling function & assigns single-output BF to each non-PI vertex in the graph. A directed edge (u, v) E exists if the output of u's BF is an input to v's The depth of vertex v E V, denoted depth(u) E No, is the length of the longest path from any PI to v. The depth of BN, denoted depth(G>)) is the maximum vertex depth in the BN.
k). The MP vector p E 2 of is the vector of coordinates ab and p 1,,
B: " Vertices with indegree
Definition 2.5 (Neural network). Let L E No and (Do, Di,..., N6+1 A neural network (NN) N/ B Pd is function with specification
N(x) (WL L (o(w o...o (....(('a x + bb) ...) + +bb-1)) bb)).
(I)
where is the Heaviside step function' and 1I {1.....,I) L}, W ZD:xDi and b' E ZP, The depth of a NN is denoted dep L. Definition 2.6 (Functional equivalence). Two functions f.g: X + y functionally equivalent Vr E X, fx) = g(x).
2.2 OBTAINING A NEURAL NETWORK REPRESENTATION OF BOOLEAN NETWORK
Here we review the SOTA for NN-based technology mapping (Gavier et al., 2023). The method takes BN Ginst as input and, through a sequence of mappings, converts it into a functionally equivalent NN.
LUT-bbase technology mapping. K-LUT-based technology mapping (Cong Ding, 1994), K Ng. is used to convert Gigst into a functionally equivalent BN Gr, with function set F, = _ consisting of k-input look-up tables (LUTs), or truth table vectors f IB2", K.
MP-based technology mapping. Following K K-LU'T-based technology mapping, each truth table vector 2 & < K, in Gr, is mapped functionally equivalent vector p Z The resulting function set is F, = z2 Each conversion from truth table vector to MP vector can be computed via hivide-and-conuus algorithm in time (2**k) (Gavier et al., 2023). We denote this conversion algorithmically as ttTMMP.
(x) if 0, and otherwise, and is extended an element-wise function.
3

---

Published as a conference paper at ICLR 2025
NN-based technology mapping from MP BNs. Following MP-based technology mapping, each MP vector p E 2²", K, in BN Gy, is mapped a functionally equivalent two-layer NN Ç 2 Z. ((x) (20 x b1) with parameters (W1, b1, W2) 2 (1x)(")) The resulting function set FN f 2(2 (2)) See Figure 2 for an example of k = 2.
Intra-depth parallelization & the Unmerged NN. Gex (V, F)) be bN following NN-based technology mapping which all vertices E have incoming edges only from vertices at depth depth(v)= 1, that is, there are no "skip connections" (this can be achieved by adding additional vertices that compute the identity function). Moreover, let Va = {v E V depth(v) = d} be the set of vertices depth d, and d {1..... depth (Grx)) )). Then the output of all vertices in V|va) can be computed in parallel as
Va = {11, 02.
((x"1)
W
21
+
W Val
Viaal
Mal
b Mi
where (WT', .
M(n)), (I,..., Val}. Note that various vertices at the same depth
could share the same input signals and in turn hidden vertices, thus reducing the input and hidden
dimensions of the above two-layer NN. We call the NN obtained via intra-depth parallelization Gax
the unmerged NN of BN GFw-
Let d E {L..... depth(GF (L....,epph(((Fp let ç c(4) (x = wh(t) ( +b(()) ad()) and ç (x( =
Inter-depth composition & the Layer-Merged NN.
Moreover, ad))_
b((tt)) = x (d+1) be the intra-depth parallelized two-layer NNs (as in Equation 2) for vertices in Va and Ve+1, respectively. Then,
(d-1) = =(((d+1) ( ((())
(3)
-Wo(t!// σ (w(d+1) (W!r0 σ (w ( xdd11) + +b(()) + +b( b((tt))) (d-1) + bl(1)
(4)
-wldtt) W (
bj bl(tz))
(5)
where W (.(d+1) That is, since the second layer depth d does not required threshold, we can merge it with the first layer at depth d 1. We call the NN obtained via intra-depth parallelization and inter-depth composition of Grx the layer-merged NN of Gyw-
Remark 2.1 (Implications for depth). Let d dGpth(GFx)) Then the depth of the unmerged Nn is 2d (non-Pl vertices in Vi,..., Vy have layer of hidden neurons added before them), and the depth of the layer-merged NN is + (the second layer of non-PI and non-PO vertices in Vi,..., Va- merged with the first layer of vertices at the next depth).
3 METHODS
In this section we set out to achieve the two goals stated in the introduc- tion: (1) optimizing the NN size and (2) doing so efficiently. We begin by considering the problem of optimizing NN size while maintaining functional equivalence. The SOTA mapping procedure reviewed in 2.2 constructs a NN representation of BN via composition of sub-NNs, each built from the MP representation of a BE. We propose optimize the size of the NN by treating the sub-NNs optimization subproblems. In 3.1, we identify sub-NN optimization as a constrained minimization problem, and propose convex technique solve it.
0
C
0
Co
C6
p
C..
ab
Figure 2: NN represen- tation of p(a. op + C, + c, + ab Weights and biases shown above connections and neurons.
Next, we turn our attention to accelerating the NN optimization process in aggregate. Since we pose NN optimization minimizing various sub-NNs, we seek to exploit similarities among the subproblems that must be solved. We develop this idea in 3.2, showing that by classifying the subproblems into classes, the solution for representative the class can used to accelerate the acquisition of the solutions for all other members of the class.
4

---

Published as a conference paper at ICLR 2025
Finally, in $ 3.3, we piece these insights together form architecture-aware optimization algorithms for the problem of NN- based technology mapping. In particular, we consider how to apply the proposed optimization techniques to the two kinds of NNs that result from the SOTA mapping procedure reviewed in $ 2.2: unmerged and layer-merged NNs. The essential notions critical for describing the main results are presented here, while comprehensive treatment is provided in the appendix.
3.1 OPTIMIZING NEURAL NETWORK REPRESENTATIONS OF BOOLEAN FUNCTIONS
We begin by establishing a relationship between MPs and the size of their two-layer NN representation. Figure 2 depicts this relationship for 1: = 2. We see that the number of hidden neurons in the Nn corresponds to the number of non-constant monomials in the MP, and the number of (layer one) connections corresponds to the sum of non-constant monomial degrees. To express this relationship in terms of MP vectors, we introduce the following definition and lemma.
Definition 3.1 (Uniform & degree criterions). Let E No and Ck deg 2² have specification (ctT)); ) = if > 0 and O otherwise, and dog
deg (k-1
k-
deg
+ 1--1
if k > 0 and [0] otherwise,
where 1 B denotes the all ones vector. E.g.. C2 cumi [0, 1, 1, 1]TH and deg = [0, 1, 1,
Lemma 3.1. Let p 2²2 be MP vector, 2²² and C 2² No be a cost function with specification C(p) = ||pllo,c. where ll.lo..e denotes the zero-norm weighted by vector c. Then, (1) C(p) = ll.eee is the number of non-constant monomials in the MP p, and (2) C(p) = ll
is the sum of non-constant monomial degrees in the MP p.
Following Lemma 3.1, we can now formally restate our observation of the relationship between MPs and the size of their two-layer NN representation: IIpllo.eq"i and ||pllo, ef- are the number of neurons and (layer one) connections in the two-layer NN representation of MP p. Optimizing the two-layer NN can now be viewed as finding polynomial with, for example, fewer monomials. However, present, removing monomials from a MP will change the BF it represents, and we would lose funcciionl equivalence. Since the BN NN mapping procedure results in a (Heaviside) threshold NN, the key insight is to consider MPs equivalent under a threshold.
Definition 3.2 (The ~o equivalence relation). Letp, 2² be MPs. We define ~ Z²" x 2 B the relation p ~a q <
Vaz E BB (x)) (a a q)(=)) Since ~o is equivalence
p q). Definition 3.3 (Minimal multilinear polynomial representation of BF)). Let f B + B be a BF with MP p E Z and C 2 No be cost function. A minimal multilinear polynomial (MMP) representation of f with respect to C' is MP p' E 7 where
relation (see Appendix C), we denote the a equivalence class of MP p as [p]. {q E Z
p' E arg min C(q).
(6)
gE(p),
E.g., b) = + is an MMP of the MP p(a, b) number of monomials, as they are equivalent under a threshold. Notice, that by removing -ab, the resulting two-layer NN has fewer neuron and 3 fewer connections (see Figure 2). However, to maintain functional equivalence, the two-layer NN requires a threshold on its output neuron.
ab (logical OR) with respect to the
Lemma 1 and Definition 3.3 suggest that finding the MMP of an arbitrary BF requires minimizing an objective with nnrmm. These problems are non-convex and NP-hard (Feng al., 2013), it not possible to solve them with conventional convex optimization methods. However, by relaxing the norm E,, the cost function becomes convex and of the form ||q|l.c ||e @ qlIi.² Although the solution to the relaxed problem may differ from the actual minimum, both aim for sparsity (Feng et al., 2013), which results compressed NNs. Next, we will show that q E [p], can be defined as linear constraint, making the optimization problem convex.
Theorem 3.1 (Linear constraints determine a equivalence class). Let E 2²" be an MP, b = 1, (S.p)) e 2² and A = 2(diag (((diag(bSSa)) (b) z²" x2* where Sy E 222 x2 is the k-th Sierpiíski
26 denotes the Hadamard product.
5

---

Published as a conference paper at ICLR 2025
matrix, 1 E B²² is the all ones vector, and is the Heaviside step function. Then, for q z²"
q Pl Aq Aqs6 b.
Following Theorem 3.1, we have all the components necessary to define an optimization problem for obtaining an MMP representation of BF and in turn its compressed two-layer NN.
Corollary 3.1 (Obtaining an MMP representation of BF). I f Z²" is the MP of a Br B + B, and C z + No has specification C(q) | @ 4llı, where c E zZ² then the set of MMP representations of f with respect to equals the solution set of the following integer linear program:
minimize qezak
C(q),
subject to
Aq S b.
Corollary 3.1 shows that indeed we can find an MMP of an arbitrary BF. While relaxing the optimization objective to an é (--mr provides with convexity, since the variables are integers the problem is still NP-hard (Karp, 1972). We conclude by connecting the new representation with the technology mapping sequence discussed in 2.2.
MMP-based technology mapping. Following Mr-based technology mapping, each vector p E Z²z k S K, BN Gy,, is mapped to functionally equivalent MMP p' [pl- by solving an integer linear program of the form presented in Corollary 3.1. The resulting function set is Fp' U We denote this conversion algorithmically as mpToMMP.
3.2 OBJECTIVE-AWAN OPTIMIZATION USING SHARED REPRESENTATIONS
In $ 2.2, we saw that NN that is functionally equivalent to a BN can be constructed by computing the MP of each (ttToMP) in the BN. In 3.1, we saw that MMP, are the solution to lossless optimization each MP, resulting in compressed two-layer (sub-)ot )NN (mpToMMB) At first glance, one may think we need to solve all these subprob- lems independently. However, by caching the solution to each subproblem. Alternatively, we can classify the subproblems solutions to their class as a whole. One option for this classification problem is use Negation-Permunn Permutation -otttattiooNeattionnn (NPN) classifica- tion of BFs (Sasao & Butler, 2022). We introduce NPN classification with the following definitions.
av a
1.0,1,1 0,,,1,1
ā 1.
a a b 1,
Tbb
can improve such algorithm
V b
V
terms of shared representations, and find
0,0, 1,
11,1,1,01
avb
ā b 1,1,0,0
1,0,0.0
Figure 3: Brs f E B in the same NPN equivalence class. Arrows depict NPN transforma- tions, and the NPN canonical form (dark red) is defined to the member with minimum truth table.
Definition 3.4 (NPN transformation). An NPN transformation T o
Ta Ta of a BF MP is the composition of an input phase assignment To (whether variable x; is to be negated), an input permutation Tи, and output polarity assignment т, (whether the output is to be negated).
Definition 3.5 (NPN equivalence). BFs f.g E B are NPN equivalent, denoted f NNN if there exists an NPN transformation 7 such that
T(f) g- The NPN equivalence class of f is denoted [f] (g E TB2
1f ENPN 9).
Remark 3.1. There are 2 NPN transformations for k-input BFs, as there are 2 possible input phase assignments, k! possible input permutations, and 2 possible output polarity assignments. Hence, an NPN equivalence class contains most 2 BFs.
Definition 3.6 (NPN canonical form). The NPN canonical form of BF f E B²* denoted x(f), is
mapping : B2² -> T that satisfies the following conditions: (1) x(f) E [fNNNN and (2) Vg E fINNN, r(g) = k(ff) (i.e., the canonical form is a unique representative of the class). We
denote k(f) Kg IB2" and the MP of Kg as Kip E 2²
Sk-1, Ok-1
S.
S if > 0. and otherwise, where O denotes the all zeros matrix.
Sk-1,

---

Published as a conference paper at ICLR 2025
2
Z 2
Pile
IB
f1
ttToMP
P1
MMMP
P1
TV
[
ttToMP
Kpp
(m(())
mpToMMP
K
K
Kip
TT)
p
| NNN
(Ki) |P/NNNN-
My INPN-
Teldh
13 OTT
TV oT (2)
To
ttToMP
mpToMMP
f2
P2
P2
[Pal
Figure 4: Accelerating the computation of multilinear polynomial (MP) and minimal MP (MMP) representations of Boolean functions (nFs) with Regation-Permutation- Neggttion (NPN) transformations. Given distinct BFS f2 E B² (as truth table vectors), the dashed arrows indicate that MPS P P2 E z² and MMPs p1 P/2 z² can be obtained via calls to TcMP (truth table MP) followed by two calls to mpToMMP (MP to MMP). If (i) the two functions share NPN canonical form (Te (1) (2)
Ti (1) O72 ( (TL² Th o (f2) = Kif B²* (ii) equality x x²) (1( holds, and (iii) the MMP criterion is invariant under input permutation and output negation, then the solid arrows indicate that by utilizing NPN transformations MP and MMP representations of f and fa can be obtained via a single call ToTMMP and MрToMMP. In fact, since the number of functions in each NPN equivalence class is at most 2 kl, if all MPs and MMPs are required to be computed for a class, this process can lead to 2*+1 k! fewer calls tt ToMP and 2k! fewer calls mp OMMP (at the cost of computing the NPN canonical form and transformations). The red and blue shaded regions depict NPN and a equivalence classes, respectively (where two MPs are o-equivalent if their outputs over x E B* are equivalent under threshold).
Figure 3 depicts one of the NPN equivalence classes for k NPN classification provide us with a way to partition the set of BPs in Gr, into equivalence classes, where each function in class is related by an NPN transformation. We can now investigate how to define solutions to the subproblems of obtaining MPs and MMPs in terms of NPN classes whole. The central idea is to transform functions in the same equivalence class into a designated canonical form, perform ToMP and TрTMMMP on the canonical form, and then use inverse transformations convert the solutions for the canonical form into solutions for all members of the class. The first question we must address is whether the MMP solutions we obtain for members of the class are ~r, equivalent to their MPs.
Theorem 3.2 (NPN transformations between a equivalence classes), Let p. q E 2²t be MPs of nFs such that p (q)) where an NPN transformation and q' E [q].. Then r(q') [p]..
We introduce a running example. Let Kp E - be the NPN canonical form of MP E 22' meaninn there exists
(Tr Tx TQ) such that r(p) -Kp- Now let Kip' be Kp w.r.t. some criterion c E g² Since (kpp p. Theorem 3.2 ensures us that 7 (Kp') E [p].. Hence, we one step closer to converting the MMP solution of the canonical form into MMP solution for a member of the class. The final question is whether - ((Gp/) is minimum w.r.t. the cost function defined by criterion c. We introduce the following notions of invariance answer this.
transformation
of
Definition 3.7 (PN-invarianl criterion). Let z²² be an MP, Tx be an input permutation, and T be an output polarity assignment. A criterion vector
2²a is PN-invariant if
||c O pll = | (T o To (p)]1..
Ang are PN-invariant Lemma 3.2 (Uniform & degree criterions are PN-invariant), cgms and cx
a criterion is PN invariann,, it means that the MMP cost function of MP p will not change when we apply input permutation and output negation transformations on p. However, it says nothing about
7

---

Published as a conference paper at ICLR 2025
input negation transformations Tá- Consequently, if Kip' is an MMP w.r.t. either the degree or uniform criterion, cannot say for certain that (K'p)) (Th Ta o TT))=((kp)) is MMP of p. since To= is being applied. This suggests we should apply the inverse phase assignment before finding an MMP. This idea is captured in the following two thcorems.
Theorem 3.3 (Inverse NPN transformation). Let = To o Tx To be an NPN transformation. Then T Tv Ta
(T())- We call Tr(ø) the permuted phase assignment.
Theorem 3.4 (Computing MMPs with NPN transformations under PN-invariant criterions). Let c E z² be a PN-invariant criterion, p, q Z² be MPs of nFr such that p (Fv (q), and q' [g)a be an MMP with respect to criterion c. Then p' = (Tv o Tx (q') E [p], is an MMP with respect to criterion c.
Using Theorem 3.3, can firstly apply the permuted phase assignment to the canonical form Ta(() and then obtain MMP of the resulting MP w.r.t. either the degree uniform Tr(p) Kp
criterion, which we denote Kip' -=(o)) Now, since all the conditions of Theorem 3.4 are satisfied, comput- ing (To Tx-1 Tx-1)(K;p))) (x= (00) results in MMP for p (see Figure 4). Following these ideas, we propose an opimmization-ojjecciieaaaaa NPN classification algorithm for MP- and MMP-based technology map- ping. The complete algorithm, a formal analysis of its advantages over unique function caching, and the time complexity of computing NPN canonical forms and transformations are provided in Appendix D.4.
3.3 ARCHITECTREE-AWAR LOSSLESS OPTIMIZATION
The previous section provides us with a technique for accelerating the acquisition of all MPs and MMPs of Bis in a BN. We now consider how to use these two representations to optimize the two kinds of nn architectures that result from the SOTA mapping procedure reviewed in $ 2.2: unmerged and layer-merged NNs. We begin by connecting this goal to the technology mapping discussed in 2.2.
NN-based technology mapping from MP and MMP BNs. Let G = (V, E) be a BN, VpT S V
2²2 be the labeling functions following MP- and bMP-based technology mapping, respectively. Moreover, let M S V \ VpI be a subset of vertices selected to be represented as MMPs. Then, if & .,, its resulting two-layer NN is of the form ((x) = W2o(W1x + b)). If u E M, its resulting two-layer NN of the form (x(x) a (W (W b,)). We consider three optimization algorithms for selecting M:
denote the set of PIs, and dit vi V + F. _
NotNo no vertices in the en are represented as MMPs (M 9). This results in no compression and corresponds the SOTA NN-based technology mapping solution of Gavier et al. (2023).
optAll: all vertices in the bN are represented as MMPs (M = VV VpT).
optMaintainn ainetthh: a subset of vertices are selected to be represented as MMPs such that the depth of the resulting layer-merged nn does not increase (M C V Vrr).
Applications that seek maximal compression would choose optAll, whereas applications that require latency (depth) constraints would choose optMaintar intehh..phh... In the remainder of this section, we develop an algorithm for optMaintainDepthh Suppose o E vertex on longest path in Gr. Then following inter-depth composition, e will be on a longest path in the resulting layer-merged NN. Hence, if v were to be represented as an MMP, an additional layer would be required to compute its output due to the addition of a threshold on its output neuron; pushing all of v's descendants forward, and thus increasing the depth of the layer-merged NN. (Note we require v to be non-PO vertex in this argument since POs do not have any successor to merge with, and hence can always be represented as MMPs without increasing depth). In contrast, if were not on a longest path in Gy., then the additional layer compute e would not cause the depth of the NN to increase. The following definition and lemma capture this insight.
VpI is a non-PO
Definition 3.8 (Leeway). The leeway of vertex v E V BN G7 = (V, E) is defined as
leeway(v) = depth(GF)) - depth(v) - Ipl(w) E No.
(10)
where (p)(e) denotes the length of the longest path from any PO in GF.
Lemma 3.3 (Zero leeway indicates membership in longest path). Let Gy = (V, E) be a bN and E V be a vertex. Then leeway < is on longest path in Gz.
8

---

Published as a conference paper at ICLR 2025
vart : (1,928)
sha3 (31,144)
ecg (105,713)
(126.883)
100
20
18
14
12
10
10
28
20
18
32
16
12
10
20
14
12
10
8
10
10
2 K
6
2
4
6
8
10
K
K
Connections
Neurons
dey
Depth
(a) Reduction in connections (blue) and neurons (red) relative the unmerged by optimizing all sub-NNs with the proposed optAll algorithm. Both criterions achieve significant size reductions.
uart (1.928)
sha3 (31,144)
ecg (105,713)
aes (126,883)
100
60
40
20
18
8
7
24
11
10
17
10
2
10
6
2
6
8
10
K
K
K
% Connections
% Neurons
dag
Depth
(b) Reduction in connections and neurons relative the layer-merged NN by optimizing subset of sub-NNs selected by proposed optMaint ainDetth algorithm. The size of the layer-merged NN able be reduced without increasing its depth. The degree criterion leads to larger reduction.
Figure 5: Neural network (NN) lossless optimization with respect to the uniform (c"mi) and degree (c criterions for minimal multilinear polynomials (MMPs) (see Definition 3.1). We find that the size (both terms of connections and neurons) unmerged (a) and layer-merged (b) NNs can be reduced by optimizing the sub-NN representations via MMPs, depths shown in gold. Circuit sizes are shown parentheses in terms of the number of logic gates.
Since Gy = (V, is DAG, computing the leeway for all vertices can be done time O(V + F). This lets us propose a O(V(V + E)) time algorithm for SotManntainDepth that repeatedly selects vertices for M that have positive leeway (i.c., are not on a longest path). Each time a vertex selected to be represented as an MMP, the algorithm augments the graph by adding predecessor hidden vertex to simulate the increase in path length for all paths containing this vertex. This ensures the depth of the optimized NN the same the layer-merged NN. In Appendix we present the complete algorithm and illustrate it with figure.
RESULTS
We evaluate the proposed architecture- and objective-aware optimization algorithms on four BNs derived from digital circuits: uart, sha3, ecg, and aes (see Appendix F for details). In Ap- pendix G.2, we report results on additional BNs to provide comprehensive analysis. Experiments were conducted on an Intel(R) Xeon(R) Gold 6230R CPU 2.10GHz with 196 GB RAM. We use the algorithm proposed by Zhou et al. (2020) to compute NPN transformations and canonical forms. As the mapping procedure is deterministic, we only show statistical significance for timing results.
4.1 ARCHITECTURE-AWAN LOSSLESS OPTIMIZATION OF NEURAL NETWORKS
We consider two settings under which apply the architecture-awart lossless optimization algorithms. The first setting considers optimizing unmerged NN that results from NN-based technology mapping. In this case, apply the optAll optimization algorithm to evaluate, without depth constraint, how many neurons and connections can be removed from the NN while maintaining functional equivalence (see Figure 5a). The second setting considers optimizing the layer-merged Nn. We apply the MatMaint a ainDepth optimization algorithm to see how many neurons and connections can be removed from the while maintaining both its depth and functional equivalence (see Figure 5b).

---

Published as a conference paper at ICLR 2025
Optimization time (s)
uart t (1,928)
sha3 (31,144)
eog (105,713)
(126,883)
10
34.3x
10
10
5.9x
10'
100
10
10"
10
10
10%
K
K
K
Naive
Cached
NPN classes
Figure 6: Accelerating neural network (NN) optimization with Negation- Cecaation-errutattiinn CntiuuttttooNNegaation (NPN) classification. The optimized NN representation of Boolean network (BN) with vertices associated with k-input truth tables, 1 < & < K, requires computing the multilinear polynomial (MP) and obtaining a minimal MP (MMP) for each vertex. Naive (blue) solves each vertex independently, while Cached (red) does per unique function. NPN classes (green) solves using the proposed objective- aware NPN classification algorithm. We report the optimization time MP- and MMP-based technology mapping w.r.t. the uniform (c" and degree (c=e)) criterions. NPV classes results in consistent speedups under both MMP criterions, achieving 34.3x for sha3 (K = 10, czmi) relative to Naive and 5.9x for aes (K 11, ce relative to Cached. Lines and error bars denote sample mean and standard deviation over trials. Circuit sizes are shown in parentheses in terms number of logic gates. Naive (uart, K 11) and (aes, K 11) not reported due compute constraints.
We note that in Figure 5, the SOTA solution of Gavier al. (2023) corresponds 100% connections and 100% neurons. In the first setting, optAll significantly optimizes the structure of the NN, reducing the connections and neurons by up to 70% and 60%, respectively. In the second, depth- constrained setting, optMaintainng 20%, respectively. We observe that the degree criterion consistently results in fewer connections and neurons than when optimizing with the uniform criterion.
reduces the connections and neurons by up to 50% and
4.2 ACCELERATING OPTIMIZATION USING SHARED REPRESENTATIONN
Here we apply the objective-aware NPN classification algorithm from 3.2 to accelerate NN opti- mization. Due to lack of prior work, we define two baselines for comparison. Naive computes the MP and obtains an MMP per vertex in BN GFy, whereas Cached does so per unique BR, NPV classes implements the proposed NPN classification algorithm to compute MPs and obtain MMPs. See Figure 6. We found that when the BN or K is small, NPN classes is competitive with Cached. However, for larger circuits and K 2 4, NPN classes consistently accelerates the optimization time in comparison to both baselines, independent
the MMP criterion used. In particular, the greatest speedup of 34.3x was achieved for sha3 (K 10, cnns) relative to Naive, and a speedup of 5.9x was achieved for the largest circuit aes (K = 11, dggg) relative to Cached (we analyze this result in Appendix G.3).
For larger BNs, we observed that the optimization time starts high for small K, lessens for intermediate K, and then increases again for large K. When the BN is large and K small, there a relatively large number of vertices in GJ (V, E). Consequently, the mapping time is dominated by iterating over V. In contrast, for large K, although Gr, has fewer vertices, the mapping time increases due to the runtime of ToMP and TOMMMMP. Intermediate K avoids both extremes.
5 CONCLUSION
In this paper, we proposed techniques for optimizing the NN representation of a BN. Realizing the NN representation is composed of various sub-NNs, we began by establishing a relationship between MPs and sub-NN size, allowing us to compress sub-NN: by minimizing the MP representation. Next, to accelerate this minimization, we introduced an objective-aware algorithm to exploit the shared structure in optimization solutions among the members of an NPN equivalence class. Finally, we integrated these insights into architecture-awan aware lossless compression algorithms that allow for an optimization in both depth constrained and unconstrained settings. Our experimental results demonstrate that our methods lead to significant optimization in NN size, as well as consistent speedups in the optimization process. Broader impacts of our work are further discussed in Appendix I.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
The authors would like to thank Arjun Karuvally from the University of Massachusetts Amherst for insightful feedback on an earlier draft of the manuscript. This research was supported in part by the Defense Advanced Research Projects Agency (DARPA) under contract number HR001 12190049,
REFERENCES
Stefano Ambrogio, Pritish Narayanan, Atsuya Okazaki, Andrea Fasoli, Charles Mackin, Kohji Hosokawa, Akiyo Nomura, Takeo Yasuda, An Chen, A Friz, et al. An analog-ai chip for energy- efficient speech recognition and transcription. Nature, 620(7975):78--75, 2023.
Surama Biswas, Santosh Manicka, Erik Hoel, and Michael Levin. Gene regulatory networks exhibit several kinds of memory: Quantification of memory in biological and random transcriptional networks. Iscience, 24(3), 2021.
Kwabena Boahen. Dendrocentric learning for synthetic intelligence. Nature, 612(7938):43-50, 2022.
Stefan Bornholdt. Boolean network models of cellular regulation: prospects and limitations. Journal of the Royal Society Interface, (Ssuppl_1::S85---1 S94, 2008
Jason Cong and Yuzheng Ding. Flowmap: An optimal technology mapping algorithm for delay optimization in lookup-table based fpga designs. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 13(1):1-12, 1994.
Matthew Parrugia-Roherts. Functional equivalence and path connectivity of reducible hyperbolic tangent networks. Advances in Neural Information Processing Systems, 36, 2024.
Mingbin Feng, John E Mitchell, Jong-Shi Shi Pang, Xin Shen, and Andreas Wächter. Complementarity formulations of 10-norm optimization problems. Industrial Engineering and Management Sciences. Technical Report. Northwestern University, Evanston, II, USA, 5, 2013.
Ignacio Gavier, Joshua Russell, Devdhar Patel, Edward Rietman, and Hava Siegelmann. Neural network compiler for parallel high-throughput simulation of digital circuits. In 2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 613-623. IEFE, 2023.
Frédéric Gruau, Jean- Yves Ratajszezak, and Gilles Wiber. neural compiler. Theoretical Computer Science, 141(1-2):1-5,, 1995.
John Hewitt, Michael Hahn, Surya Ganguli, Percy Liang, and Christopher D. Manning. RNNs can generate bounded hierarchical languages with optimal memory. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (eds.), Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 1978-2010, Online, November 2020. Association for Computational Linguistics. doi: 1tt18665//11/222.mmmmm...
Uwe Hinsberger and Reiner Kolla. Boolean matching for large libraries. In Proceedings of the 35th annual Design Automation Conference, pp. 206-211, 1998.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks universal approximators. Neural networks, 265):35 1989.
Richard M. Karp. Reducibility among Combinatorial Problems, pp. 85-103. Springer US, Boston, MA, 1972. ISBN 978-1-4684-2001-2. doi: 10. 10.10077978-1144684-000 2000-222..
Arjun Karuvally, Terrence J Sejnowski, and Hava Siegelmann. Hidden traveling waves bind working memory variables in recurrent neural networks. arXiv preprint 101163, 2024.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521((553):436 2015.
Yingjie Li. Mingju Liu, Mark Ren, Alan Mishchenko, and Cunxi Yu. Dag-aware synthesis or- chestration. IEEE Transactions on Computer- Aided Design of Integrated Circuits and Systems, 2024.
11

---

Published as a conference paper at ICLR 2025
Zhuo Li, Hengyi Li, and Lin Meng. Model compression for deep neural networks: A survey. Computers, 12(3):60, 2023.
Tailin Liang, John Glossner, Lei Wang, Shaobo Shi, and Xiaotong Zhang. Pruning and quantization for deep neural network acceleration: A survey. Neurocomputiing 461:370-403, 2021.
Dian-Lun Lin, Haoxing Ren, Yanqing Zhang, Brucek Khailany, and Tsung- Wei Huang. From rtl to cuda: A gpu acceleration flow for rtl simulation with batch stimulus. In Proceedings of the 5 International Conference on Parallel Processing, pp. 1-12, 2022.
Dian-Lun Lin, Yanqing Zhang. Haoxing Ren, Brucek Khailany, Shih-Hsin Wang, and Tsung-We Wei Huang. Genfuzz: Gpu-accelerated hardware fuzzing using genetic algorithm with multiple inputs. In 2023 60th ACM/IEEE Design Automation Conference (DAC), pp. 1-6. IEEE, 2023.
Alan Mishchenko, Satrajit Chatterjee, and Robert Brayton. Dag-aware aig rewriting a fresh look at combinational logic synthesis. In Proceedings of the 43rd annual Design Automation Conference, pp. 532-535, 2006.
João Pedro Neto, Hava T Siegelmann, and J Félix Costa. Symbolic processing in neural networks. Journal of the Brazilian Computer Society, 8:58-70, 2003.
Ryan O' O'Donnell. Analysis of functionnss Cambridge University Press, 2014.
Devdhar Patel, Ignacio Gavier, Joshua Russell, Andrew Malinsky, Edward Rietman, and Hava Siegelmann. Automatic transpiler that efficiently converts digital circuits to a neural network representation. In 2022 Internationaa Joint Conference on Neural Networks (IJCNN), pp. 01-08, 2022. doi: 10. 11091CCNN550644202229999900
Ana Petkovska, Mathias Soeken, Giovanni De Micheli, Paolo lenne, and Alan Mishchenko. Fast hierarchical npn classification. In 2016 26th International Conference on Field Programmable Logic and Applications (FPL), pp. 1-4, IEEE, 2016.
Xiangyu Qi, Yi Zeng, Tinghao Xie, Pin- Yu Chen, Ruoxi Jia, Prateek Mittal, and Peter Henderson. Fine-tuning aligned language models compromises safety, even when users do not intend to! arXiv preprint arXiv:2310.03660 2023.
Hao Qian and Yangdong Deng. Accelerating rtl simulation with gpus. In 2011 IEEE/ACM Interna- tional Conference on Computer-Aided Design (ICCAD). pp. 687-693. IEEE, 2011.
Mingyi Rao, Hao Tang, Jiangbin Wu, Wenhao Song, Max Zhang, Wenbo Yin. Ye Zhuo, Fatemeh Kiani, Benjamin Chen, Xiangqi Jiang, al. Thousands of conductance levels in memristors integrated on cmos. Nature, 615(7954):823- 822-829,228888 2023.
Tsutomu Sasao and Jon Butler. Progress in Applications of Boolean Functions. Springer Nature, 2022.
Thiago Serra, Abhinay Kumar, and Srikumar Ramalingam. Lossless compression of deep neural net- works. In International conference on integration of constraint programming, artificial intelligence, and operations research, pp. 417-430. Springer, 2020.
Hava T Siegelmann. Neural programming language. In AAAI, pp. 877-882, 1994.
Hava T. Siegelmann and Eduardo D. Sontag. On the computational power of neural nets. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory, COLT '92, pp. 440-449, New York, NY, USA, 1992. Association for Computing Machinery. ISBN 089791497X. doi: (431145/13385.1333
Michael Sipser. Introduction to the theory of computation. ACM Sigact News, 27(1):27-29, 1996.
Emma Strubell, Ananya Ganesh, and Andrew McCallum. Energy and policy considerations for deep learning in nlp. arXiv preprint arXiv:1906.0222 2019.
HéctorJ Sussmann. Uniqueness of the weights for minimal feedforward nets with a given input-output map. Neural networks, 5(4):589-593, 1992.
12

---

Published as a conference paper at ICLR 2025
Tze Sin Tan and Bakhtiar Affendi Rosdi. Verilog hdl simulator technology: survey. Journal of Electronic Testing, 30:255-266 26955--6,,200 2014.
Sunil Vadera and Salem Ameen. Methods for pruning deep neural networks. IEEE Access, 10: 63280-63300, 2022.
Zishen Wan, Che-Kai Liu, Hanchen Yang. Chaojian Li, Haoran You, Yonggan Fu, Cheng Wan, Tushar Krishna, Yingyan Lin, and Arijit Raychowdhury. Towards cognitive ai systems: survey and prospective on symoolyymboli ai. arXiv preprint arXiv:2401.00 01040,, 2024.
Yanqing Zhang, Haoxing Ren, and Brucek Khailany. Opportunities for rtl and gate level simulation using gpus. In Proceedings of the 39th International Conference Computer-Aided Design, pp- 1-5, 2020.
Xuegong Zhou, Lingli Wang, and Alan Mishchenko. Fast exact npn classification by co-designing canonical form and its computation algorithm. IEEE Transactions Computers, 69(9): (000)):299333331 2020.
13

---

Published as a conference paper at ICLR 2025
Appendix
Table of Contents
Appendix Outline
14
B Background
15
Minimal Multilinear Polynomial Representation
20
C.I. Suhoptimality of Ei-Relaxation in MMP Problems
24
D Objective-Aware Optimization using NPN Classes
26
D.1 Computing Inverse NPN Transformatons.
30
D.2 Relating NPN and a Equivalence Classes
33
D.3 Computing MMPs with NPN Transformations
35
D.4 Objective-Aware Optimization Algorithm using NPN Classes
37
D.5 Relation to Existing NPN Classification Techniques and NPN Invariance
40
E Architecture-Aware Lossless Optimization
42
F Digital Circuits and Automata used in Experiments
45
Extended Results
47
G.1 Accelerating MP-based Technology Mapping with NPN Classification
47
G.2 Results on Additional Boolcan Networks
47
G.3 Empirical Analysis NPN Classification
50
H Synthesized Neural Networks for Figure
51
Broader Impacts
52
A APPENDIX OUTLINE
This appendix has the following order. In Appendix B, we define the truth table and multilinear polynomial (MP) representations of Boolean functions (BBS), and show how these representations are related via linear transformations. In Appendix C, we define the ~a relation between BFs to capture the notion equivalence under threshold and prove that it is an equivalence relation. We proceed to define minimal MP (MMP) representation of BF in terms of a equivalence classes, and by proving that linear constraints determine a equivalence class, show that such a representation can be obtained by solving an integer linear program. In Appendix D, define Negation (NPN) transformations and prove how these transformations act on MPs. In Appendix D.I, we prove that the inverse NPN transformation can be computed in non-standard order, result relevant for reusing solutions to MMPs. In Appendix D.2, we prove that the functions in the a equivalence equivalent functions are related via transformations. This result is applied in Appendix D.3, where we define the notion of PN-invariant criterions for MMPs, and prove that MMPs under PN-invariant criterions can be computed from other MMPs using NPN transformations. In Appendix D.4, we use these results to define an objective-aware algorithm based on NPN classification for MP- and MMP-based technology mapping that computes MPs and MMPs via NPN canonical forms in order to minimize the number of calls to computationally expensive procedures. In Appendix E, we define various neural network (NN) compression algorithms that incorporate MMPs into NN- technology mapping. We present O(V(V E)) time algorithm that greedily selects vertices in Boolean network (BN) to be represented as MMPs while ensuring the resulting layer-merged NN depth does not increase. Finally, Appendix details the circuits and automata used in experiments, and Appendix G presents additional results and analyses. Appendix presents the synthesized neural networks (NNa) for Figure 7, and Appendix concludes with the broader impacts of our work.
Eegaation-Permutatii
classes of
14

---

Published as a conference paper at ICLR 2025
Table 1:
Outline of the key definitions, statements and algorithms covered the appendix. Hyperlinks provide correspondence between definitions and statements in the main paper and in the appendix.
Defimition/Statement
Main paper
Appendix
Boolean function (BF)
Definition 2.1
Definition B.1
Truth table representation of a BF
Definition 2.2
Definition B.3
Multilinear polynomial (MP) representation of BF
Definition 2.3
Definition B.4
The ~a relation
Definition 3.2
Definition C.2
Minimal MP (MMP) representation of BF
Definition 3.3
Definition C.4
Uniform criterion
Definition 3.1
Definition C.5
Degree criterion
Definition 3.1
Definition C.6
(NPN) transformation Boolean network (BN)
Definition 3.4
Definition D.1
PN-invariant criterion
Definition 3.7
Definition D.5
Definition 2.4
Definition E.1
Leeway
Definition 3.8
Definition E.3
The ~a relation is an equivalence relation Linear constraints determine a equívalence class Obtaining an MMP representation of BF Inverse NPN transformation
Lemma C.1
Theorem 3.1
Theorem C.1
Corollary 3.1
Corollary C.I
Theorem 3.3
Theorem D.1
NPN transformations between equivalence classes Uniform criterion is PN-invariant
Theorem 3.2
Theorem D.2
Lemma 3.2
Lemma D.13
Degree criterion is PN-invariant
Lemma 3.2
Lemma D.14
Computing MMPs with NPN transformations under PN- invariant criterions
Theorem 3.4
Theorem D.3
MP- and MMP-based technology mapping with NPN classes
Algorithm
Maintain depth neural network optimization algorithm
Algorithm
B BACKGROUND
Remark B. We denote the set of binary numbers as B (0, the set of natural numbers (including
0) as No {0, 1, ........ 3, and the set of integers as Z, (..., 1, ....
Definition B.1 (Boolean function). A k-iinpt, (single-output) Boolean function (BF) is function f: B² > IB, x >> ((x), where x = (zi,-..; .x) is a bit vector representing the input variables I, E IR < < If bit vector æ. when interpreted binary number (947s-1...2)) encodes
value E {0,
2 1}. we write (im).
Example B. If k 3, (4) is the bit vector 12,, Xz) = (0,0, 0, 1) since its interpretation as binary number ( ) = (100), encodes the value 4.
Definition B.2 (Multilinear polynomial). A degree-k multilinear polynomial (MP) a polynomial in variables Σ1.- .......2 2g where no variable occurs to power of 2 or higher.
Example B.2. k = 2, x2) = x1 + D2 I1 22 is MP whereas ((11, = of + 2 is not.
Definition B.3 (Truth table representation of BF). The truth table representation an expression of BF f : 1 + B in the basis of the indicator functions la B + IB, E B*
11 aa (x) = {1)
if = a. otherwise.
(11)
The expression of ff in this basis is
f(x)
Σ f(a)la()).
(12)
aEB
The truth table vector f E B²* of f is the dimeennsio vector of coefficients f(a) in the above linear combination of indicator functions. Hence,
f Σ f(a)la:
(13)
aEB
15

---

Published as a conference paper at ICLR 2025
where 1a B² denotes the vector with 1 in the i-th coordinate, 0 i 2 and 0's elsewhere, if = (())-
Example B.3. Let (2) 21 + 22 21 22. Then the truth table representation of f expression
x2) = Σ f(a))a((1,1)
aE
= 0) (o,0) x2)
f(1, 0) (1,0 f(0, (o)
f(11 I + (1))a.n((21
(z)
(0)
+ a
and the truth table vector
B of is
0
O
f(0,0)
1
f(1.0)
f= Σ [a))== S(0,0)
f(1,0)
+
1)
+ ((,
0
1(0.1)
QEB
((1
Definition B.4 (Multilinear polynomial representation of a BF). The MP representation is an expression of f 3* + B in the basis of the logical AND functions Xs 2 E, S E P((l...., kJ). where P--) denotes the power set,
f1, [.IEs Ttz
if i = 0, otherwise.
Xs(x)= =
(14)
The expression of f in this basis, which we denote p 2 2s
p(x:) = E
f(S)xs(2).
(15)
SEP((I....k))
where f(S) E E and Vx B* (f(x)) p(æ)). The MP vector p z² of f is the 2 di-deennion vector of coefficients f(S) in the above linear combination of logical AND functions. Hence,
Σ
f(S)xs:
(16)
SEP((I.....))
where Xs E -² denotes the vector with a 1 in coordinate I(S), 0 < Z(S) < 2 1, and 0's elsewhere, and I : P([1, ......... k)) + (O....2 .2 13 is a bijection with specification (0, 0). ({1}, 1), (f2). 2). 21, 3). ({3), 4). (f1....,,)) k). 1).
Remark B.2 (Obtaining coefficients f(S) in the representation). We briefly mention method for obtaining the coefficients in the MP representation of or f B² > B, which also serves as a construction proof for the representation Oonnelll,, 2014). Firstly, define the indicator MPs Pa : T Z, a B
pd (z)
II (1 a; Iz + 2a,r,).
The indicator MPs have the property that for all E Bh pl equals 1 if x and 0 otherwise. Let p: k + be the MP
p(x)) Σ (a))d(a))
(17)
aE3x
then Vo E (*( p()) (follows from Equation 12). Since the indicator MPs pa()) are multilinear, simplifying p(æ) will produce MP with the coefficients f(S) E Z, S E P([I...., in the MP representation of f. Lemma B.I generalizes this conversion procedure.
Example B.4. Let f(11, x1 = x2 representation of / is the expression
σ xz. Example B.3, we found that the truth table
f(11, = Σ (()12
aE
(1) 22) (0) + (1) (21, + (1) (2).
16

---

Published as a conference paper at ICLR 2025
Let p:: Z - Z be the MP p(21,
EaeB: ((1)))((1)22) then
Σ
f(a)pp
aE32
=1))fo,0, (x1, 22)
+ (0) (2), 22) (1) (1),
(1)(1 - -x1)(1 222)
+ (0)(z1)(1 x2) (1)(1-
+ (1)(21)(22))
(1-21 22 2102)
+ (0)
+ (x102)
(1)(1)
+ (-1)(an)
(0)(222
+ (1)(1102)
(1)x0
+ +-1)xx
+ +0)x12)
+ (1)x(12)
E (())))(F1,
SEP((1.))
and EsEP((Le)) f(5)xs(11 x2) is the MP representation of f. The MP vector E 2² of f is
= Σ
f(S)xs f(0)
+ f((+))
0
1
+
f(12))
+ f((1,2) 2))
0
0
SEP((1.2)
f(0)
1
1
f((1))
f((2))
0
(((1.2))
Definition B.5 (Cofactors of BF and its MP representation). Let i {I,...,k)} and f : B* + be a BF with MP representation 2 + 2. The positive and negative cofactors of f with respect to æ; are the BFs far fE. B h- B, where
fa. f( T3 1,...),
fa. f(..., O....).
(18)
Similarly, the positive and negative cofactors of p with respect to x; are the MPs Pr;:Pa; where
7 Z
Ps. = p(. l,...),
Pa. = :(...,,, = =........
(19)
Note that Pz, and Pa. are the MP representations of fa, and f2. respectively.
Definition B.6 (Fourier transformation matrix). Let e No and Ta E - specification
be a matrix with
[ k 0,
T Th-1,
Ok-1 -Te-11 T--1
(20)
k 0,
where Ox-1 E 1 -1 denotes the all zeros matrix. We call Ti the k-th Fourier transformation matrix.
Lemma B.1 (Computing the MP vector from the truth table vector). Let k E No. f BB B be aF with truth table vector f E 1B22 and Mp vector p E 7?* and T E =2*x2* x2" be the k-th Fourier transformation matrix. Then TxJ p.
Proof. We prove this statement by induction on k Ng.
Basis (k = 0). Let f ::BB - be the constant BF f() = c. where c E B. Then f = [c] and = [c].
Thus, To [1), Taf p.
17

---

Published as a conference paper at ICLR 2025
Inductive step (assume 1). Let f B + E be BE: Following Boole's expansion theorem,
f(x) Σ (a))
(21)
aEB
Σ
(a))la(
(22)
( 1.00 1
+
Σ
f(a)la(()
(23)
= =((o)(ER)
Σ
() ((a.)).)........ 2x-1)
(24)
+ +
Σ
f(a, ( TA-I.....
(25)
= [o0 (F ( x2-1) + (1)(22)) (T1, (II,
(26)
Hence, following the discussion in Example B.4, MPp p: / with specification
p(x) = p(oo((r))
Σ
fla. 0)p (,,,..,, (..1.)
(27)
a am 1)ERK-1
+ Pray( (3xe
Σ
f(a, 1)pa ( #k-1))
(28)
a= (1 1)EB--1
(1x) (I1,..., Ia 1) + P(1) (a (as
(29)
= (1 3kk TK (f1,..., xk-1) 1) + (F (#1, Fk-11
(30)
Pau (II,... I1) + (pxy (I1,..., Fs x1- - Pax (II,..., Ih xk--)) xb
(31)
has the property that Væ B& (f(z) p(x)). We next consider the truth table vector f E R²* and MP vector E Z²² of f. From the above analysis, they must have specifications
f
PSN. PSL
f =
(32)
f
Pa.
nx
where f.y: fz, E 2 and Psu, Pa. E 2 Thus, by the inductive hypothesis for k 1, the following sequence of equalities completes the lemma,
Txf =
-Tk-1, Tk-1
Th-1, OK-1l
fax]
fx
Ps. Pox
Pa.
= =p
(33)
Example B.5. We now find the vector from Example B.4 using matrix multiplication. Let f(1 22) 31 32 Fy ay be BE with truth table vector f B² and MP vector p E z²² Following Example B.3,
00
f Σ Ma)laa
Following Lemma B.I, we have
0
Σ
1
1
0
p
0
1
=
SEP((I.....I)
-1
-1
which result for the vector of in Example B.4.
18

---

Published as a conference paper at ICLR 2025
Definition B.7 (Sierpińskki matrix). Let ls E Ny and Sy x2*
be matrix with specification
[1]
k 0,
Sk-1,
Ok-1 Sk-1
(34)
k >>> 0,
Sk-1,
where Ok-1 B 1x2* denotes the all zeros matrix. We call Sy the k-th Sierpiñski matrix. Lemma B.2 (The Sierpiński matrix is the inverse of the Fourier transformation matrix), Let No. Ty E 72 x2 be the k-th Fourier transformation matrix, and Sy BB2xx2 x2" be the k-th Sierpiñski matrix. Then Sa = I,, where Ig E [B2 x2" is the identity matrix.
Proof. We prove this statement by induction on E No.
Basis (k = 0). SoTo = [1] [1] To- Inductive step (assume Sr Ix).
Sk 02
Tk
Ok
TaTR Ok
Ok SaT
Ik:
O2
Sk+1Tk+1
Ikt1-
(35)
Sk,
Tk
Tx
Ok,
1x
Corollary B.1 (Computing the truth table vector from the MP vector). Let k E No. S B
B be
with truth table vector f E TB²² and MP vector p 82*h and Sy E B2 x2" be the k-thh Sierpiíski matrix. Then S&p = f.
Proof.
Spp S.Tif
(36)
where T& Z²2 x2" is the k-th Fourier transformation matrix, and the first equality follows from Lemma B.1.
Example B.6. We can now find the truth table vector from Example B.3 using matrix multiplication.
Let ((1 [t) = xı + x2 = 3n V za be BF with truth table vector f E B² and MP vector E 2 Following Example B.5,
p Σ
f(S)xs
0
SEP(
Following Corollary B.1, we have
1
0
0
07
f= Σ f(a)1a = Syp
0
0
0
0
1
4E33
1
1
1
which was our result for the truth table vector of f in Example B.3.
Remark B.3. In the following sections, we refer to the truth table (resp. MP) representation and the truth table (resp. MP) vector BF interchangeably. Boldface notation is used vectors in order to distinguish between the objects.
19

---

Published as a conference paper at ICLR 2025
C
MINIMAL MULTILINEAR POLYNOMIAL REPRESENTATION
Definition C.I (Heaviside step function). Let a: 2 + B be function with specification
1, 0, 0,
(x)
(37)
r x
We extend the definition to a: z² B where (o(x)), = oαx; (i.e., it is applied element- wise).
glement-wise).
Definition C.2 (The ~- relation). Let p. 2²t be MPs. We define ~g: 2² 2² + .B as the relation
(a p ~ q = Va E B (ooo))aa) ()()))
(38)
Example C.I. Let 32)
+ 2ι 22 be with MP representation p(11, 22)
1 #1 + 21 and MP vector p = 11,01 1j. Moreover, let ((11,
21 + 22 be a MP with
MP vector q [1, 11,-1,1,0) Then ~o q.
p0,,0) = 1,
(0, 1,
p(1, 0) 0,
g1,, (1 0,
p(0, 1) 1,
(00, 1) 2,
p(1,1)=1 =1
((,, 1.
Lemma C.1. ~g is an equivalence relation.
Proof. We show the ~a relation is reflexive, symmetric and transitive. Let p. qr 8² be MPs.
~a is reflexive.
p ~ p = Ya E
(o)))(x))
(39)
= Yx E B (T)
(40)
(41)
~a is symmetric.
p ~r q = Vo E (* = (a 2)()))
(42)
= Vo E B* ()(=)) = (o p))))
(43)
=
(44)
3. ~y is transitive.
p~o A q ~o r
= Vx E B* ((rop)(<) = (oo)) A Ao e (()og)((()) = (o (oor)(z))
(45)
Va E (((op))) (a (oo A (()og)(z)= (a (o)))()))
(46)
Va e (()o)))) = -ooor(
(47)
p ~g
(48)
2²t denoted ppl. the Definition C.3 (a equivalence class). The equivalence class MP p
set {q E 722h p ~g 4).
Definition C.4 (Minimal multilinear polynomial representation of a BF). Let f B + be a BF with MP p E z² and C:: 2 + No be cost function. A minimal multilinear polynomial (MMP) representation of f with respect C is MP p' z where
p' arg min C(g). gE(p).
(49)
20

---

Published as a conference paper at ICLR 2025
Example C.2. Let f(x1, 22 be with representation p(æ1. 2:2) x1 22 21 and MP vector p [0.1.1.-1]. Moreover, let p' (((11 x2) = #1 + 22 be a MP with MP vector p' [0, 0]. Then, under the assumption that C(q) represents the number of terms in g.
p' E arg min C(q),
(50)
gE(p),
and p' is an MMP representation with respect to C.
Definition C.5 (Uniform criterion), Let le No and c
2
be vector with specification
0,
i 0,
(51)
1,
Example C.3. c3 cani D
1,,,,I,,,,,,,,,
Definition C.6 (Degree criterion). Let & E No and deg E 2 be vector with specification
[0] k
deg Ck
(52)
deg Ck-11
deg Ch-1
+ -
k > O,
where 1--1 E B2a
denotes the all ones vector.
Example C.4. C3
deg E 00, 1,
Lemma C.2 (Cost functions for MMP)). Let E n² be a MP vector, CE L², and C 2²2 + No be cost function with specification C(q) = |/oo, where lo- denotes the zero-norm weighted by vector Then,
C(q) = ||allo.ere the number of non-constant monomials in the MP q.
2. C(q) ||all, day is the sum of non-constant monomial degrees in the MP q.
Proof. Let I(S) be the bijection specified in Definition B.4 to index the components of the MP vector, and 1g Z + B be an indicator function where 1o(x) = < x = 0. Then follows from the definition of the weighted zero-norm:
C(q)= = || egll
(53)
Σ
(c()))(())
)I(S) (1 (1- Lo(f(s)))
(weighted zero-norm)
(54)
SEP((L....k))
(c )I())
(1-1o(((0))
(1 (z()) (AP((11....))))
Σ
(ch II(s)
1o(f())))
(55)
Σ
(1-10(f(s))
(56)
Similarly, 2. follows from the same definitions. We prove this statement by induction on & E No-
(c ))(0) (1 Io([(())) (o (1 1n( 0. Basis (k 0). C(g) |lallo. =c
Inductive step (assume 1: - 1). Let 1 E - denote the all ones vector. Recall from the proof of Lemma B.1 that 14 Ims a2e where Qnz 2z2-1 and Ozg E =22 the vectors
21

---

Published as a conference paper at ICLR 2025
of the positive and negative cofactor of q with respect to ry, respectively. For q Z²" have,
C |1 the
(57)
Σ
(z())
deg
)z(()
(1- (1-1o((()))
(58)
SEP((),..)))
E
(cH1))(0)) (1-1o(f(5))
SEP((L...
E
deg (12))) +1) (1-10(f(SU
(59)
SEP((I...k_I) 1})
= =119a. 1lo, + 11. - qs, 1lo.00 deg + 11 qa 1l..
(60)
Where, by the inductive hypothesis, the first term corresponds to summing the degree of each monomial in q not containing zk: and the second term corresponds to summing the degree minus one of each monomial in q containing Zg. The third term corresponds to the sum of monomials in q containing Ik. Hence, the second and third term correspond to summing the degree of each monomial in q containing Ti-
Theorem C.I (Linear constraints determine equivalence class). Let 2²2 be an MP, (Spp) B²", b 1 2f Z² and A (ddagg())Ss) E 2² where Sy BB x2 is the k-th Sierpiński matrix, 1 E 2 denotes the all ones vector, and is the Heaviside step function. Then, for MP q E Z²²
q
[p)r
Aq b.
(61)
Proof. Let g = S&q E 2²a
We begin by expanding the expression Aq S
Aq S
=2(diag(
(olliag(b)S{))) b)$+)q 1 2f
(62)
= 2 2iaagg (b)aaq < 1, - 2f
(63)
diag( [1 2f)g S 1 2f
(64)
I 1- (f)
0
0
g(aw)) s(am))
1 - 2f(a
1 2f2((m))
0
1 - 25((
2-
5
0
1
-1)J
9 (1)2
2 (a -1)
(65)
(1 ((((w)
1 - 2f(a())
(1
2(((())))((a)))
1 - 2
2
<
(66)
(1 2f 1))
(f(a
Vi E {0, 1, .,.,....,+ 1)(2(1-2((a)))) 2f((g)))) 1 1 21)
2
1
(67)
We next derive equivalence for q [p] in terms of the k-th Sierpiński matrix:
q E [pl. = pp= ~ 9
(68)
= Yx E B² ((o p) = (a (x)))
(69)
= Vi E (0, 10.,....,, 2 1) ()(((()))))) ((S.))))
(70)
= ei (0, 10.,,...,?
2 ((((si)))) (((sk))))
(71)
= vi E (0, 10,1....,,
2 1)(((am) o()(a())))
(72)
22

---

Published as a conference paper at ICLR 2025
We now show both directions.
1. (q [plo = Aq S b): If q E (plo, then by Equation 72,
Ei {0, 1,...,, ,2 ()((m)) o(((a)))))
(73)
Since f(a E B, either f(( or f(a 1. Taking f(am)) = have (g(a ))
which implies g((()) I 0 and that (g(a(n) S 1 as ((a()) 2. Taking f(a 1, we have (g(a())) which implies s(a(s) > 0 and that (g)) 2 1 as s(a()) E Z. Consequently,
E (o. 2 ()((((()) = =(((a))))
Vi E 1, 1) - (1((()))(()) < -12(((a))) (74)
By Equation 67 we conclude Aq - b.
(Aq S q p):): Aq < b. then by Equation 67,
Vi 10, 1, 1...,
2 () - 2f 2f(( 1 -ff(((()))
(75)
Since f(a()) E B, either (() 0 or f(a ) 1. Taking (() 0. we have (g( 1
which implies (((()) < 0 as g((()) & 2. meaning ((((())) = 0 ((a())) Taking ((a = 1,
we have 2g( (a))) 2 1 which implies ((a 2 as g(a()) E Z, meaning 0g (g(a())) = 1 = -((()))
Consequently.
Vi (0, 1........ 2 - (2 (0(( - 2f(a
= EiE (0, 10. ())((a)))) = =(((a())
(76)
By Equation 72 we conclude E [p)...
Remark C.I. Lemma C.2 and Theorem C.I allow us to formulate the MMP problem an fo-morm optimization problem. These problems are known to be non-convex and NP-hard (Feng et al., 2013), so it is not possible to use conventional convex optimization methods find optimal solutions. However, as is common in optimization problems, by relaxing the norm from ty to l,, the cost functions specified in Lemma C.2 become |,e| problem.
||e @ glli, resulting in convex optimization
Example C.5. Let p- = 0, 1, 1 be a MP vector, and C2 : -²th + No be a cost function with specification Cı(q)= |glle,gg... Following Theorem C.1, compute b (1x (r(pp)) and A (()iag()Sst):
2
0
2
22
0
0
b
A
2
-2
0
-
-2
-2
-2
The MP vector that minimizes Cg(g) such that Aq b is q 1,,1,
1J. It also minimizes (i Example C.6. Let p 1, 1, 1 be vector, and C2 T No be cost function with
specification Cz(q) = ||q|l (. Following Theorem C.I, we can compute b = (1, - (0(Pp)
and A ((ddiag()SS..
2
0
0
2
2
0
0
b
A =
2
-2
0
-
-2
-2
-2
The MP vector that minimizes Colg) such that Aq < is q Ci(q).
-1, It also minimizes
Corollary C.1 (Obtaining an MMP representation of BF). Letp 2²² be the MP of f BB* BB x2* f= Syp B²" b 14 2f Zz and A = ((diag(b)Sa) E x2*x where Sy E B2*x2* is the k-th Sierpiński matrix, 1 E 2 denotes the all ones vector, and is the Heaviside step function. Moreover, let C 7,2 Ng have specification C(g) = ||c gll,, where 322 Then the set of
23

---

Published as a conference paper at ICLR 2025
мMP representationns of f with respect C is equal to the solution set of the following integer linear program:
minimize qeza*
C(q),
(77)
subject to Aq S
(78)
Proof. This statement follows from Theorem C.I.
Remark C.2 (Runtime analysis for obtaining an MMP representation of BF). 0-1 integer linear programming, the decision problem in which variables are restricted to take on values in and only the constraints must be satisfied, is NP-complete (Karp, 1972). This implies integer linear programming. the problem we solve to obtain an MMP representation of a BP, is NP-hard. We can also observe that the number of variables, constraints, and possible coefficient values in the program all grow according to (22)).
Due to the problem being NP-hard, we bound the time complexity by considering brute-forte force search for an MMP under a model of computation in which addition, multiplication, inequality checking, and computing the absolute value and indicator function all cost unit time. Let q E g² where 9, E @ { 2 Evaluating Aq < b from Corollary C.1, to check if q is feasible point, requires 2 units of time. Moreover, computing cost function Il-loo.c or II-I1i,e requires 2 + 2 1 units of time.
2k-1] S Z. meaning a; can take on | = 2^ + 1 possible values.
Consequently, brute-force force search over all @) MMP candidates, checking feasibility with Aq b and solution cost with either |l-llu.e or |1-Ili,e. requires time
T ToMMM (k)
-1) (2 + 1)²²* (226+1 + +2++1 + +2 1) S (2 - 24)²² (22kt1 22h+11
1||2 .22h + 26+1 2t 2-11)
(79)
(80)
(81)
(2 22h-2
(82)
22 22k+2
(83)
22 +2k+2
(84)
20(2*))
(85)
We note that while relaxing ll-llo.e to ||-111.c does not reduce the asymptotic time complexity, in practice it allows for the use of branch and bound algorithms that make use of linear program subroutines over the reals. These algorithms tend to find solutions significantly faster than brute-force search. Such a relaxation can however lead to suboptimal solutions. We discuss this point further in Appendix C.I. We add that another relaxation would be to remove integer constraints, solve the resulting linear program, and then round the solution coefficients to the nearest integer. This would provide algorithm with time complexity polynomial in 2 However, since this kind of relaxation can lead to infeasible solutions that would break functional equivalence, we did not consider it.
C. SUBOPTIMALITY L RELAXATIOO IN MMP PROBLEMS
The weighted zero-norms || and ||Pllo.c**> correspond to the number of neurons and (layer
one) connections in the two-layer NN representation of MP p E Z² Consequently, given that our objective is to find sn representations of BNs with as few neurons and connections as possible, would like to find MMP representations of BFs that minimize these cost functions.
However, in Remark C.2, saw that, in the worst case, solving such optimization problem requires a brute-force search, which is computationally intractable even for small & E Ng. This motivated the relaxation to the weighted one-norm ||=I| 1,c in our formulation of MMPs.
While a theoretical analysis of the consequences of this relaxation lies beyond the scope of this work, discuss some preliminary investigations the topic of solution suboptimality.
24

---

Published as a conference paper at ICLR 2025
Table 2: The number (and percentage) of BFs for which the proposition in Equation 86 true.
C
d
k
BFs
Count
(%)
Count
(%)
2
16
0.0
0
0.0
3
256
0.0
0.0
4
65536
180
0.3
557
0.8
Table 3: ct and 6₁ deg - -wighhted zero- and one-norms for MP vector Pox635A E 2 sponding vector Pox635a E 2
and its corre-
Cans
de
|| I-
|1-11 II-II,,epm
|| |1-1l,,
|1-111.e
1,
Pox625a
10
16
21
38
Pox635A
11
14
23
30
Difference
-1
-2
8
Particularly, we consider the following question. Let p' E [p], be an MMP of MP p E Z² w.r.t. the c-weighted one-norm I|.l where e [cumi cdeg). }. Is the following proposition ever true?
1/'' ||1,e |pllo,e ||p'|lo.e-
(86)
That is, by optimizing the MP representation of the w.r.t. the weighted one-norm, increase the value of the weighted zero-norm In such a case, for the purposes of nn compression, we should choose the over the MMP. (Note that the results reported do not do this, selecting MMPs based the value of the weighted one-norm). By iterating over all Bis for E {2, 3, 4), we are able to answer this question in the affirmative. See Table 2. We find that this proposition is not true (for the MMPs found) for all BF with inputs for which this proposition is true. We report one such function below.
and
inputs. However, there a small fraction of BFs with =
Let fox63sx B4 + B be the BF with truth table 0x635A. The MP representation of foxs3sa is
Pox63sa (2,, T3, xA) = I4 + I3 + I1 2rz04 - T2#1 - 21 201
+ 2rg + 33 2ryuztzza.
(87)
The sets of MMP representations of fox635a with respect to |1-111,07 and || 1, have the following polynomial in their intersection
Poxessa (11 (2,, T3, ma)
+.4 43 + .1
2xz344 T244
T233 20143
+ 224334 + 20 - 27 212244 27 2122223
(88)
We report the weighted zero- and one-norms of the corresponding and MMP vectors in Table 3. We see that under the e criterion, the MMP reduces the weighted one-norm by 2, but increases the weighted zero-norm by 1, and that under the ddeg criterion, the reduces the weighted one-norm by 8, but increases the weighted zero-norm by 2. Hence, the weighted one-norm MMP is suboptimal in comparison to the original MP terms of the weighted zero-norm. In regard to the two-layer nn representation of MMP Pox635a. it would have one additional neuron and two additional connections in its first layer in comparison to the two-layer NN representation of MP Pox635A-
We conclude this brief investigation by noting that there are many interesting questions in this direction that remain unanswered, such as the effect of MMP selection based on the weighted zero- norm (instead of the weighted one-norm) when considering the NN optimization algorithms optAll and optMa i ana i nDepth, and, as pointed out by reviewer, the consideration of alternative approximation methods for the weighted zero-norm optimization problem.
25

---

=NPN 9. if there Published as a conference paper at ICLR 2025
D OBJECTIVE-AWARE OPTIMIZATION USING NPN CLASSES
Definition D.1 (NPN transformation). Negation-Permutatioo---ess of a Boolean function (Br) (F BB) multilinear polynomial (MP) (IF Σ) is the composition of an imput phase assignment Td. an imput permutation Tx and an output polarity assignment Ty. where (1....
(NPN) transformation
(1.....kh k), i Φ if and only if z; has negative phase (i.e., 3; is to be negated), t : (1.....k) + (1,..., }3 is a bijection, v E B, and y = 1 if and only if the output polarity is negative (i.e., the function output is to be negated). Applying denoted Tp)) (Te OT, (p). where sv. Tx, Tá E2 + =pe" Whereas applying transformation
transformation T to vector p F2*
to function p F² + FF is denoted por Tr Tn o Tg. where Ta TG. : Fh F and Ty F-+E +
Remark D.I. Let f _B3 + B be in variables 21, 22, T3- An input phase assignment corresponds to selecting subset of variables in f to negate. For example, the selection & = {2,3) corresponds to 9 F2, We say that the phase of 22 and 23 in g negative w.r.t. whereas the phase of # is positive w.r.t. f. Similarly, an output polarity assignment corresponds to selecting whether to negate the output of For example, the selection that the polarity of h is negative w.r.t. S, whereas the polarity of is positive w.r.f. S.
corresponds to h f(x11, 22, 23). We say
Definition D.2 (NPN equivalent). BTs f.g E BB² are NPN equivalent, denoted exists an NPN transformation 7 such that r(f) = g.
Definition D.3 (NPN equivalence class). The NPN equivalence class of BF f E B denoted [f]NNN the set {g E ? f =NPN 9).
Definition D.4 (NPN canonical form). The NPN canonical form of f E B²² denoted x(f)) is mapping 1B2 + 1B2 that satisfies the following conditions:
1. k(f) [flNPN.
2. Vig [f]NeN (x(gg) x())-
Note that the second condition implies that the NeN canonical form of a BF is unique representative of the NPN equivalence class. We denote x(f) as Ky E B2". and the MP of Ky as Kp E z
Remark D.2. There are 2 neN transformations for k-input BPs, as there are 2* possible input phase assignments, k! possible input permutations, and 2 possible output polarity assignments. Hence, an NPN equivalence class contains at most 2 k! BFs.
Remark D.3. The MP representations of BFs 3t, x1 A N2, and 2 22 are I1, 1122, and I1 x2 T2 respectively.
Lemma D.I (Cofactors of vector). Let E (1,..., .......,,, p: 2 Z be an MP, and Pro zk-1 + E be the positive and negative cofactors of with respect to F,s respectively. Then the mr
vectors Ps. E =2" of ps; and p2, given by the following expressions
Ps.
Σ
(f(S) + (())
(89)
Ps:
Σ
f(S)xs.
(90)
SEP((L....NN0))))
Proof. Following the definition of an MP as a linear combination of logical AND functions, we have
(xx)
Σ
f(S)xs(*)
(91)
SEP((I....)))
Σ
i(S)xs(x) +
Σ
i(S)s(())
(92)
SEP((1...H)(11)
SEP KATO)
26

---

Published as a conference paper at ICLR 2025
where we use P([1,.... ...,....K
k} (i}) to denote P(f1....., P([1,..... ...,,... (t)). Thus,
Pr: = p(... Zi = 1....)
(93)
E
(.,)
SEP FMf))
(94)
Σ
Σ
= I....
KMMA))
SEP((1...XAPM
(95)
Σ
(i(s) + ((SU 1....)
(96)
and
Pz. -i. -(.....(==.....) O....)
(97)
Σ
=;0;;
Σ
f(S)xs(..... 0....)
SE SEP (1................ k((())
(98)
Σ
(99)
SEP(LL..A)MO))))
Lemma D.2 (Ta, acting MP vector). Let p E 2² 7 be MP with MP vector p E 2²", and
6 = {i} S (I....,kk k}.
Then the MP vector To, (p) 22" is given by the expression
To. (p)
Σ (f(S) + f(S (i)))
Σ
(-
(100)
SEP(( (M())
Proof. Following Boole's s expansion theorem,
o (.) = p(To, (z))
(101)
- (1-x;)pm,, (a) + z,Pa, , (x) Ps. (z) (pz. (x) Pr. (a)) F4.
(102)
(103)
Substituting for the cofactors according to Lemma D.I, we have
Tox)
Σ
(f(S) + f(SU (i)))x((*)
Σ
f(S)xs(x) Σ
(f(S) ((s))
(104)
SEP(O....
Σ
(f(s) + ((SU
(MP((1....M))))))
+CE
(f)
(105)
Σ
(f(S) + f(SU (()))
Σ (-f(5))xs(x))
(106)
(MMA)
SEP(IL...A/11)))
Lemma D.3 (Tx acting on an MP vector). Let p E Th + be an MP with MP vector p E 22th
and π. (I,...,k) k) + {l,.... k) be bijection. Then the MP vector Tx(p) E 2² is given by the expression
(p))=
Σ
(S)
(107)
SEP((I.....))
27

---

Published as a conference paper at ICLR 2025
Proof.
p(Tx(())
(108)
Σ
[(5)xx(Tx(x))
(109)
SEP(()....))) k()
E
f(5)x=(8)(x))
(110)
SEP(()....)))
Σ
f(T (8)xxs()
(111)
SEP
Lemma D.4 (Tu acting vector), Let E 22 be with Mr vector p 2²" and 1.
Then the MP vector (p) 7?2h given by the expression
Tx(p) = (1- +
Σ
(-f(s))xs-
(112)
SEP
Proof.
(Tu (x)) = - p(x)
(113)
= SEP((I.....))
f(5)xs(z))
(114)
(f(0)xo(z)+ +
E
f(S)xs(z))
(115)
SEP(
- (1=f(0))x((=)++ +
Σ
(=)(5))xo(z).
(116)
SEP(1I...
Where the final equality holds since x0(x) 1.
Example D.1. Let (x1, x2, xz) = (x1 x22) xs. 33 + I 22 - 2232233 and the MP vector of f is
The MP representation of f is f T2)
== Σ
f(S)xs
SEP((123))
=[f(0),
htt0:///....../.u//////////////r 0,,,0,0, 1,000,11
Following Lemma D.2, Top (p) E is equal to
TØl (p) Σ
((S))
+
Σ
(-)(s)) (117)
(EP((L23)))))
SEP((123)\33)
((0))
(0) + (1)
((1))))())
(0) 00
((2)))(())
(0) (0)
(((1,))33)))
(-)+
(118)
-f((3)
-f((13))
3((233))
- f((1,2,3))
which corresponds the MP (poTog) ) (11, 22, (1 23
1110:222111111110 1 -03 11233
28

---

Published as a conference paper at ICLR 2025
Let T221 (1 be permutation with inverse T231 1312 1 ). Following Lemma D.3,
Thpsi (p) E 2 is equal to
Taan (p)
E
(112((()))
(119)
SEP((1.23))
a31)(f(0))
1(0)
Taz(f((1))
f((3))
Tan(((((2))
((())
mnn(f((),2))
f(113))
(120)
msn(((((3))
f((2))
T12 (f((13)))
f((2,3))
Ta12 Tsi2 (f((233))
f((1,2))
TT12 (((1,((2)),))))
f(11,2,3))
which corresponds to the MP (p Trum: (21, 23) 21 + 22 212223.
Lastly, let 1. Following Lemma D.4, (p) E 2 is equal to
Tp(p) = (1 (1-
Σ
(-)(s))xs
(121)
SEP((123))
1 1- f(0)
(0)
-{(1)
0
-f((2)
0
-f(112))
1
(122)
-f((3))
11)
-((1,3))
f((2,3))
1(11,2,3))
which corresponds to the MP (r, (2),
(03 21 Z1
D3 T1
Remark D.4 (Linear algebra perspective). Letp e 2² be vector, の: {i} S {L...., k}. n, Tisii f1..... k} + (1....,k kb be bijections, where Tiesi represents the transposition (1, and 1. Lemmas D.2, D.3, and D.4 respectively show
To. (p) P
Tk-1:
Tx-1
Poc..) p.
(123)
Ok-1,
-1k-1
(p) PxP,
(124)
To (p)
02t-1
p.
(125)
where 02t_1 1 E B² - and I B² x22-1 denote the all zeros vector, all zeros matrix, and identity matrix, respectively, and P.. Pr... E B x2" denote permutation ma- trices. We see Té. (in turn T3) and are linear transformations, whereas т, is an affine transformation.
O
Remark D.5 (Time complexity of computing NPN transformations). If p E z² is stored in memory as a tensor of shape (,,...,2). 2), then computing (p) requires time (k)) from permuting tensor
indices. Computing To. (p) requires time O(k) + 0(2 O(k) O(2*) from (i) tensor index transposition, (ii) adding the bottom half of the top half (O(2*-1) and then sign flipping the bottom half (O(2*-1)) and (iii) tensor index transposition. Lastly, computing (p) requires time O(2)) from vector addition.
29

---

Published as a conference paper at ICLR 2025
D.1 COMPUTING INVERSE NPN TRANSFORMATIONS
Lemma D.5 (Commutability of and Tx), Letp Z² be an MP vector, v B and π fl,..., ,k}
{1....,K k} be a bijection. Then (T, o (p) = (Tx o (p))
= O, then T, Id. and the statement is clearly true. We now consider the case where V= =. Under the functional perspective of T, the statement is equivalent to showing Tu (p Tx) pp) Tr, where z + & is an MP, which holds by associativity of function composition. The statement also follows from Lemmas D.3 and D.4,
Proof. If v=
(Tu (p)) Tv
Σ SEP((I,...)))
f( (8))xs)
(126)
=T (f(IT (0))xo
Σ
f(5 ((x-1(5)xxs)
(127)
(f(()() +
Σ
f( (
(128)
SEP( 1DM
(1 - -((()) +
Σ
(-f(T-1(SS))
(129)
SEP(CL..AD)(0)))
(Tr (p) Tm (11 (1- f(0)) +
To
Σ
(-f(S))xs)
(130)
(EP((I....)))(00)
Tm ((P(0))) +
Σ
f(S)xs)
(131)
= f( (()=)(
Σ
f(( (()=)s
(132)
-(())x +
Σ
(()-1
(133)
(EP((I...))))
= (1 - -(0)))x
Σ
-
(134)
Lemma D.6 (Commutability of t, and T&). Let p E Z²" be an MP vector, v E B. and é S (1....,kk). Then (To (p) (To (p).
Proof. We begin by noting that T6 To, i Φb Now, to prove the statement of the lemma, it suffices to show (Tu To,) (Ta, (p)) If v = or or & o, then either Tμ = Id. or To, = Id., and the statement is clearly true. We now consider the case where = 1 and i E o. Under the functional perspective of the statement is equivalent to showing T, (p o To,) = (T, o p) a Te., where p _ - Z. which holds by associativity of function composition. The statement also follows from Lemmas D.2 and D.4,
ToL where Te. = T() if E and To. Td. if
30

---

Published as a conference paper at ICLR 2025
(To o TTW
=T
Σ
J(SU
E
(-f()))xs)
(135)
SEP((I...)100))
SEP BJ(E
(((()) f(OU x
Σ
Σ
(-f()))xs)
(136)
(EP(L)...N000000 To (f(0)x
SEP (FEE))
Σ
((S)xs +
E
((S)xs)
(137)
SEP(O...ANNNNOO
SEP SEP KFHE)
(1 (0)))
Σ
(-f(S)))s
Σ
(-f(S))xs
(138)
SEP(( (OD)
SEP (HE)
(1 - (f(0) + f(O (()()))
Σ
+ ((SU
E
(-(-(())))xs (139)
SEP((L...
SEP (H(()
(1 -11 f(U (())))x
Σ
(-f(s) f(SU +
Σ
f(S)xs
(140)
SEP( MMM)
(To, (p)
TTu (11 (()) +
Σ
(-f(8))xs)
(141)
=Th (p(())x +
Σ
P((S)xs)
(142)
= -P(0 +
Σ
i(()xxs +
Σ
((())ss)
(143)
SEP((I.....T)) B)CDN((
SEP (F(())
= -('(0) + (((0 (it))xo
Σ
(f + ((SU
Σ
(-f
(144)
SEP((....AA)1
((1-f(0)) (-1- (-1-))))))() (()
+
Σ
((-(()))( +
Σ
(--f(S)))x
SEP(H)....
(145)
= (1 - f(0 - f(0 (i)))xo
Σ
(-f(s) j(S (()))x++ +
Σ
N(S)s
(146)
SEP(()..... MNOX)
(PP(II...R)16)))
Lemma D.7 (Rearrangement Tr and Tq). Let p E 2² be an MP vector & C (1....,
k}, and
(1,...,k) {1,..., k) be a bijection. Then (To Tx-1)(p)) (Ta-1 (p()))
31

---

Published as a conference paper at ICLR 2025
Proof. We begin by noting that T6 Tá: oTT where Tà, = [() if c. and Te. Id. Now, to prove the statement of the lemma, it suffices to show (To: Tp) (Tx-1 (d)) (p).
If i & p, then (i) & (Ø). Té. Id., Ta())a(a Id., and the statement is clearly true. We now consider the where E Φ, which implies (i) E π (().
(Th, o TT)
Σ
f(T(S))xs)
= =To.
(147)
SEP((I....))
= Too
Σ
P(S)xs)
(148)
SEP(IT......)
Σ
((S
Σ
(-f(S))
(149)
SEP (((A)))))))
Σ
(f(T(S)) f +
Σ
(-f(7(S)))x (150)
E
(
Σ
(-f(T(S)))xs
9N6))
SEP(L (V(())....)))))
(151)
(Ta 1 (d())(n))) (p)
Σ
(f(S) + (rs
Σ
(-f(s))xs)
= Tx--1
((7())...(((((())
(152)
-
Σ
P(S)xs +
Σ
F(S)xs)
(153)
SEP MMARH
SEP(II....AAAAE
Σ
((((s)) +
Σ
f(((S))
(154)
()
SEP(()...,)M((OO))
Σ
((((S))xs++
Σ
((((S))
(155)
SEP((
SEP AVOD
Σ
Σ
(-f(
(EP(()....))1)))))
(156)
Equation 156 holds since & - T(i) & (S) and e S = +() E TSS).
Theorem D.1 (Inverse NPN transformation). Let 7 Tu o Tx To be an NPN transformation. Then T-! To - TT())-
Proof.
r T OTx TT,
(157)
= T 0 TT- 0 OT
(Boolean algebra)
(158)
TΦ 0 Tv T1
(Lemma D.5)
(159)
Tv OT 0 -1
(Lemma D.6)
(160)
T, 0T,-1 0 (x(
(Lemma D.7)
(161)
n
32

---

Published as a conference paper at ICLR 2025
D.2 RELATING NPN AND EQUIVALENCE CLASSES
Lemma D.8. Let p, q E 82t be MPs of RFs, and p' [p)a. Then
Vo B² ((()) (p'(x)) o (g(x)) pl p((x))
(162)
Proof. If q(x) = 0, then 0 = 0. ((x) 1, then (x)())) = o (z))
Lemma D.9. Let p.p. E z²" mrs of brs p' E [pl. and q' E [g].- Then
Vx E B (1 (r(xz) p'())) + (f(()) (<)) = o (r(xz) ((()) + f(x)) (((x)))
(163)
where F(x) = 1 r()().
Proof. The expression is akin 2-1 multiplexer, where acts as a select line. If r(r)) then (a)()) a (d'())) If rx)) I, then (p'())) o (p'(x))
Lemma D.10 (Relating ~o and ). Let p, q -² be MPs of BFs such that p To, (q), where 6 = {i} S f1....,. k}, and q' E [9.. Then To. (q') E (p).
Proof.
p= To. (g) + Vx B p(x)) = (1 2.)9a (x) + 2.40, (x))
(164)
Vo E B²
(((x) = (1 2,)o (x)) + 2: (1 (z))
(q' E [q]=)
(165)
Vo E B&
(p(x) = ((1 z;)g (x)) + σ (a:4k, (z))
(Lemma D.8)
(166)
Var E BB
(p(x)) ((1 - =:)a's (x)  (a:)
(Lemma D.9)
(167)
Vo E A²
(a(p(z)) = o(1 ((-11x))...)
z.)d (x) + 2. (x))
(168)
To: (d)
(169)
Lemma D.11 (Relating ~o and TT)) Let p. E Z² be MPs of BFs such that p T (g). where T: kk. (1,.... k) is a bijection, and q' E [g).. Then Tu (q') E (p)..
Proof.
== P= (q) + Vo B (p(x) (p(z)= q(x (x))
(170)
Vo Bk (p(z) o (T (T+
(q' (gle)
(171)
Vo E B² (a(p(=)) = (d
(172)
Pr Tx(4)
(173)
33

---

Published as a conference paper at ICLR 2025
Lemma D.12 (Relating ~a and Ty). p, Z²" be Mrs of hrs such that p (q) where and q' E (g... Then Tr(q') [plo-
Proof.
p -v(9)) + Vo B ((()) (p(x)
g(x))
(174)
Va B* (p(x) (d'(z)))
(q' (gla)
(175)
Vo Bh (p(x) (1 y((x:))
(176)
Vo (o(p(z)) (l o (x))
(177)
- (g))
(178)
To prove Equation 176 holds, suffices consider the two cases where ((xx) and (((x) < 0. If
(a) 0, then ((x) and p(x) 0. Since (x) E Z, - q' (x) I 0 and hence a (1 q (x))
0 p(x). If (x) < 0, then ((x) 0 and p(x) 1. Since of (x) Z. 1 g'(x) and hence a(1 (x))) = = p(x))
Theorem D.2 (NPN transformations between equivalence classes). Let p. q E 2² be MPs of nts such that p TQq), where Tv Tx T is an Nww transformation, and q' Iglo. Then r(q') E (p).-
Proof. We begin by noting that T3 Tox To.. where Té. T()) if E d, and To. Id. if i Φ. Let 91 (g), 42 Tx (41), and qs = (g())) Then
91 (q)))) = q'
(Lemma D.10)
(179)
~ Tx 91) = Tx (T(()())) = 12
(Lemma D.11)
(180)
43 ~ Tu (4)) = (T((T(TT(qq)) = 433
(Lemma D.12)
(181)
Since, p 43 p ~o (Tv o Tx (p)) =(g)).
34

---

Published as a conference paper at ICLR 2025
D.3 COMPUTING MMPs WITH NPN TRANSFORMATIONS
Definition D.5 (PN-invariant criterion). Let E Z² be an MP, V E IB and π [l....,k}
{l....,k) be bijection. A criterion vector E -² is PN-invariant if ||e O pppi = ||o O (To o Tx) (p))l-
(182)
Lemma D.13 (Uniform criterion is PN-invariant). Let lo E No. ck is PN-invariant.
Proof.
c Jeni
pll
(f(0)x
Σ
{())s))1
(183)
SEP( KD110
f(S)xs
(184)
SEP( ()M
Σ
[f(S)
(185)
SEP(() ())())
Let (a similar argument can be used to prove the where 0, and hence Tv Id.).
| O (Tv Tx (p))l
Ck
uni
① (11 f(0))x
Σ
(-f( (5)) 1|
(186)
SEP(( ())(0))
Σ
(5))x=
(187)
SEP(( R))((0}
Σ
- f-
(188)
SEP(()..... (D)
[(S)
(189)
SEP(( ())())
Lemma D.14 (Degree criterion is PN-invariant). Let k E No. Cg
deg
is PN-invariant.
Proof.
|c deg ② pll1
|| |oger ④ (f(0)xo +
Σ
f(S)xs)
(190)
(EP((I....))))
Σ
(IS) f(S))xs
(191)
SEP( (M))
Σ
|||| f(S)
(192)
SEP((I..... ())
Let (a similar argument can be used to prove the case where v = 0, and hence To = Id.).
10 deg 2 (Tv o Tx (p)ll
ck
deg
o (1-f(00)
+
Σ
(-f (S))xs)
(193)
Σ
(-15) ((S)))xs
(194)
SEP((1.....))) k)){())
Σ
|-| f(m -(())
(195)
SEP( ())()))
= Σ
||| f(S)
(196)
SEP(().....)))
35

---

Published as a conference paper at ICLR 2025
Theorem D.3 (Computing MMPS with NPN transformations under PN-invariant criterions). Let Z²" be a PN-invariant criterion, p, E Z²" be MPs of nFx such that p = (Tu Tx (q)( and q' [q) be an MMP with respect to criterion c. Then p' = (Tv o (x) E [pl is an MMP with respect to criterion
Proof. If qf an MMP with respect to criterion c, then
E arg min C(r) arg min rElg.
(197)
rE[g,,
Moreover, since e is PN-invariant, we have
|c @ d'll = Ico (Tv T = 1 p =
(198)
and by Theorem D.2 p' [plo- We claim p' arg min 0 rll1.
Suppose, for sake of contradiction, p' & arg min ||e @ 1 < a. Let q = (-= -. (p) = (Tp o Tx=11 (()). where the second equality holds due to Theorem D.I. Following Theorem D.2, q E ag.. and since is PN-invariant, we have
||e rll1, then there exists P E [plo such that
| p 11 ||c (Tp -x-1 (+) |ce e Ill a,
(199)
which is contradiction, as we assumed d' arg elg) ||e rrl..
36

---

Published as a conference paper at ICLR 2025
Algorithm 1: MP- and MMP-hased technology mapping with NPN classes
Input: BN Gy = (V, E) and vertex labeling function R V F, where F U B²" Output: Functions & 2i V +F' where F U x² Function :techMapNPN (Gr, Vt))
Initialize v. 0 and v t 0
for k + 0 to do
C' CppnCasssi (GF, 15,, k)
// Compute NPN classes
for each NPN class Oxy = ( | (Ky)) C do
Kp - ttToMM (Kz)
11 Compute MP of NPN canonical form
for each unique permuted phase assignment subset
Sx(0) {(f,(""" 11 Cxy 5- = To T (x()) do
if S ( |{s
= then
p r 7- (Kip)
p' + mpToMMP (p)
// Compute MMP of p
V t vi U U(l.p)) ())()== f
V/ - -e U((e,'')) z (bz(1) = -f}
else
Jxw + ((()((pp)) Kp
7:00 mpToMMP (Kip ((())) Compute MMP once for p sharing Tx(o)
15
for
(f, T -1 STi0) do p + (Tr T ( (n(()
16
p' t (To O (K(p Tx) Tx()))
4 t w (((,,) EV x 2 |V=(D) = f}
V - vp U((v,p') E 2 (b)(() = f}
19
20
end
21
end
end
end
24
end
25
return J T1
D.4 OBJECTIVE-AWARE OPTIMIZATION ALGORITIIM USING NPN CLASSES
We propose an appimization-obectivve--ee
NPN classification algorithm for and MMP-based technology mapping. The algorithm firstly classifies functions into their respective NPN equivalence classes by computing canonical forms and corresponding NPN transformations. The canonical forms are then mapped to their MP representations. Next, each equivalence class is partitioned into subsets that share permuted phase assignments Tz(σ). The "permuted phase assignment NPN canonical forms" Tates of each subset are then minimized with respect to a PN-invariant criterion. Finally, the MPs and Kop
MMPs of other members of the subset are computed following Theorem D.3. See Algorithm
Remark D.6 (Correctness for Algorithm 1). The ordering of the cache hierarchy, and specifically the order in which the inverse NPN transformation is computed. is correct following Theorem D.1. Furthermore, the statement that all MMPs indeed MMPs according to criterion c or dee follows from Lemma D.13, Lemma D. 4,, and Theorem D.3.
Remark D.7 (Time complexity of NeN classification). Let m denote the number of unique k-input BFs being classified. The NPN classification algorithm we used for our experimental results to compute NPN canonical forms and transformations requires time 0(m2* k) + e, where 0(m2* k) is due to computing signature vector for unique functions, and e denotes exhaustive enumeration time (which requires checking at most 2 k! NPN transformations per unique BE) (Zhou et al., 2020). Letting 0(m2++1k)) have time O(m2* k m22+1k1) k!). We note that asymptotic analysis
37

---

Published as a conference paper at ICLR 2025
does not provide significant insight here, as for practical reasons of synthesis K - 10. Heuristics, symmetries, low-level implementations, and multi-level caches (Petkovska et al., 2016; Zhou et al., 2020) make NPN classification relatively fast in comparison to the aggregate collection of ToMM and mp ToMPP subproblems we aim to solve.
Remark D.8 (Time complexity of Algorithm 1). Let Gr,, (V, and ,F, + Fy. where Fy - k= B² be the K-LUT Boolean network (BN) and vertex labeling function provided as input to Algorithm I, respectively. Let Va = {u E V indegree(u) = k3 be the set vertices with g 8²* Do Vi (1v, (v) = be the set of k-input BFs in GF,,
inputs in CF,, ,
and K [obr, [V&]] = { E T ah E ,,, [VA] (s<(h) = =) be the set of k-input NPN canonical forms in Gyy,
We now define the quantities of interest for our analysis of time complexity. Let
v = |&l E No denote the number of k-input Brs in Gy,-
bb,, [V]]] E No denote the number of unique k-input Brs in Gry,
[ [Vi]]] E No denote the number of NPN equivalence classes on the set of k-input Bis
in G Fy, and
No denote the number of permuted phase assignment subsets on the of k-input BFs in Gry-
Next, we determine bounds on these quantities.
I v, as does not have an upper bound.
0 Σ m < 2 as there are 22* k-input nrs.
m. The upper bound occurs when all m unique BFs fall into different npn equivalence classes. The lower bound requires some analysis. Recall from Remark D.2, there are 2 NPN transformations on k-input Brs. Moreover, let f E st,, [V&]. Now, suppose that applying the 2 kt NPN transformations f returns 2*+ k!! unique BIs. Then the size of the NeN equivalence class of f is [[f]NP = 2 Hence, if [f] NNN C Φ [V&]. the NPN class accounts for 2 of the m unique BEs in ,i,, [V&]. Consequently, if this happens for all BBs in thy [Vx], then the number of NPN equivalence classes on u [V[] would be 24-1k!"
m 26 S S m and e S 8. These bounds require some analysis. Let Ciyy = ((f f
T (kz)), where f, ,,, [Vu], be an NPN equivalence class with NPN canonical form Ky. Then permuted phase assignment subset S*(0) {(f, ((f, Ceyy |-- Tu Tx 1 Tn()) is subset of the NPN equivalence class that shares the same permuted phase assignment (()) C [L....,k]. Notice, that there are 2 possible permuted phase assignments. For the lower bound 2H S 8, suppose |Cz,1 2 Then the NPN class will be partitioned into 2* permuted
2* 2k. Consequently, if this happens for all Brs in , [V... then the number of permuted phase assignment subsets on viF,[Vá, would be m For the upper bound S m. this occurs when all m unique Brs fall into different permuted phase assignment subsets. Finally, since permuted phase assignment subsets are subsets of NPN equivalence classes, we have that e S s.
phase assignment subsets, each of size 2*
zE!
Before continuing with the time complexity, we note some corollaries of the analysis performed. Note that all BFs in an NPN equivalence class share an NPN canonical form Ki, and that for all functions in the class Algorithm I computes ToMP only once. Hence, since an NPN equivalence class can have up to 2 kc! members, Algorithm will reduce the number calls to TtTMMP by up to 2 k! 1 for the class.
Similarly, note that all Brs in a permuted phase assignment subset of an NPN class share a "permuted phase assignment NPN canonical form" kip = T (Kp)), and that for all functions in the subset Algorithm computes mpToMMs only once. Hence, since permuted phase assignment subsets can have up to 2h! members, Algorithm will reduce the number of calls to mpToMMP by up to 2 for the subset.
We now continue with the time complexity of Algorithm 1. Firstly, the algorithm computes NPN canonical forms and transformations for each of the functions in rhy,, (Vk), requiring time O(m2* k-
38

---

Published as a conference paper at ICLR 2025
m!)+ (see Remark D.7). A cache key (the hexadecimal string representation of function's truth table) must then be computed per vertex, requiring time v 02*() ToMP is then computed for each spn canonical form, requiring time O(2*k) (using the algorithm from Gavier et al. (2023)). Next, at most k input negations TΦ, are performed to compute each of the 8 permuted phase assignment NPN canonical forms, requiring time s k- (22) (see Remark D.5). mpToMMP is then computed for each of the permuted phase assignment NeN canonical forms, requiring time s 200k2*)) (see Remark C.2). Finally, for each of the m unique BFs in vir [V&]] an input permutation Ts and output negation Tи are computed, requiring time m -(*)) (see Remark D.5). The time complexity of Algorithm for a K-LUT BN therefore:
TyPN classes ()) 00m2mKKKK K +22 K!) + u. O(2*)+
+ 1c.00(2KA)) K) sK 0(2 + 2(K2*) + m 0(2k)
(200)
= =0mm +1 K! + v2 + c2 K + s2 K + m2* + x2
(201)
= =0 +1 K! + u2 + 22 K) + 220(k2))
(202)
-((2mK) u =((2mk) cK)2 ) (k2**)
(203)
+ (k2
(204)
Remark D.9 (Time complexity of the Naive algorithm from 4.2). We follow the notation introduced
in Remark D.8. The Naive algorithm computes TMM and ToMMP per vertex in Vi. requiring
time v O22hk) (using the algorithm from Gavier et al. (2023)) and v 20(x2*) (see Remark C.2), respectively. Hence, the time complexity of the Naive algorithm for a K-LUT BN is:
Naive (K) = u 0(2
K K) + (k2())))
(205)
= =0((uK)2**+ + kk
(206)
Remark D.10 (Time complexity of the Cached algorithm from 4.2). We follow the notation introduced in Remark D.8. The Cached algorithm computes a cache key (the hexadecimal string representation of function's truth table) per vertex in Ve, requiring time v. O(2²). It then computes ttToMP and mpToMMP per unique function in &.,, [V+], requiring time m O(2*k) (using the
algorithm from Gavier et al. (2023)) and m (k(22)) (see Remark C.2), respectively. Hence, the time complexity of the Cached algorithm for K-LUT BN is:
TCached (K) = v 0(2*) + m O(2* K) + m20(k2*)
(207)
= =0 + m2 K) + (Kk2)
(208)
10((v+mK))) +
+ m20(k2
(209)
Remark D.11 (Additional space used by the Naive and Cached algorithms from 4.2 and Algorithm 1).
We follow the notation introduced in Remark D.8. Firstly, note that storing truth table requires space (2²)), and storing an MP/MMP with coefficients in {-2k-1,._ ... 2h-13 requires space (lk:2)).
Furthermore, storing Tn requires space O log k) from storing sequence of k unique integers in (0,1.....kk k- - 1}. storing Ty requires space ((k) from storing which inputs are to be negated, and storing 7u requires space ((1) from storing whether the output is to be negated. The Naive algorithm requires no additional space. The Cached algorithm requires m O(K2 additional space for storing the MP/MMP cache of unique functions. Lastly, Algorithm 1 requires m O(K2) additional space for NPN classification, then m O(K log K) + c. (K22*) + s O(K2*) additional space for the NPN transformations of unique functions, the top-level cache of NpN canonical forms, and the second-level cache of permuted phase assignment subset NPN canonical forms, respectively.
Remark D. (Comparison of the Naive and Cached algorithms from 4.2 and Algorithm 1). We follow the notation introduced in Remark D.8. For the set of k-input BFs of K-LUT BN, Naive requires calls to t ToMMMP and v calls to MoMMMMP. Cached requires m S calls to ToMP and m S v calls to TpTMMMP. A calls to mpToMMP For practical reasons of synthesis, K S 10 (as many operations and structures grow exponentially in time and space). Consequently, for fixed K S 10. as the number of vertices in a BN increases, we expect NPN classes and permuted phase assignment subsets to become more densely populated, meaning s - Ext and c - ş increasing the benefits of Algorithm 1, See Appendix G.3 for empirical analysis of the quantities v, m, e and s.
m < 3 S m requires कानंşा < C S m calls to T and 2
m
ma
za
39

---

Published as a conference paper at ICLR 2025
D.5 RELATION TO EXISTING NPN CLASSIFICATION TECHNIQUES AND NPN INVARIANCE
(NPN) classification forms a well-establisher and extensively studied subfield within the broader domain of Boolean function (BB) classification (Sasao Butler, 2022). This interest in NPN classification is largely driven by its utility in areas such as logic synthesis, technology mapping, and logic verification (Hinsherger & Kolla, 1998). In modern logic synthesis tools, NPN classification is commonly used in rewriting algorithms, which optimize technology- independent representations of BNs (Mishchenko et al., 2006). Rewriting for And-Inverter Graphs (AIGs) typically involves precomputing a set of optimized structures for each k-input NPN canonical form and storing them within a hash lookup table. Doing this for k V is common today and computationally tractable (Li et al., 2024). However, for k = 5 and lc 6 there are 666, 126 and 2.0 x 10a4 NPN equivalence classes, respectively, meaning both the time to compute and the space to store the optimized structures quickly becomes intractable (Sasao & Butler, 2022).
Permutation
In this paper, we discuss the optimization of NN representations of BNs. It was noted by Gavier al. (2023) that the number of layers in the layer-merged NN representation of BN, following the technology mapping sequence reviewed in $ 2.2 with K-LUT mapping, approximately depends on (K)) -! Consequently, applications that are latency critical would aim to use the largest value of K. From our preceding discussion, it is evident that an optimization algorithm which precomputes and stores the MMP for each k-input NPN or permuted-phase-ae intractable both in time and space. For this reason, we could not utilize NPN classification in the same way as existing rewriting algorithms based on precomputed hash lookup tables.
canonical form, k < K, would be
Instead of precomputing and storing MMPs, our solution involves computing them on-the-fly, Indeed, the straightforward approach would be to compute them per unique BF in the K-LUT BN. However, our goal was to utilize NPN equivalence to reduce the number of times we would need to solve the MMP optimization problem. Based the analysis in Remark D.8, it would be ideal if the MMP optimization problem could be solved once per NPN equivalence class (as opposed to once per permuted phase assignment subset of NPN equivalence class, which is what is done in Algorithm 1). Following the results presented in Appendix D.3 and specifically the proof of Theorem D.3, this would seem to require that the criterions used in the MMP optimization problem are NPN-invariant. In Lemma D.13 and Lemma D.14, we respectively proved that the uniform criterion c and the degree criterion cdeg the criterions we care about for compressing the NN representation of the BE, are PN-invariant. That is, they are invariant under input permutation and output negation transformations. Therefore, the final step to being NPN-invariant would be N-invariance, that is, invariance under input negation transformations. However, the following lemmas prove, the criterions c. and d that we interested in are not N-invariant.
Definition D.6 (N-invariant criterion). Let p E 2² be an MP and ø S (L...., kj. A criterion vector E 2 is N-invariant if
||c pll Ico
(210)
Lemma D.15 (Uniform criterion is not N-invariant). Let E No, 2 2. ct is not N-invariant.
Proof. Let = 11, 22.02=22) 2 E -² and ø = {1,2}, where 02h_22 2²2 22 zeros vector. Then (p) [0,0,0, 1, 02. = and
- is the all
||oa.i @ pll: = 3 1 1 ||ck @ Tp(p)111
(211)
Lemma D.16 (Degree criterion is not N-invariant). Let l E No. l 2 2. deg is not N-invariant.
Proof. Letp= = -,,
0,. 22]T= E t and ó = {1,2}, where 02h_2 22 E 2²" 22"-22
22 is the all
zeros vector. Then (p) [0,0,0, 1, 02 2=]T, and
| о opll 4 x 2 = واا Tx(l))l1
(212)
40

---

Published as a conference paper at ICLR 2025
Table 4: Cg de9 -weightd one-norms for MPs in 2², where 21, and T (Pox:)) = Poxse*
Pax16
P6x16
Pox68
Pox68
(P(66))))
|| 1
24
15
15
21
This is why Algorithm computes MMPs per permuted phase assignment NPN canonical form, since all members of the permuted phase assignment subset related by input permutation and output negation transformations, which do not change the MMP solution cost under the PN-invariant criterions e and ede To make these ideas concrete, conclude this discussion with example of what can go wrong when trying to share MMP solutions w.r.t. non-N-invariant criterions among functions that are related by input negation transformations.
Let faxi6 : B B be the BE with truth table Cx16. The MP representation of fox16 is
Pox16 F2, T3) 21 + 32 + 33
2x1
2x133 20233 3223
(213)
An representation of fox16 w.r.t. C3
deg is
Pox16 (2,, = x2
13
20 2x
2x2223
(214)
Let fax6s 3 B be the BE with truth table Cx68. The representation of foxes is
Pox6s (11, vz) ) = #1 + 21 + 2273 3214223.
(215)
An MMP representation of fox6s w.r.t. deg
( 12, x3) = -
x3 2x 222233
(216)
Let (1, and consider the input negation transformation Tg. Firstly, notice that (Pox16 To) (21, Poxse (T1, 12, xz). Next, we consider applying To to the MMP Poxie (x1, 22 2z),
(Poxce T (21, 22 F3)) = - + 3x, + 3z- + 3r3 2r1 201 2r203-
(217)
Following Theorem D.2, To (pxx16) [Poxsela- Therefore, To (Pbxis) could be an MMP Pox6s w.r.t. deg However, as Table shows, Th (Pox1s) does not have minimum solution cost within [Posssla Indeed, its cost under || 11--11,egee greater than both the found MMP Péx6s and the original MP Pox6s-
Consequently, after mapping from the MMP solution Pex15 using Tg. mpToMMP would need to be called again find an MMP of Poxss- However, this defeats the purpose of using NPN equivalence since we do not save call to the computationally expensive optimization procedure of mp MMP.
41

---

Published as a conference paper at ICLR 2025
E ARCHITECTURE-AWAR LOSSLESS OPTIMIZATION
Definition E.1 (Boolean network). A Boolean network (BN) G = (V, is a directed-acyclic graph (DAG), with vertex labeling function V + F, that represents an n-input, m--utput Boolean function (Br) B IB" + B Vertices with indegree zero are primary inputs (PI), and vertices with outdegree zero are primary outputs (PO). The labeling function & assigns single-output BF each non-PI vertex in the graph. A directed edge (u, v) E E exists if the output of u's BF is an input to v's BF. The depth of vertex to u. The depth of BN, denoted depth(G=)) is the maximum vertex depth in the BN.
V. denoted depth(v) E No. the length of the longest path from any PI
Remark E. (Types of NN optimization algorithms). Let G5= (V, E)) be the set of Pls. NN optimization algorithms select a subset of vertices M C V Vpr to represented as MMPs in the synthesized NN. We consider three types of NN optimization algorithms.
and Vpr denote
1. optNoner no vertices in the EN are represented as MMPs (M 9). This results in no compression and corresponds the SOTA NN-based technology mapping solution of Gavier et al. (2023).
optAll: all vertices in the bN are represented as MMPs (M V Vir).
a subset of vertices are selected to be represented as MMPs such that the 3. depth of the resulting layer-merged NN (see & 2.2) does not increase (M V VPt).
We propose a greedy algorithm for optMa intMaanntai nDepth that runs in time O(V(V + E)).
Definition E.2 (Path). A path of length n, denoted Pn, in EN G5 EV is finite sequence of ( 0;+1) E E).
vertices Pn = (Vo, fi,..., Un) E y=+1, where Vi E {0.....
Definition E.3 (Leeway). The leeway of vertex E V. denoted leeway((v) E No. in BN Gy = (V, F) defined as
leeway(v) depth(Gx)) depth(u) - -pp(())
(218)
where (p)(v) denotes the length of the longest path from any PO in GF. Lemma E.1 (Zero leeway indicates membership in longest path). Let Gy (V, E) be BN and V E be a vertex. Then leeway( ()) = -0 < v is on a longest path in Gy.
Proof. Recall that depth(v) is the length of the longest path from any PI to u and depth(Gr)) is
the maximum vertex depth. Let depth(v) + (p)(r) and P. (to....,, U.....,,................... Un) Vh+1 be a longest length path in G involving e. If leeway(v) = O, then depth((F=) = depth(v) + (v) n, which implies is on longest path in GF. If v is on longest path in GF, then depth(u) + (pl(v) = depth(Gxx), which implies leeway(s) 0.
Algorithm 2: Maintain depth Nn optimization algorithm (optMaintainDepth)
Input: bN G5= = (V, E), where F = _ Zz",, and function 8: V + No representing the difference in criterion between MP and MMP representations of V
Output: Vertices M C V selected to be represented as MMPs
Funciionnsoprtasittttiteeee (GF, 8)
G - augment (Gr, E outdegree = 0})
M E V outdeeeee = 0 A 5(v) > 0}
Consider POs
computeleeways (G'z)
for E V, in descending order w.r.t. 8, do (v.innegreee > 0) A (v. outdegree > 0) (v. (v.leeway > 0) A (8(x) > 0) then
// Greedy candidate selection
M - (u)
G' - augment (G', (n)) computeLeeways (G'))
end
10 end
return M
42

---

Published as a conference paper at ICLR 2025
Remark E.2 (Correctness for Algorithm 2 (ootMaintaainDepth)) We prove correctness for Algorithm 2 by showing that the subset of vertices M _ V it selects to be represented as MMPs do not cause the depth of the resulting layer-merged nn to increase.
Let Gy = E) be a BN. We denote the unmerged NN and layer-merged NN (see $ 2.2) of Gy resulting from synthesis N and N', respectively.
Let
pei = (vo, 11, .2.............................. 04, 1/41: Md-1: Ug) be a longest path in Gy, where d depth(Gx)), 20 is Pl, and 0d is PO. Then
(219)
Pa (Vo, h1, U1, f22 ...,...,,, h4, Vss h,+1, D++1, hd-1, Vd-1 ha, va) a longest path in N, where h; represent some hidden vertex of vi and
(220)
P = (vo, h1, h2,...,, ,,, h4+1, ha--: ha, va)
(221)
is a longest path in N Equation 220 holds since there are no vertices in G representing constant BF (constant or constant 0), as these vertices are combined with their successors by replacing successor
BFs with their positive or negative cofactor. Thus, each U/ E PCF i fl.....d}. will have least one hidden vertex h; as a predecessor in N.
We make two remarks about selecting vertices in G5 to be represented as MMP. Firstly, POs can always be represented as MMP: without increasing the depth of N'. Taking as an example, we see that adding a non-linearit at ea does not prevent the merging of any vertices since dia E P.N does not have ha+1 to merge with in N.
Secondly, note that if some intermediate vertex E PG=, (l...., d-...,-11 1). is selected to be represented as an MMP Gy, then since non-linearity must be applied at vs in N, v cannot be merged with h4+1- This would cause the length of P and in turn the depth of N', to increase by one. Consequently, any intermediate vertex V, that is, a vertex that is neither PI nor PO, can only be selected to be an MMP if does not appear on a longest path in Gy. After selecting such a v, the lengths of all paths in N' involving will increase by 1, which may prevent the selection of other vertices that could have been represented as MMPs
Since Algorithm only selects intermediate vertices with positive leeway and POs to be MMPs, following Lemma E. the depth of N' will not increase.
Algorithm 3: Computing leeways
Input: EN G5 = (V,
:uactiioncooppteeeeer
(Gr)
for d = depth, depthh deepth-l....... do
for u E .er.etetcesttttett (d) do
if v. outddgeee 0 then
v.1p1+00
// Longest path length (1p1)
else
V. v.lp1 + max [u. 1p1 E No (u, u) E E}) +
end
v. leeway & de..epth - v. depth - v. 1p1
end
10 end
Remark E.3. Algorithm 3 runs in time O(VV + [E.).
Remark E,4. Algorithm 4 runs in time O((E))
Remark E.5 (Runtime analysis for Algorithm 2). Algorithm 2 runs in time (VV The for-loop
(lines 4:10 of Algorithm 2) run (VV) times. Each iteration runs in time +())+(EE++O(1 E)
O(V + E). There may be O(V) additional vertices and edges added via augmentations. However, this does not affect the asymptotic runtime, as O((V + VV v)) O(V E).
Remark E.6 (Space complexity for Algorithm 2). Algorithm 2 runs in space O(V + E). Storing the
input graph requires space O(V + E), and O(V) additional space is used to store (i) vertices and edges added via augmentations, (ii) vertex properties such as leeway and (iii) the selected candidate set M C V.
43

---

Published as a conference paper at ICLR 2025
Algorithm 4: Augmenting with temporary vertex
Input: RN G (V, F)) and vertices A S V
Output: Augmented BN G (V','')
Function :augment (GF, A)
for U E A do
V' + U [tremp)
E' + (E {(u, E u VJ) {(u, (temp) (V1)2 (u, v) E E} U { (eemmps 2)}
Utemp depth t v. depth v.depth +- v. d.deph +1
end
return G' = (V', E')
2
2
Leeway to "push forward"
internal vertices while maintaining network deplh
T3
33
y2
b
Layer-merged NN depth
1
Leeways
02
22
V1
Hidden vertices
E3
MMP candidates
Ø 1
Depth maintained
C2
Z2
V
2s
8/1
Selected candidate
x3
82
Updated leeways
Hidden vertex
Figure 7: Architecture-awen neural network (NN) lossless compression algorithm that selects subset of vertices M to be represented as minimal multilinear polynomials (MMPs) while maintaining the layer-merged NN depth. Boolean network (BN) with three inputs (x;), two outputs (y:). and internal vertices (zi), where 23, 25 have leeway (Definition E.3) greater than zero. b, Output vertices always augmented with hidden vertices (red). An MMP candidate (yellow) is an internal vertex with positive leeway that is associated with a function whose multilinear polynomial (MP) can be minimized. Here assume minimization is with respect to the number of terms in the MP, and hence a 6 a + b ab can be minimized to a + b, whereas a 5 = ab and -a = 1- a cannot. e, MMP (blue), the newly introduced hidden vertex
Supposing 23 next selected to be represented (red) causes the leeway of 25 to drop to 0. Since no MMP candidates remain, the algorithm terminates with selection M {2a}. }. The synthesized from the in e functionally equivalent that of b, has the same depth, yet has 4 fewer neurons and 10 fewer connections (see Appendix H).
44

---

Published as a conference paper at ICLR 2025
F DIGITAL CIRCUITS AND AUTOMATA USED IN EXPERIMENTS
The technology mapping sequence discussed in 2.2, and the optimization techniques we propose, work for arbitrary Boolean networks (BNs). Hence, given specification of discrete graphical model, we can encode the model as a BN, then it can be provided as input to the optimized technology mapping sequence arrive an optimized NN representation of the In this section, we describe encoding techniques for, and instances of, the two discrete graphical models that were used in our experimental results; digital circuits and deterministic finite automata.
Digital circuits. Digital circuits specified in hardware description languages can be converted into BNs via a process known as technology independent synthesis (see Gavier et (2023)). We provide additional information and references for the four open-source digital circuits used in the experimental results of the main text.
uart is communications core that parses internal bus commands via Universal Asyn- chronous Transmittrt (UART) interface.
sha3 is cryptographic core implementing Secure Hash Algorithm (SHA-3) with an output length of 512 bits.
ecg" is cryptographic core implementing sealar multiplication of an element in the elliptic curve group.
aes? is cryptographic core implementing the encryption function of the Advanced En- cryption Standard (AES) symmetric-key algorithm with key length of 128 bits.
We also provide details on the digital circuits used in the extended results (see Appendix G.2).
add is 64-bit full adder.
alu is a 32-bit arithmetic logic unit implementing +, -, x, +, etc.
rand8 and rand12 are randomly generated re-input, n--utpuut look-up table (LUT) digital circuits, where n E {8, 12).
riscv" is RISC-V V 3-stage pipeline.
Deterministic finite automata. deterministic finite automaton (DFA) is a computational model with finite memory. Formally, it is a 5-tuple D (Q, E, qo; F), where
1. Q is a finite set called the states,
2. Σ is a finite set called the alphabet,
3. 8
Σ -
the transition function,
4. do E Q is the start state, and
5. S Q is the set of accept states (Sipser, 1996).
We now present a BN construction for an arbitrary DFA D E, 6, go, F)) using a one-hot encoding for states and symbols. Let Vpr = {4t, ...... Iqq U (o 02, .2, } } be the set of primary input vertices, Vro = { & .., {q be the set primary output vertices, and = = Vro be the set of vertices. Let Ay [(g [ Σl 8(g, o) d') be the preimage of g' E Vpo. Let E = {(u, 4') E Vps x Vpo 3(4,o) E A, (u = q V = r)} the set edges, and a + F be the labeling function with specification
('g')
V (o.))
(g
(222)
for all of E Vro (recall the labeling function assigns a single output BF to each non-PI vertex). Then, Gy (V, F)) with labeling function & is BN representation of DFA D. We that the resulting eN can be optimized using technology independent synthesis tools.
'https: hnttaa///ppacoesssoo///ooott///
45

---

Published as a conference paper at ICLR 2025
a.
1
b
a
a
3
2
(a) DEA Daoc.
(b) DFA Dondd
Figure 8: State diagrams of the DIAs used in the extended results.
We now provide details on the DEAs used in the extended results (see Appendix G.2).
aaa is the uN representation of a DEA Daas whose language is the set of all strings over the alphabet E = {a,b) containing the substring "aaa". The regular expression for this language is (a + ba""aaaaa + b)*. Formally, let Dasa (Q: Σ, 5, 0, F) be DFA, where
1. Q = {0, 2, is the set of states,
2. Σ {a, b} is the alphabet.
E Q is the start state,
= {3} is the set of accept states, and
transition function 5 Q x Σ - Q is specified in Figure 8a.
cmod5 (counter mod 5) is the BN representation of a DFA Demods whose language is the set of all strings over the alphabet Σ {a.b) b} containing either (i) m a's (increments). or (ii) suffix consisting of a b (reset) followed by a's (increments). where m = 0 (mod 5). The regular expression for this language is (a5)* ) + + b(a)(" Formally, let Dands (Q, Σ, 8, 0, F) be DFA, where
1. Q {0, 1, 3, 4} is the set of states,
{a, b} the alphabet,
E Q the start state,
F = {0) is the set of accept states, and
5. transition function 8 Q x Σ + Q is specified in Figure 8b.
46

---

Published as a conference paper at ICLR 2025
G EXTENDED RESULTS
G.1 ACCELERATING MP-BASED TECHNOLOGY MAPPING WITH NPN CLASSIFICATION
uart (1,820)
sha3 (31,146)
ecg (105.713)
aes (128.863)
Mapping time (s)
10
10
10"
2x10+-
10"
10'
Ex101
10%
K 12
K
K
Naive
Cached
NPN classes
Figure 9: Accelerating MP- (multilinear polynomial) based technology mapping (and in turn NN- based technology mapping) with NPN classification. MP-based technology mapping takes a Boolean network (BN) with vertices associated with k-input truth tables. 1 S S K, and computes the functionally equivalent MP for each vertex. Naive (blue) computes the per vertex in the BN, while Cached (red) computes them per unique function. NPW classes (green) implements the proposed NPN classification algorithm, computing MPs via NPN canonical forms and transformations, NPV classes achieves consistent speedups when the overhead of computing NPN canonical forms and transformations is insignificant that of computing MPs. Lines and error bars denote the sample mean and standard deviation over trials. Logic gate counts, following technology independent synthesis, shown parentheses.
G.2 RESULTS ON ADDITIONAL BOOLEAN NETWORKS
aaa (13)
cmod5 (16)
cnod5
Mapping tmee (9)
(15)
(16)
% Connections
drg
Depth
Naive
Cached
NPN ciasses
(a) Reduction in connections (blue) and neurons (red) relative to the unmerged NN by optimizing all sub-NNs with the proposed apttAl1 algorithm. crods
(b) Mapping time MP-based technology mapping.
aaa
a8a
cmods
(13)
Optimization time (6)
10
4x
Exit
% Connections
% Neurans
Depth
Naive
Cached
NPN clesses
+
Arg
(c) Reduction in connections and neurons relative to the layer-merged by optimizing subset sub- NNs selected by the proposed optMainn int a anttainDethii nDepph algorithm. The size of the layer-merged NN able to be reduced without increasing its depth.
(d) Mapping time for MP- and MMP-based technology mapping w.r.t. uniform (c ""i and degree deg criterions.
Figure 10: NN lossless optimization and mapping acceleration results for DEA BNs aaa and cmod5. NN lossless optimization with respect to the uniform (c"mi) and degree (cdeg) criterions for MMPs for unmerged (a) and layer-merged (c) NNs. NN depths are shown gold. Mapping time for MP- base technology mapping (b) and and MMP-based technology mapping (d). See 4.2 for details on the different methods (Naive, Cached, NPN classes). Lines and error bars denote the sample mean and standard deviation
trials. Logic gate counts, following the DEA BN construction and technology independent synthesis, are shown in parentheses.
47

---

Published as a conference paper at ICLR 2025
add (874)
alu (12.024)
randB
rand12 12
6408, 400, 4091
16,300, 6.304. 6,314)
113
100 100
100 100
100 100
100
120
22
300 23L
18
10
Connections
Neurons
deg
Depth
(a) Reduction in connections (blue) and neurons (red) relative to the unmerged by optimizing all sub-NNs with the proposed optAll algorithm. add
rand8 (408, 406)
rand12 (8,508, 6,304, 6,314)
(874)
(12,024)
100 110
100
40
155
12
10
512
10
K
% Connections
% Neurons
2
dley
Depth
(b) Reduction connections and neurons relative the layer-merged by optimizing a subset of sub-NNs selected by the proposed optMaint ainDepth algorithm. The size of the layer-merger NN is able to be reduced without increasing its depth.
NN lossless optimization with respect to the uniform (c"".) and degree (c criterions for MMP.. NN depths shown in gold. Logic gate counts, following technology independent synthesis, are shown in parentheses. For rand& and rand12 2, lines and error bars denote the sample mean and standard deviation across different circuits.
Figure 11:
add
alu (12.024)
rand8
rand
8,308, 6,314)
Mapping time (s)
Naive
Cached
NPN classes
(a) Mapping time MP-hased technology mapping.
add (574)
alu
rand8 (406, 400 409)
rand12 (8,208, 6,304, 6,314)
Optimization (s)
(12.024)
10'
10"
10
8
Naive
Cached
NPN classes
dog
(b) Mapping time for MP- and MMP-based technology mapping w.r.t. the uniform (c" and degree (e criterions.
Figure 12: Accelerating and MMP-hased technology mapping with classification. Naive (blue) computes the MP (a) or MP and MMP (b) per vertex in the BN, while Cached (red) computes them per unique function. NPN classes (green) implements the proposed NPN classification algorithm. For add and alu, lines and error bars denote the sample mean and standard deviation over 3 trials. For rand8 and rand12, they denote sample mean and standard deviation across 3 different BNs with trials each. Logic gate counts, following technology independent synthesis, are shown in parentheses.
48

---

Published as a conference paper at ICLR 2025
riscv (415,047)
riscy (415,947)
Unrmered NN reduct
Layw me ged reduction
map
MP. map
Mapping time
7.0
% Connections % Neurons
2013
deg
Depth
Cacchdd
NPN classes
C
Figure 13: NN lossless optimization and mapping acceleration results for riscv. NN lossless optimization w.r.t. the uniform (c"mh) and degree (cdog) criterions for MMPs for unmerged (far left) and layer-merged (mid left) NNs, NN depths are shown in gold. Mapping time for MP-based technology mapping (mid right) and MP- and MMP- based technology mapping w.r.t. the uniform (c"*h) and degree (c criterions (far right). Lines and error bars denote the sample mean and standard deviation over 3 trials. Logic gate count, following technology independent synthesis, is shown in parentheses.
We present additional results on three different classes of digital circuit ANs (see Figure 11, Figure 12, and Figure 13), as well as results on DFA BNs (see Figure 10), using the same experimental setting as in the main text (see $ 4). We provide details on the digital circuits and automata in Appendix F, and summarize our findings below.
Rell-known/Arithmette circuits (add & alu) In comparison to the main results, we achieve new best under the denth-constrained NN compression setting with add, reducing the connections and neurons in the layer-merged NN by 60% and 30%, respectively. When compressing the unmerged Nn of add and a lu, we observe that as K increases so does the relative reduction in size (also observed for uart and ecg in the main results). As for mapping time, add is too small to see benefits with NPN classes. While alu is also relatively small, we see a speedup in mapping time with NPx classes.
Arbitrary/Random circuits (rand8 rand12) We achieve considerable compression in NN size for randß and rand12. 1. We also find that the NPv classes and Cached algorithms are not useful for these BN. for large K. This is because as K increases, Brs are equally likely to occur BN, the likelihood of having two BFs in the same NPN class, or in the same BN, tends to zero (see Appendix G.3). We note that the applications in the Broader Impacts statement (see Appendix I) mainly involve non-random BNs, for which our experiments have demonstrated the value of NPN classes.
Large circuit/ / Core (risev) riscv is 3.3 times larger than aes (the largest BN we reported in the main results). For riscv, our techniques were able to reduce connections and neurons by up to 40% and 10%, respectively, without a depth constraint, and by up to 40% and -1 11, respectively, in the cepth-constrained setting (the increase in neurons is justified by the fn-oorm relaxation, see Appendix C.1). We also observed mean speedup using NPW classes over the Cached algorithm.
Deterministic finite automata (aaa & cmod5) Following the BN construction for DEAs discussed in Appendix F, the BNs for Dase and D Demoas have 6 and 7 primary input vertices, respectively. Consequently, in Figure 10, we limit K-LUT mapping to K S 6 and K < < for the BNs aaa and cmod5, respectively. Since the maximum number of inputs to any BF in aaa and cmod5 is 4 and 7, respectively, K-LUT mapping applied to aaa with K E {4, 5, 6) results in the same K-LUT This is why we observe the same reduction results for aaa with K (4,5,6) in Figure 10a and Figure 10c. Moreover, we see that the resulting NN representations for aaa and cmod5 with K E 5,,6,) and K 7, respectively, have only two layers. In these cases, the unmerged and layer-merged NNs are identical since inter-depth composition cannot be applied (see $ 2.2). Even though these BNs are significantly smaller than the digital circuit BNs we examine, we are still able to achieve substantial compression; observing a reduction in connections and neurons of 40% and 12%, respectively, for aaa with K (4, 5,6) under the ddeg criterion (reducing connections from 62 to 37, and neurons from 27 to 24), and reduction in connections and neurons of 85% and 64%, respectively, for cmod5 with K- = 7 under the edey criterion (reducing connections from 407 to 60, and neurons from 94 to 34). As for mapping time, all K K-LUT BNs of aaa and cmod5 have < 19 BE.. Hence, these BNs are too small to see benefits from the proposed NPN classification algorithm.
49

---

Published as a conference paper at ICLR 2025
G.3
EMPIRICAL ANALYSIS OF NPN CLASSIFICATION
Vertices
Functions
10
NPN classes
(()) subsets
10
Count
10
10
10%
2
7 9 11
k K
Empirical analysis of the quantities introduced in Remark D.8 for the K-LUT Boolean network (BN) of aes with K 11. The number of vertices (blue), unique functions (red), NPN classes (gold) and permuted phase assignment subsets (green) in the BN are shown for 0 < k < K.
Figure 14:
We empirically examine Remark 1.12 for the largest eircuit (aes) and largest K (K- 11) presented in the main text for MP- and MMP-based technology mapping. Since there are 2 BFs and the lower 22
bound on the number of NPN classes is 24+ig! (Sasao & Butler, 2022), as k tends to infinity the number of NPN classes will approach the number of unique functions. Consequently, the Cached algorithm from $ 4.2 and the NPN classes algorithm (i.e., Algorithm 1) would require the same number of calls TEToMP and MMMMMMP. However, K generally limited be around 10 due the exponential runtime and space requirements of synthesis operations and data structures, respectively. Hence, as mentioned in Remark D.12, we can make use of NPN equivalence classes to speed up mapping time; statement which was validated by our empirical results. In Figure 14, we observe both ends of the bounds presented in Remark D.12 for the number of NPN classes and the number of permuted phase assignment subsets. While for k = 5 there are 18 unique functions, 4 NPN classes and 6 permuted phase assignment subsets, for & = 8, there are 1,096 unique functions yet only NPN classes and 25 permuted phase assignment subsets. Thus, the Cached algorithm requires 1,096 calls t ToMP and mpT oMMP, whereas the NPN classes algorithm requires 11 calls to t ToMP and 25 calls to TOMMMMP. This explains the observed speedup of 5.9x in Figure 6.
50

---

Published as a conference paper at ICLR 2025
H SYNTHESIZED NEURAL NETWORKS FOR FIGURE 7
See Figure 15 and Figure 16.
Figure 15: Layer-merged neural network (NN) for panel b of Figure 7. The NN has 24 neurons, 38 connections, and depth 5.
Figure 16: Layer-merged neural network (NN) for panel c of Figure 7. The optMaintainDepl h NN compression algorithm was applied under the uniform criterion. The NN has 20 neurons, 28 connections, and depth of 5.
51

---

Published as a conference paper at ICLR 2025
1 BROADER IMPACTS
In this work, we propose a novel lossless optimization technique for neural network (NN) represen- tations of Boolean networks (BNs) and an algorithm for accelerating the conversion from BN to NN. Here, we briefly discuss the positive impacts our results suggest for two important domains: BN (in particular, digital eircuit) simulation and neurosymbolic artificial intelligence (AI).
Registerrtransfer level (RIL) simulation is used to achieve functional verification of digital circuits (Tan & Rosdi, 2014). Although the use of GPUs for RIL simulation was proposed as early as 2011 (Qian & Deng, 201 1), due to the continued developments in GPU hardware, modern machine learning frameworks, and the proliferation of GPUs in data centers, there has been a recent call for accelerating RTI simulation on parallel processing hardware platforms (Zhang et al., 2020). This has resulted in GPU RTL simulation tools (Lin et al., 2022) and their integration into more advanced functional verification techniques, such as hardware fuzzing (Lin et al., 2023). NN-based technology mapping was recently applied in a GPU RTL simulation methodology, leveraging batched stimulus to parallelize the evaluation of test cases (Gavier et al., 2023). Our proposed Nn optimization technique reduces the memory footprint of the resulting NN, meaning more test cases can be batched in parallel and throughput can be further increased. Furthermore, mapping time is crucial for the adoption of NN-based simulation methodologies in practice, as time delays are expensive in the interative design flow of digital circuits. Our proposed techniques are also applicable to other Boolean network simulation frameworks, such as gene regulatory networks (Bornholdt, 2008; Biswas al., 2021).
NPN classification technique for accelerating
Neurosymbolic AI is a promising paradigm for integrating learning-basee techniques with symbolic algorithms that provide robustness and explainability. However, neurosymbolic methods generally involve heterogeneous computing architectures, which diverge from the current hardware roadmap of improving matrix- -acrox vector multiplication (Wan et al., 2024). One way of utilizing recent advances in matrix-vector multiplication architectures, such as compute-in-mentt memory crossbars (Rao et al., 2023; Ambrogio et al., 2023), is to use NN-based technology mapping to convert the symbolic circuits into matrix-vector multiplications. Hence, all components of the neurosymbolic system can be run on the same hardware architecture. Moreover, the high NN sparsity that results from K-LUT- based technology mapping (Gavier al., 2023) implies that the mapped NN is likely to satisfy the thermal constraints that accompany three-dimensional crossbars (Boahen, 2022). Our proposed NN optimization techniques reduce matrix sizes and energy requirements for neurosymbolic approaches that would use such matrix-vector multiplication architecture, which is of particular relevance for memory- and energy-limites edge computing applications.
For example, autonomous systems often integrate data from multiple sensors to make informed decisions about their actions. These systems typically employ NN encoders transform high- dimensional, continuous data into discrete set of symbolic classifications, which encapsulate critical information for the system. These classifications are then passed to logical decision-making algorithm that determines the system's 's actions. In modern computing architecture, the NN encoders could leverage compute-in-memory crossbars for efficient processing. However, the daeision-making algorithms are generally executed on digital processors, resulting in a heterogeneous system design. Using NN-based technology mapping, it is possible to translate logical circuits into a series of matrix-vector multiplications. This approach enables homogeneous system architecture consisting exclusively of crossbars and their associated peripherals. Our lossless NN optimization techniques, which reduce matrix sizes and the number of required operations in the resulting NN, would reduce the area requirements on the crossbar and lower energy consumption for such an architecture while ensuring the decision leaision-making algorithm is computed without error an aspect that is vital for system safety and reliability.
52


Reviews:
[{"review_id": "akATVMqEmD", "reviewer": "Reviewer_VSF5", "summary": "This paper proposes to optimize neural network representations of Boolean networks by improving the efficiency with NPN classification of sub-networks and considering objective in sub-networks during optimization. It achieves up to 5.9x speedup than the caching solution and reduces neurons and connections of final representations by 60% and 70% respectively.", "questions": "1. Please provide comparison with traditional DAG optimization methods for a fair comparison.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "This paper proposes to speedup the optimization of neural network representation of Boolean functions and consider architecture constraints. Instead of solving each subproblems independently, the paper finds solutions of each NPN class and exploit shared optimized representations of two-layer sub-networks. The optimization of sub networks is modeled as finding a polynomial with fewer monomials or monomial degrees. In architecture aware lossless optimization part, the level constraints are considered when performing sub-network replacement.", "weaknesses": "1. The scientific novelty is limited. NPN classification and level constraints based DAG optimization are common techniques used in logic synthesis tools and neural network compilers. \n2. The k-input LUT technology mapping lacks fair comparison with other traditional DAG optimization methods such as ABC (Boolean DAG optimization tools including technology indepedent and technology dependent optimization) and AI compilers like Google XLA.\n3. Only two-layer sub-NN optimization is considered which is relatively too local for better neurons and level optimization.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PJ30Uj7GXh", "reviewer": "Reviewer_Wkfo", "summary": "This paper presents a new approach to optimizing neural network representations of Boolean networks. The authors propose a technique compressing NNs via minimizing  the MP representation of each Boolean function in the network.", "questions": "* how well does it scale, as solving integer LP can be more demanding than solving LPs. \n* Computation complexity wiase, how does it compare against SOTAs?\n* What's the impat of  NPN equivalence lasses on the optimization process?", "limitations": "", "rating": 6, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "* The paper provides a solid theoretical foundation for the proposed approach, such as the equation introduction of new concepts like NPN and detailed analysis of the underlying optimization problem.\n* Evaluation looks comprehensive, including various bnchmarks, to demonstrate the effectiveness especialy in reducing network size and improving optimization time. \n* The proposed method looks interesting and novel as it combines multiple techniques including MP-based mapping, NPN equivalence classes and objec-aware optmization, to optimize representations of BNs.", "weaknesses": "Please see questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "M82ExGCSUt", "reviewer": "Reviewer_eC2r", "summary": "In this work, the authors present an optimization framework for deriving representations of neural networks of Boolean networks. The overall goal of the proposed framework is to overcome known limitations of current state-of-the-art methodologies that result in suboptimal neural networks, in terms of number of neurons and connections, which hinders their application in real-case scenarios. More specifically, the proposed method introduces a lossless technique for optimizing neurons and connections needed in a two-layer NN representation of a Boolean function. This is achieved by establishing an optimization problem that transforms the pruning of the network architecture into monomial reduction tasks for a given polynomial. The lossless functionality between the Minimized Multilinear Polynomial and the represented Boolean function is achieved by incorporating the heavyside threshold of the NN, with the relaxation of the optimization objective to the $l_1$-norm providing the required convexity. Due to the NP-hard nature of the proposed optimization, the authors introduce an objective-aware optimization, which is based on Negation-Permutation-Negation classification, that constructs subclasses of multilinear polynomial representations for the minimization of the Boolean functions, exploiting the shared representations among them and accelerating the NN optimization process using unique function caching. Finally, the paper provides two alternatives for optimizing the Neural Networks, one that involves all the vertices of the binary networks to the minimization of the multilinear polynomial and another that selects the subset of vertices in such a way that the depth of the resulting layer-merged neural network does not increase. The proposed method achieves significant improvements in contrast to the state-of-the-art approach in terms of optimization speed and the required connections and neurons.", "questions": "See Weaknesses", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is very well organized and written, providing the necessary background as well as the required proofs to support the claims of the authors. The experimental results clearly reflect the contribution of this work.\n\nThe proposed method outperforms the current state-of-the-art in terms of decreasing the size of neural networks, which means the number of connections and neurons, while simultaneously preserving the equivalent functionality. The proposed lossless compression, along with the objective-aware optimization, resulting in a faster and more efficient solution than the state-of-the-art.\n\nThe paper establishes a novel framework for lossless optimization techniques for neural network representation of boolean networks that can provide further advantages to neurosymbolic AI.", "weaknesses": "The proposed method is established in two-layer NN representation without discussing the potential generalization on the (2 + n) layer NN representation and the theoretical limits of the proposed method regarding this potential. Taking into account the non-stochastic nature of the proposed NPN transformation and the required time $O(m2^k) + e$, the proposed algorithm seems quite limited to the 2-layer NN representation. However, a further discussion of this can provide fruitful insights for future work.\n\nEven though the relaxation of the optimization objective provides the required convexity, the problem still remains NP-hard. Indeed, the proposed deterministic solution ensures the lossless functionality of the binary network with the caching solution providing significant acceleration, hindering, however, the scalability of the proposed method in target networks. To this end, I recommend further discussion of the existing stochastic methodologies in the bibliography for lossy solution, studying the accuracy-efficiency tradeoff between deterministic and non-deterministic methodologies. In my opinion, the deterministic linear programing nature of the proposed optimization method should be noted in the abstract of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "W9kqKMnqjk", "reviewer": "Reviewer_vaK3", "summary": "This paper addresses the challenge of optimizing neural network (NN) representations of Boolean networks (BNs). The authors point out that while NNs can represent Boolean functions, the current state-of-the-art method for deriving these representations often results in suboptimal NNs with a large number of neurons and connections, leading to inefficient simulation. Existing NN compression techniques are either lossy or inapplicable due to the specific nature of the NN-based technology mapping problem.\n\nThe paper makes three key contributions. First, it proposes a novel lossless technique for optimizing two-layer NN representations of Boolean functions, focusing on reducing the number of neurons and connections while preserving functional equivalence. This is achieved by formulating the problem as a constrained minimization task and employing a convex relaxation technique to solve it.  Second, the authors introduce an objective-aware optimization algorithm that leverages Negation-Permutation-Negation (NPN) classification. This algorithm exploits shared representations among the two-layer sub-networks to significantly speed up the optimization process, demonstrating a substantial speedup over naive and caching-based solutions. Third, an architecture-aware lossless optimization algorithm is proposed, targeting both unmerged and layer-merged NN architectures. This algorithm determines which sub-NNs should be minimized to achieve overall NN size reduction while optionally maintaining the depth of the layer-merged network, which is critical for latency-sensitive applications. Experimental results on benchmark BNs derived from digital circuits show significant reductions in the size of the resulting NNs, confirming the effectiveness of the proposed optimization techniques.", "questions": "1. **Generalization to other Boolean network domains:** The experimental results focus primarily on digital circuits. Could the authors elaborate on the applicability of their methods to other types of Boolean networks, such as gene regulatory networks or biological networks? Are there any specific adaptations or considerations needed for these domains?  Presenting results on even a small set of non-circuit BNs would greatly bolster the claim of general applicability.\n\n2. **Scalability analysis and potential optimizations:** The optimization time appears to grow considerably with BN size and K. Could the authors provide a more detailed analysis of the computational complexity of their methods?  Are there any potential optimizations or algorithmic improvements that could be explored to enhance scalability, such as parallelization or more efficient data structures? A breakdown of execution time for different stages of the algorithm would help identify bottlenecks\n\n3. **Clarifying the impact of NPN transformations on the number of MMP computations:**  The paper mentions that using NPN classification can reduce the number of MMP computations compared to function caching. However, the precise reduction factor ((2^k)!/2^(k+1)k!) is not immediately intuitive.  Could the authors provide a more detailed explanation of how this reduction is achieved and its significance in practice, perhaps with a concrete example for a small value of k?  It would be especially insightful to directly visualize how many MMP computations are saved for each benchmark circuit.\n\n4.  **Connection to Neurosymbolic AI Implementations:**  The paper mentions the potential of the work for neurosymbolic AI, but the link is somewhat abstract.  Could the authors expand on how specifically the proposed methods could be integrated into neurosymbolic systems? For example, are there specific neurosymbolic architectures or frameworks where these optimized NN representations would be particularly beneficial?  Perhaps a concrete example application scenario, even if hypothetical, could illustrate the potential.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Originality:** The paper tackles the problem of optimizing NN representations of Boolean networks from a fresh perspective. While NN compression is a well-studied area, the authors identify a specific gap in existing techniques, namely the lack of *lossless* methods applicable to the BN-to-NN mapping problem. They creatively combine ideas from Boolean function classification (NPN) and convex optimization to develop a new approach to address this gap. The concept of leveraging NPN classes to accelerate the optimization by exploiting shared representations among subproblems is particularly original and demonstrates a deep understanding of the underlying structure of the problem. Moreover, the introduction of the *leeway* concept and the architecture-aware algorithm for maintaining depth in layer-merged NNs showcases innovative thinking in adapting the optimization process to different NN architectures.\n\n**Quality:** The paper is technically sound, with rigorous mathematical formulations and proofs supporting the proposed methods. The authors carefully define the necessary concepts and notation, ensuring clarity in their technical exposition. The experimental methodology is well-designed, with appropriate benchmarks and metrics used for evaluation. The comparison against relevant baselines (naive and caching solutions) provides a strong validation of the proposed techniques. The inclusion of additional results and analysis in the appendix further reinforces the quality of the work.\n\n**Clarity:** The paper is generally well-written and organized. The introduction effectively motivates the problem and summarizes the key contributions. The background section provides the necessary context and definitions, though perhaps could benefit from a slightly higher-level motivating example early on for a broader audience.  The use of figures, especially Figure 1, significantly aids in understanding the optimization problem and the proposed approach. The steps of the algorithms are clearly presented, and the results are reported in a concise and informative manner.\n\n**Significance:** The paper addresses an important problem with practical implications for various domains. Efficient BN simulation is crucial in areas like circuit verification and design automation. The proposed optimization techniques can lead to substantial reductions in NN size and faster optimization times, making NN-based BN simulation more practical and scalable. Moreover, the connection to neurosymbolic AI highlights the potential of the work for advancing this emerging field. The ability to represent symbolic systems efficiently using NNs could pave the way for new hardware architectures and algorithms that combine the strengths of both symbolic and connectionist AI approaches.  The paper's focus on lossless compression is also significant from a safety and reliability perspective, as it ensures that the optimized NN representation remains functionally equivalent to the original BN.", "weaknesses": "1. **Impact of L1 Relaxation:** The authors acknowledge that relaxing the ℓ0-norm objective to ℓ1 might lead to suboptimal solutions. However, the paper lacks a detailed analysis of the extent to which this relaxation affects the quality of the results.  Quantifying the gap between the ℓ0 and ℓ1 solutions for the benchmark BNs, or investigating alternative approximation methods for the ℓ0-norm minimization, would provide a more complete understanding of the trade-offs involved.  Perhaps experiments comparing the optimized NN size obtained with ℓ1 relaxation to theoretical lower bounds achievable with ℓ0 could highlight the potential room for improvement.\n\n2. **Scalability to Larger BNs:** The experimental results suggest that the optimization time can become substantial for large BNs and higher values of K (maximum input size of LUTs).  While the NPN classification algorithm offers speedups compared to caching, the paper does not thoroughly investigate the scalability limitations of the overall method.  Analyzing the runtime complexity as a function of BN size and K, and potentially exploring strategies for further improving the efficiency of the optimization process (e.g., by leveraging parallelism or more sophisticated data structures), would be beneficial.  Consider profiling the algorithms to pinpoint bottlenecks and focus optimization efforts.\n\n3. **Clarity and Accessibility for a Broader Audience:** Although the technical content is generally well-explained, the paper could benefit from a more intuitive and accessible introduction to the problem and its significance. Providing a high-level illustrative example that highlights the practical implications of optimizing NN representations of BNs would engage a broader readership within the ICLR community. While the paper currently focuses on a specialized audience with expertise in Boolean functions, making it more approachable for readers with a general machine learning background would enhance its impact.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)