Technical Reports

The ICICS/CS Reading Room

UBC CS TR-87-20 Summary

Randomized Function Evaluation on a Ring, May 1987 Karl Abrahamson, Andrew Adler, Lisa Higham and David G. Kirkpatrick

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: \begin{enumerate} \item 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. \end{enumerate

If you have any questions or comments regarding this page please send mail to