On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
DOI10.1006/inco.2001.3040zbMath1007.68065MaRDI QIDQ1854456
Georg Schnitger, Juraj Hromkovič
Publication date: 14 January 2003
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/inco.2001.3040
ordered binary decision diagrams; finite automata; complexity measures; nondeterministic computation; Las Vegas computation; deterministic computation; computational power of randomized computations; one-way communication complexity
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W20: Randomized algorithms
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Communication complexity
- Exact lower time bounds for computing Boolean functions on CREW PRAMs
- Relationships between nondeterministic and deterministic tape complexities
- On quantum and probabilistic communication
- Graph-Based Algorithms for Boolean Function Manipulation
- Communication Complexity