Better upper bounds on the QOBDD size of integer multiplication

DOI10.1016/j.dam.2006.11.010zbMath1120.68056OpenAlexW2065197237MaRDI QIDQ2370421

Akira Maruoka, Kazuyuki Amano

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

zbMATH Keywords

upper boundsinteger multiplicationordered binary decision diagram

Mathematics Subject Classification ID

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