On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
DOI10.1006/inco.2001.3040zbMath1007.68065OpenAlexW2072453354MaRDI 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 diagramsfinite automatacomplexity measuresnondeterministic computationLas Vegas computationdeterministic computationcomputational power of randomized computationsone-way communication complexity
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 (26)
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
This page was built for publication: On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata