# The ICICS/CS Reading Room

## UBC CS TR-87-20 Summary

- No on-line copy of this technical report is available.

- 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
help@cs.ubc.ca.