Source-linked AI summary
Upper and lower bounds on the OBDD-width of a special integer multiplication
Tong Qin
TL;DR
The paper studies the OBDD width of a restricted-domain multiplication function computing the middle product bit, addressing the gap in matching upper and lower exponents. It introduces a combinatorial function s_*(n) and proves that the width is Θ(2^{s_*(n)}), while identifying scope and characterization limitations.
Problem
Existing upper and lower OBDD bounds for integer multiplication have a gap between their exponents, motivating a concrete matching exponent for restricted-domain middle-bit multiplication.
Method
The paper defines s_*(n) combinatorially and analyzes OBDD width using fooling sets and path sets.
Results
The OBDD width for SMul_{n−1}^n is Θ(2^{s_*(n)}), unifying the upper and lower bounds through s_*(n).
Takeaways & Limitations
The result gives an early example in which upper and lower OBDD bounds for integer multiplication are characterized by the same combinatorial function.
Takeaways & Limitations
The paper gives only asymptotic bounds rather than an exact closed form for s_*(n), and the unification applies only to a restricted class of inputs.
Abstract
from arXiv · showhide
We consider the Boolean function ${\rm SMul}_{n-1}^n(\boldsymbol{x},\boldsymbol{y})$, which computes the middle bit of the multiplication of two natural numbers represented as $n$-bit binary strings $\boldsymbol{x}$ and $\boldsymbol{y}$, drawn from a restricted domain. We investigate the width of OBDDs computing ${\rm SMul}_{n-1}^n$. We introduce a combinatorially defined function $s_*(n)$ and show that the width of such OBDDs is $Θ(2^{s_*(n)})$.
1 Introduction
The introduction frames a gap between existing upper and lower OBDD-size exponents for integer multiplication and seeks a concrete matching exponent. It introduces s_*(n) and shows that OBDD width for SMul_{n-1}^n is Θ(2^{s_*(n)}), yielding matching bounds.
- 1 Introduction: OBDDs represent Boolean functions with ordered variable tests, and reduced OBDDs are uniquely determined for each function and ordering.Reduction merges identical subgraphs and removes nodes whose children are identical.
- 1 Introduction: Existing bounds for integer-multiplication OBDDs have different exponents, motivating a matching exponent s(n)=Ω(n).The desired bounds are 2^{s(n)} ≤ |B(Mul)| ≤ p(n)2^{s(n)} for some polynomial p(n).
- 1 Introduction: The paper introduces a combinatorially defined function s_*(n) as a concrete matching exponent.This is presented as a step toward replacing the abstract exponent log_2|B(Mul_{n-1}^n)| with a concrete function.
- 1 Introduction: Θ(2^{s_*(n)}) is the width of OBDDs computing SMul_{n-1}^n.The resulting bounds are 2·2^{s_*(n)}−1 ≤ |B(SMul_{n−1}^n)| ≤ n·2^{s_*(n)}.
2 Preliminaries
The preliminaries define OBDD width through edges crossing a variable-order boundary and introduce fooling sets and path sets to bound that width. They also connect width bounds to OBDD size.
- 2 Preliminaries: For variable x_i, its width is the number of edges entering x_i or later nodes from nodes before x_i.The definition uses E_π(i), the set of such crossing edges in B_π(f).
- 2 Preliminaries: A partition around x_i separates variables before x_i into L from the remaining variables R.The first variable in R under the ordering is x_i, and assignments l·r combine left and right assignments.
- 2 Preliminaries: A fooling set contains left assignments that can be distinguished by some common right assignment.For distinct l and l′, some r makes f(l′·r) differ from f(l·r).
- 2 Preliminaries: A path set represents every left assignment by an equivalent representative whose behavior agrees for every right assignment.This supports upper bounds because equivalent left assignments reach the same OBDD node under uniqueness.
- 2 Preliminaries: Fooling-set and path-set cardinalities bound width from below and above, respectively.The framework gives |P(L,R)| as an upper bound on width, while a subtree argument supplies a lower bound of 2Width_π(i)−1 nodes.
- 2 Preliminaries: Width bounds are polynomially related to OBDD size, enabling width estimates to yield size estimates.The stated corollary gives 2c_1 2^{s(n)}−1 ≤ |B(f)| ≤ c_2 n 2^{s(n)} under the corresponding width conditions.
3 Upper and lower bound analysis
The paper analyzes OBDD widths for the restricted middle-bit multiplication function by constructing fooling sets for lower bounds and path sets for upper bounds. Both bounds are expressed through the combinatorial quantity s_*(n), yielding an exponential width characterization.
- 3.1 A lower bound: The restricted function fixes two y-variables to 1 and all other y-variables to 0, reducing its middle-bit value to a parity expression involving x_a, x_b, and possibly x_m.A carry occurs only when x_m = x_{m-h} = 1, where h = b − a and m is the largest relevant index satisfying the equality.
- 3.1 A lower bound: The split set records positions where paired x-variables cross a partition induced by an ordering, identifying the locations relevant to fooling-set construction.Each x-variable index has a unique representation as k(j,p), supporting the definition of Split(L, R; a, b).
- 3.1 A lower bound: Maximizing the split-set size over partitions and pairs a < b, then minimizing over x-variable orderings, defines s_*(n) and gives a width lower bound for every OBDD ordering.The argument applies even when y-variables are interleaved, by relating x-variable partitions to OBDD width and extending the ordering.
- 3.1 A lower bound: The fooling set A(L, R; a, b) has size 2^|Split(L,R;a,b)| and distinguishes distinct left assignments using a suitable right assignment.The proof handles cases m′ = b and m′ < b, ensuring the two assignments produce different function values through carry or parity behavior.
- 3.1 A lower bound: The paper leaves open a combinatorial characterization of the x-variable ordering π_wopt that achieves the minimum defining s_*(n).The limitation concerns understanding the optimal ordering, not the width characterization itself.
- 3.2 An upper Bound: A path-set construction provides the matching upper-bound scale, with |P(L, R; a, b)| ≤ 8 · 2^|Split(L,R;a,b)| for an ordering π_wopt.The construction preserves the relevant x_a, x_b, and x_m values across paired assignments, leading to the stated upper-bound theorem.
4 Analysis of s∗(n)
The analysis relates the auxiliary Split′(h) construction to Split(L, R; a, b), transferring fooling-set bounds across the two formulations. For every −n/2 < h < n/2, suitable parameters a and b yield a Split set at least as large as Split′(h).
- Analysis of s∗(n): Split′(h) is introduced as a construction similar to Split(L, R; a, b) for bounding its size.The paper notes that the relationship is formalized by a subsequent lemma.
- Analysis of s∗(n): For any variable ordering π and partition (L, R), the analysis compares Split(L, R; a, b) with Split′(h).The comparison is made using partitions with |L| = n/2 in the cited lemma statement.
- Analysis of s∗(n): For every −n/2 < h < n/2, some pair (a, b) satisfies |Split(L, R; a, b)| ≥ |Split′(h)|.The proof treats h ≥ 0 and h < 0 separately, mapping the corresponding variable pairs into Split(L, R; a, b).
- Analysis of s∗(n): The construction also establishes h ≤ n/2 and |Split(L, R; a, b)| ≤ n/2 when one partition has size below n/2.This bounds the number of relevant split parameters by the size of the smaller partition.
5 Conclusion
The paper studies the middle multiplication bit on a restricted domain and characterizes the OBDD width using a combinatorial function s_*(n). It presents this as an example of unifying upper and lower bounds, while leaving exact and unrestricted cases open.
- Conclusion: The target function SMul_(n−1)^n(x, y) computes the middle multiplication bit for n-bit inputs from a restricted domain.The paper frames this restricted-domain function as its object of study.
- Conclusion: The combinatorial function s_*(n) characterizes both the upper and lower OBDD-width bounds for SMul_(n−1)^n.The conclusion states that the two bounds can be expressed through the same function.
- Conclusion: The result provides an early example of unified upper and lower OBDD bounds for integer multiplication.This unification is stated within the paper’s multiplication setting.
- Conclusion: The work gives only asymptotic bounds for s_*(n), not an exact closed-form formulation.Determining the precise function is left for future research.
- Conclusion: The unification applies only to a restricted class of x and y, whereas arbitrary n-bit binary strings remain outside the established scope.The paper identifies extension to arbitrary inputs as significantly more challenging.
A Proof of Claim 2 and 3
The appendix proves Claims 2 and 3 by constructing right assignments and analyzing parity relations across paired indices. These constructions establish the required separation and exclusion properties for the fooling-set arguments.
- A Proof of Claim 2 and 3: Claim 2 handles the case m′ = b by defining r(x_i) = 0 for every x_i in R.The resulting construction is used to establish the claim’s listed properties.
- A Proof of Claim 2 and 3: The same m′ = b construction also excludes an index i in H with l′ · r(x_i) = l′ · r(x_{i−h}) = 1.The appendix states this as the analogous property for l′.
- A Proof of Claim 2 and 3: For m′ < b, r is defined from the unique pair (j, p) satisfying k(j, p) = i, using ω_p on Split(L, R; a, b) and zero otherwise.The definition is piecewise: indices above b receive 0, while indices at most b use the parity expression.
- A Proof of Claim 2 and 3: The appendix proves property (1) by showing that paired variables x_a and x_b lie in the same partition and therefore differ under both assignments.This yields l · r(x_a) ⊕ l · r(x_b) = l′ · r(x_a) ⊕ l′ · r(x_b) = 1.
- A Proof of Claim 2 and 3: For paired indices x_i and x_{i−h}, the relations p_1 = p_2 and j_1 + 1 = j_2 force opposite parity values under l · r.The proof uses the same relations to derive the corresponding equality required in property (2).