An asymptotically optimal lower bound on the OBDD size of the middle bit of multiplication for the pairwise ascending variable order

DOI10.1016/J.DAM.2010.03.002zbMath1206.68152OpenAlexW2005253641MaRDI QIDQ708357

Martin Sauerhoff

Publication date: 11 October 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2010.03.002

zbMATH Keywords

lower boundmultiplicationuniversal hashingOBDDmiddle bit

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Larger lower bounds on the OBDD complexity of integer multiplication

Cites Work

• Better upper bounds on the QOBDD size of integer multiplication
• New results on the most significant bit of integer multiplication
• New results on the complexity of the middle bit of multiplication
• Bounds on the OBDD-size of integer multiplication via universal hashing
• On the OBDD Complexity of the Most Significant Bit of Integer Multiplication
• A Larger Lower Bound on the OBDD Complexity of the Most Significant Bit of Multiplication
• Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions
• Branching Programs and Binary Decision Diagrams
• A read-once branching program lower bound of Ω(2 ^n/4 ) for integer multiplication using universal hashing

This page was built for publication: An asymptotically optimal lower bound on the OBDD size of the middle bit of multiplication for the pairwise ascending variable order