5 Randomised complexity of \(\operatorname{eval}\)

Definition 5.1 Randomised complexity of a protocol

The communication complexity of a randomised NOF protocol \(P\) for \(F\) with error \(\epsilon \) is the smallest time \(t\) such that

\[ \mathbb P(x \mid P \text{ is not valid at time } t) \le \epsilon \]

or \(\infty \) if no such \(t\) exists.

Definition 5.2 Randomised complexity of a function

The randomised communication complexity of a function \(F\) with error \(\epsilon \), denoted \(R_\epsilon (F)\), is the minimum of the randomised communication complexity of \(P\) when \(P\) ranges over all randomised NOF protocols.

Definition 5.3 The randomised equality testing protocol for \(\operatorname{eval}\)

The randomised equality testing protocol for \(\operatorname{eval}\) has domain \(\Omega := (\operatorname{Bool}^d)^{\lceil \log _2\epsilon ^{-1}\rceil }\) with the uniform measure and is defined by making participant \(i\) do “Compute

\[ a_{i, k} = \sum _{j \ne i} \omega _{j, k}x_j \]

and send the sum of the digits of \(a_{i, t/d}\) mod \(2\) at time \(t\)” and “Guess \(1\) iff the sum of the digits of \(\omega _i x_i\) + what participant \(i\) said is \(0\) modulo \(2\)”.

Lemma 5.4 The randomised equality testing protocol for \(\operatorname{eval}\) is valid

The randomised equality testing protocol is valid for \(\operatorname{eval}\) at time \(2d\).

Proof ▶

If \(\operatorname{eval}(x) = 1\), then the protocol guesses correctly. Else it errors with probability

\[ 2^{-\lceil {\log _2\epsilon ^{-1}}\rceil } \le \epsilon \]

Theorem 5.5 The randomised complexity of \(\operatorname{eval}\) is constant

\[ R_\epsilon (\operatorname{eval}) \le 2d\lceil \log _2\epsilon ^{-1}\rceil \]

Proof ▶

By Lemma 5.4, the randomised equality testing protocol is valid for \(\operatorname{eval}\) at time \(2d\).