Larger lower bounds on the OBDD complexity of integer multiplication
From MaRDI portal
Publication:553298
DOI10.1016/j.ic.2010.11.007zbMath1217.68111OpenAlexW2088302362MaRDI QIDQ553298
Publication date: 27 July 2011
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2010.11.007
computational complexityordered binary decision diagramslower boundscommunication complexityinteger multiplication
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (06E30)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An asymptotically optimal lower bound on the OBDD size of the middle bit of multiplication for the pairwise ascending variable order
- A note on the size of OBDDs for the graph of integer multiplication
- Reduction of OBDDs in linear time
- Optimal lower bounds on the depth of polynomial-size threshold circuits for some arithmetic functions
- Better upper bounds on the QOBDD size of integer multiplication
- Symbolic topological sorting with OBDDs
- Symbolic graphs: Linear solutions to connectivity related problems
- Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication
- 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
- On the OBDD Complexity of the Most Significant Bit of Integer Multiplication
- Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms
- Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions
- New Results on the Most Significant Bit of Integer Multiplication
- Graph-Based Algorithms for Boolean Function Manipulation
- Branching Programs and Binary Decision Diagrams
- Communication Complexity
- SOFSEM 2005: Theory and Practice of Computer Science
This page was built for publication: Larger lower bounds on the OBDD complexity of integer multiplication
