No label defined (Q3790653)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4055049
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4055049 |
Statements
1988
0 references
function evaluating
0 references
unidirectional asynchronous ring of processors
0 references
communication complexity
0 references
Boolean function
0 references
randomized algorithm
0 references
0.9957449436187744
0 references
0.8094399571418762
0 references
0.7717304229736328
0 references
0.7678064703941345
0 references
0.7650940418243408
0 references
[For the entire collection see Zbl 0638.00039.] Let R be a unidirectional asynchronous ring of n processors each with a single input bit. Let f be any cyclic non-constant function of n Boolean variables. Moran and Warmuth prove that any deterministic algorithm for R that evaluates f has communication complexity \(\Omega\) (n log n) bits. They also construct a cyclic non-constant Boolean function that can be evaluated in O(n log n) bits by a deterministic algorithm. This contrasts with the following new results: 1. There exists a cyclic non-constant Boolean function which can be evaluated with expected complexity O(n \(\sqrt{\log n})\) bits by a randomized algorithm for R. 2. Any nondeterministic algorithm for R which evaluates any cyclic non- constant function has communication complexity \(\Omega\) (n \(\sqrt{\log n})\) bits.
0 references