scientific article; zbMATH DE number 7092118
From MaRDI portal
Publication:5228561
zbMath1497.68175MaRDI QIDQ5228561
Publication date: 12 August 2019
Full work available at URL: http://mathnet.ru/eng/ivm103
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Classical models of computation (Turing machines, etc.) (68Q04)
Cites Work
- Probabilistic communication complexity
- Graph driven BDDs -- a new data structure for Boolean functions
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- A linear lower bound on the unbounded error probabilistic communication complexity.
- Graph-Based Algorithms for Boolean Function Manipulation
- Efficient Boolean manipulation with OBDD's can be extended to FBDD's
- Branching Programs and Binary Decision Diagrams
- Randomization and nondeterminism are comparable for ordered read-once branching programs
- On BPP versus \(NP\cup coNP\) for ordered read-once branching programs
- The satisfiability problem for probabilistic ordered branching programs
This page was built for publication:
