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.002zbMATH Open1206.68152OpenAlexW2005253641MaRDI QIDQ708357FDOQ708357
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
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
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Branching Programs and Binary Decision Diagrams
- On the OBDD Complexity of the Most Significant Bit of Integer Multiplication
- New results on the most significant bit of integer multiplication
- Better upper bounds on the QOBDD size of integer multiplication
- Bounds on the OBDD-size of integer multiplication via universal hashing
- Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions
- New results on the complexity of the middle bit of multiplication
- 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
Cited In (2)
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)
