Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication
From MaRDI portal
Publication:2771493
DOI10.1051/ita:2001113zbMath0992.68057OpenAlexW2027355214MaRDI QIDQ2771493
Publication date: 14 February 2002
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: http://www.numdam.org/item?id=ITA_2001__35_2_149_0
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (5)
On the OBDD Complexity of the Most Significant Bit of Integer Multiplication ⋮ On the OBDD complexity of the most significant bit of integer multiplication ⋮ Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication ⋮ A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs ⋮ Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Graph driven BDDs -- a new data structure for Boolean functions
- Probabilistic verification of Boolean functions
- Polynomial size \(\Omega\)-branching programs and their computational power
- Meanders and their applications in lower bounds arguments
- Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs
- Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams
- 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
- A Lower Bound for Integer Multiplication with Read-Once Branching Programs
- Efficient Boolean manipulation with OBDD's can be extended to FBDD's
- Branching Programs and Binary Decision Diagrams
- Read-once projections and formal circuit verification with binary decision diagrams
- 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: Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication
