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.002MaRDI QIDQ708357zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Better upper bounds on the QOBDD size of integer multiplication
• On the OBDD complexity of the most significant bit of integer multiplication
• scientific article; zbMATH DE number 1688393
• Bounds on the OBDD-size of integer multiplication via universal hashing
• Larger lower bounds on the OBDD complexity of integer multiplication

Cites work

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

Cited in

(2)

• Larger lower bounds on the OBDD complexity of integer multiplication
• Better upper bounds on the QOBDD size of integer multiplication

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q708357)