Randomized OBDDs for the most significant bit of multiplication need exponential space

DOI10.1016/j.ipl.2010.11.013zbMath1260.68151MaRDI QIDQ1944061

Marc Gillé, Beate Bollig

Publication date: 4 April 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.11.013

zbMATH Keywords

computational complexity; randomized algorithms

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68P05: Data structures

68W20: Randomized algorithms

Cites Work

• Unnamed Item
• On data structures and asymmetric communication complexity
• A lower bound for integer multiplication on randomized ordered read-once branching programs.
• 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
• A Larger Lower Bound on the OBDD Complexity of the Most Significant Bit of Multiplication
• Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions
• Graph-Based Algorithms for Boolean Function Manipulation
• Branching Programs and Binary Decision Diagrams
• Randomization and nondeterminism are comparable for ordered read-once branching programs