A lower bound for integer multiplication on randomized ordered read-once branching programs.
DOI10.1016/S0890-5401(03)00118-4zbMath1059.68045WikidataQ62045248 ScholiaQ62045248MaRDI QIDQ1426006
Marek Karpinski, Farid M. Ablayev
Publication date: 14 March 2004
Published in: Information and Computation (Search for Journal in Brave)
ComplexityRandomized algorithmsOBDDLower boundsDeterministic and randomized branching programsInteger multiplication
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)
Related Items (6)
Cites Work
- The graph of multiplication is equivalent to counting
- Efficient data structures for Boolean functions
- On lower bounds for read-\(k\)-times branching programs
- On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
- Graph-Based Algorithms for Boolean Function Manipulation
- Branching Programs and Binary Decision Diagrams
- Randomization and nondeterminism are comparable for ordered read-once branching programs
- Lower bounds for one-way probabilistic communication complexity
- Communication Complexity
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: A lower bound for integer multiplication on randomized ordered read-once branching programs.