Larger Lower Bounds on the OBDD Complexity of Integer Multiplication

DOI10.1007/978-3-642-00982-2_18zbMath1234.68085OpenAlexW2687667803MaRDI QIDQ3618582

Beate Bollig

Publication date: 2 April 2009

Published in: Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-00982-2_18

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Related Items (2)

New results on the most significant bit of integer multiplication ⋮ Randomized OBDDs for the Most Significant Bit of Multiplication Need Exponential Size

Cites Work

• Unnamed Item
• A note on the size of OBDDs for the graph of integer multiplication
• 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
• 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