Dependencies

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

The \(d\)-dimensional corner-coloring number of \(G\), denoted \(\chi _d(G)\), is the smallest number of colors one needs to color \(G^d\) such that no non-trivial \(d\)-dimensional corner is monochromatic.

The \(d\)-dimensional corner-free number of \(G\), denoted \(r_d(G)\) is the size of the largest set \(A\) in \(G^d\) such that \(A\) doesn’t contain a non-trivial corner.

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.

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.

The \(\operatorname{eval}\) function is defined by

We say a tuple \((a_1, \dots , a_d) : (G^d)^d\) is a forbidden pattern with tip \(v : G^d\) if

for all \(i, j\) distinct. We also simply say \((a_1, \dots , a_d)\) is a forbidden pattern if it is a forbidden pattern with tip \(v\) for some \(v\).

For an index \(i : [d]\), we define

A multidimensional corner in \(d\) dimensions is a tuple of the form \((x, x + ce_1, \dots , x + ce_d)\) for some \(x : G^d\) and \(c : G\), where \(ce_i\) is the vector of all zeroes except in position \(i\) where it is \(c\). Such a corner is said to be trivial if \(c = 0\).

Given a coloring \(c : \{ x \mid \operatorname{eval}x = 1\} \to [C]\), writing \(a_i\) the vector whose \(j\)-th coordinate is \(x_j\) except when \(j = i\) in which case it is \(-\sum _{j \ne i} x_j\), we define the non-monochromatic protocol for \(c\) by making participant \(i\) do “Send the \(t / d\)-th bit of \(c(a_i)\) until time \(\lceil \log _2\chi _d(G)\rceil \), then send \(1\) iff \(c(a_i)\) agrees with the broadcast from time \(1\) to time \(\lceil \log _2\chi _d(G)\rceil \) read as a color” and “Send \(1\) iff the broadcasts from time \(\lceil \log _2\chi _d(G)\rceil \) to time \(\lceil \log _2\chi _d(G)\rceil + d\) were all \(1\)”.

A NOF protocol \(P\) consists of maps

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.

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

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\)”.

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

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

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)\)".

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

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

If \((a_1, \dots , a_d)\) is a forbidden pattern such that \(\operatorname{eval}(a_i) = 1\) for all \(i\), then

is a multidimensional corner for all index \(i\).

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

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.

Given \(P\) a NOF protocol valid in time \(t\) for \(\operatorname{eval}\), all monochromatic forbidden patterns are trivial.

If \(c\) is a coloring such that all monochromatic forbidden patterns are trivial, then the non-monochromatic protocol for \(c\) is valid in time \(\lceil \log _2\chi _d(G)\rceil + d\).

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

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

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