On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
type: Item
instance of: scholarly article
title: On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
zbMATH Open document ID: 1007.68065
author: Georg Schnitger
author: Juraj Hromkovič
published in: Information and Computation
publication date: 2003-01-14T00:00:00Z
Mathematics Subject Classification ID: 68Q10
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68W20
zbMATH DE Number: 1853201
zbMATH Keywords: computational power of randomized computations
zbMATH Keywords: Las Vegas computation
zbMATH Keywords: deterministic computation
zbMATH Keywords: nondeterministic computation
zbMATH Keywords: complexity measures
zbMATH Keywords: one-way communication complexity
zbMATH Keywords: ordered binary decision diagrams
zbMATH Keywords: finite automata
MaRDI profile type: Publication
full work available at URL: inco.2001.3040
OpenAlex ID: W2072453354
cites work: Relationships between nondeterministic and deterministic tape complexities
cites work: Exact lower time bounds for computing Boolean functions on CREW PRAMs
cites work: Q4293543
cites work: Q4337605
cites work: Communication Complexity
cites work: Q4228510
cites work: Graph-Based Algorithms for Boolean Function Manipulation
cites work: Q3762226
cites work: On quantum and probabilistic communication
cites work: Communication complexity
cites work: Q3768423
DOI: 10.1006/INCO.2001.3040
description: scientific article; zbMATH DE number 1853201