A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs
From MaRDI portal
(Redirected from Publication:1007589)
Recommendations
- A simple function that requires exponential size read-once branching programs
- A very simple function that requires exponential size read-once branching programs.
- scientific article; zbMATH DE number 1962822
- Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs
- A lower bound technique for nondeterministic graph-driven read-once-branching programs and its applications
- scientific article; zbMATH DE number 1929932
- On the complexity of randomized read-once branching programs
- Comparing the sizes of nondeterministic branching read-k-times programs
- Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication
- A lower bound for read-once-only branching programs
Cites work
- scientific article; zbMATH DE number 4204283 (Why is no real title available?)
- scientific article; zbMATH DE number 512863 (Why is no real title available?)
- scientific article; zbMATH DE number 1011685 (Why is no real title available?)
- scientific article; zbMATH DE number 1962822 (Why is no real title available?)
- scientific article; zbMATH DE number 1929932 (Why is no real title available?)
- scientific article; zbMATH DE number 2086709 (Why is no real title available?)
- scientific article; zbMATH DE number 1834649 (Why is no real title available?)
- A comparison of free BDDs and transformed BDDs
- Branching Programs and Binary Decision Diagrams
- Communication Complexity
- Efficient Boolean manipulation with OBDD's can be extended to FBDD's
- Graph driven BDDs -- a new data structure for Boolean functions
- Graph-Based Algorithms for Boolean Function Manipulation
- On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs
- Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication
- Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
- Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems
Cited in
(6)- Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs
- scientific article; zbMATH DE number 1962822 (Why is no real title available?)
- A simple function that requires exponential size read-once branching programs
- A very simple function that requires exponential size read-once branching programs.
- Folklore confirmed
- Bounded semantics
This page was built for publication: A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1007589)