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)

zbMATH Keywords

ComplexityRandomized algorithmsOBDDLower boundsDeterministic and randomized branching programsInteger multiplication

Mathematics Subject Classification ID

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)

Better upper bounds on the QOBDD size of integer multiplication ⋮ Approximating Boolean functions by OBDDs ⋮ Randomized OBDDs for the most significant bit of multiplication need exponential space ⋮ On BPP versus \(NP\cup coNP\) for ordered read-once branching programs ⋮ Randomized OBDDs for the Most Significant Bit of Multiplication Need Exponential Size ⋮ On the computational power of probabilistic and quantum branching program

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.