Randomized OBDDs for the most significant bit of multiplication need exponential space
From MaRDI portal
Publication:1944061
DOI10.1016/j.ipl.2010.11.013zbMath1260.68151MaRDI QIDQ1944061
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
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