Upper and lower bounds on the OBDD-width of a special integer multiplication
Abstract
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)})$.
Fields of Study & Subjects
Coding theory and cryptography
Cryptography and Residue Arithmetic
Tensor decomposition and applications
Publication details
- Journal / source
- arXiv (Cornell University)
- Volume
- 118
- Issue
- 268
- Pages
- 45–54
- Publication date
- 31 August 2026
- Language
- EN
- Document type
- Preprint