On the OBDD Complexity of the Most Significant Bit of Integer Multiplication

DOI10.1007/978-3-540-79228-4_27zbMath1139.68342OpenAlexW1499765196MaRDI QIDQ3502656

Beate Bollig

Publication date: 27 May 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-79228-4_27

zbMATH Keywords

computational complexityordered binary decision diagramslower boundsinteger multiplication

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Related Items (9)

Randomized OBDDs for the most significant bit of multiplication need exponential space ⋮ New results on the most significant bit of integer multiplication ⋮ On symbolic OBDD-based algorithms for the minimum spanning tree problem ⋮ Larger lower bounds on the OBDD complexity of integer multiplication ⋮ A note on the size of OBDDs for the graph of integer multiplication ⋮ An asymptotically optimal lower bound on the OBDD size of the middle bit of multiplication for the pairwise ascending variable order ⋮ On the OBDD Complexity of Threshold Functions and the Variable Ordering Problem ⋮ Larger Lower Bounds on the OBDD Complexity of Integer Multiplication ⋮ Randomized OBDDs for the Most Significant Bit of Multiplication Need Exponential Size

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• 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
• A lower bound technique for nondeterministic graph-driven read-once-branching programs and its applications
• Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication
• On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
• Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions
• Graph-Based Algorithms for Boolean Function Manipulation
• A Lower Bound for Integer Multiplication with Read-Once Branching Programs
• Branching Programs and Binary Decision Diagrams
• Communication Complexity
• A read-once branching program lower bound of Ω(2 ^n/4 ) for integer multiplication using universal hashing
• SOFSEM 2006: Theory and Practice of Computer Science

This page was built for publication: On the OBDD Complexity of the Most Significant Bit of Integer Multiplication