Randomized OBDDs for the Most Significant Bit of Multiplication Need Exponential Size
From MaRDI portal
Publication:3075511
DOI10.1007/978-3-642-18381-2_11zbMath1298.68109OpenAlexW1668478328MaRDI QIDQ3075511
Publication date: 15 February 2011
Published in: SOFSEM 2011: Theory and Practice of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-18381-2_11
computational complexityordered binary decision diagramslower boundsinteger multiplicationrandomized one-round communication complexity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On data structures and asymmetric communication complexity
- On randomized one-round communication complexity
- A lower bound for integer multiplication on randomized ordered read-once branching programs.
- Threshold circuits of bounded depth
- Lower bounds for predecessor searching in the cell probe model
- Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication
- Fast multiplication of large numbers
- 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
- Larger Lower Bounds on the OBDD Complexity of Integer Multiplication
- Graph-Based Algorithms for Boolean Function Manipulation
- A Lower Bound for Integer Multiplication with Read-Once Branching Programs
- Branching Programs and Binary Decision Diagrams
- Randomization and nondeterminism are comparable for ordered read-once branching programs
- Communication Complexity
- A read-once branching program lower bound of Ω(2 n/4 ) for integer multiplication using universal hashing
This page was built for publication: Randomized OBDDs for the Most Significant Bit of Multiplication Need Exponential Size
