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
      [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

      Identifiers