2 The NOF model

Let \(G\) be a finite abelian group whose size we will denote \(d\). Let \(d \ge 3\) a natural number.

Definition 2.1 NOF protocol

✓

A NOF protocol \(P\) consists of maps

\begin{align} \operatorname{strat}: & [d] \to G^{d - 1} \to \operatorname{List}\operatorname{Bool}\to \operatorname{Bool}\\ \operatorname{guess}: & [d] \to G^{d - 1} \to \operatorname{List}\operatorname{Bool}\to \operatorname{Bool}\end{align}

We will not make \(P\) part of any notation as it is usually fixed from the context.

Definition 2.2 NOF broadcast

✓

Given a NOF protocol \(P\), the NOF broadcast on input \(x : G^d\) is inductively defined by

\begin{align} \operatorname{broad}(x) : \mathbb {N}& \to \operatorname{List}\operatorname{Bool}\\ 0 & \mapsto [] \\ t + 1 & \mapsto \operatorname{strat}_{t \% d}(\operatorname{forget}_{t \% d}(x), \operatorname{broad}(x, t)) :: \operatorname{broad}(x, t) \end{align}

Lemma 2.3 Length of a broadcast

✓

For every NOF protocol \(P\), every input \(x : G^d\) and every time \(t\), \(\operatorname{broad}(x, t)\) has length \(t\).

Proof ▶

Induction on \(t\).

Definition 2.4 Valid NOF protocol

✓

Given a function \(F : G^d \to \operatorname{Bool}\), the NOF protocol \(P\) is valid in \(F\) at time \(t\) on input \(x\) if all participants correctly guess \(F(x)\), namely if

\[ \operatorname{guess}_i(\operatorname{forget}_i(x), \operatorname{broad}(x, t)) = F(x) \]

for all \(i : [d]\).

Definition 2.5 The trivial protocol

For all \(F\), we define the trivial protocol by making participant \(i\) do "Send the \(t / d\)-th bit of the number of participant \(i + 1\)" and "Compute \(x_i\) from the binary representation given by participant \(i - 1\), then compute \(F(x)\)".

Lemma 2.6 The trivial protocol is valid

For all \(F\), the trivial protocol for \(F\) is valid in time \(d\left\lceil \log _2 n\right\rceil \).

Proof ▶

Obvious.

Definition 2.7 Deterministic complexity of a protocol

✓

The communication complexity of a NOF protocol \(P\) for \(F\) is the smallest time \(t\) such that \(P\) is valid in \(F\) at time \(t\) on all inputs \(x\), or \(\infty \) if no such \(t\) exists.

Definition 2.8 Deterministic complexity of a function

✓

The deterministic communication complexity of a function \(F\), denoted \(D(F)\), is the minimum of the communication complexity of \(P\) when \(P\) ranges over all NOF protocols.

Lemma 2.9 Trivial bound on the function complexity

The communication complexity of any function \(F\) is at most \(d\left\lceil \log _2 n\right\rceil \).

Proof ▶

The trivial protocol is a protocol valid in \(F\) in time \(d\left\lceil \log _2 n\right\rceil \).

Lemma 2.10 The tip of a monochromatic forbidden pattern

✓

Given \(P\) a NOF protocol and a time \(t\), if \((a_1, \dots , a_d)\) is a forbidden pattern with tip \(v\) such that \(\operatorname{broad}(a_i, t)\) equals some fixed broadcast history \(b\) for all \(i\), then \(\operatorname{broad}(v, t) = b\) as well.

Proof ▶

Induction on \(t\). TODO: Expand