Randomized Function Evaluation on a Ring

Karl Abrahamson, Andrew Adler, Lisa Higham and David G. Kirkpatrick
Publishing date
May 1987

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 [8] 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: 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$. \item Any nondeterministic algorithm for $R$ which evaluates any cyclic non-constant function has communication complexity $\Omega (n \sqrt{\log n})$ bits.