Better upper bounds on the QOBDD size of integer multiplication
From MaRDI portal
Publication:2370421
DOI10.1016/j.dam.2006.11.010zbMath1120.68056OpenAlexW2065197237MaRDI QIDQ2370421
Publication date: 26 June 2007
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2006.11.010
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (7)
On the OBDD Complexity of the Most Significant Bit of Integer Multiplication ⋮ New results on the most significant bit of integer multiplication ⋮ On the OBDD complexity of the most significant bit of integer multiplication ⋮ Larger lower bounds on the OBDD complexity of integer multiplication ⋮ A note on the size of OBDDs for the graph of integer multiplication ⋮ An asymptotically optimal lower bound on the OBDD size of the middle bit of multiplication for the pairwise ascending variable order ⋮ Larger Lower Bounds on the OBDD Complexity of Integer Multiplication
Cites Work
- Unnamed Item
- A lower bound for integer multiplication on randomized ordered read-once branching programs.
- BDDs -- design, analysis, complexity, and applications.
- Bounds on the OBDD-size of integer multiplication via universal hashing
- On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
- Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions
- Graph-Based Algorithms for Boolean Function Manipulation
- A Lower Bound for Integer Multiplication with Read-Once Branching Programs
- The size of reduced OBDD's and optimal read-once branching programs for almost all Boolean functions
- A read-once branching program lower bound of Ω(2 n/4 ) for integer multiplication using universal hashing
- On the OBDD-representation of general Boolean functions
- Finding the optimal variable ordering for binary decision diagrams
- Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems
This page was built for publication: Better upper bounds on the QOBDD size of integer multiplication