183 Communication Complexity — Lower Bound
183.1 Overview
This module proves the linear public-coin one-way lower bound of Kremer–Nisan–Ron for the Index problem \(\mathrm{IND}_n\) via Yao’s distributional method, with fully explicit constants: for \(n \ge 300\), every public-coin one-way protocol for Index with error \(1/9\) must communicate more than \(n/10\) bits. The argument counts, for a deterministic one-way protocol, the “answer vectors” \(a(m) \in \{ 0,1\} ^n\) realised by its messages, shows that most of Alice’s inputs are far (in Hamming distance) from every answer vector, and converts this into a distributional error bound under the uniform distribution on pairs \((x,i)\).
183.2 Declarations
For a deterministic one-way protocol \(p\) for Index on \(n\) bits and a message \(m\) of \(p\), the answer vector \(a(m) \in \{ 0,1\} ^n\) is the string whose \(i\)-th coordinate is Bob’s output \(\mathrm{decode}(m, i)\) on receiving \(m\) with index \(i\).
The answer set \(A\) of a one-way protocol \(p\) is the finite set of all answer vectors \(a(m)\) as \(m\) ranges over the messages of \(p\), i.e. the image of the message type under CommunicationComplexity.Functions.Indexing.answerVector.
Alice’s input \(x \in \{ 0,1\} ^n\) is bad for the protocol \(p\) if there is no answer vector \(a \in A\) with \(d_H(x, a) \lt n/4\), where the radius \(n/4\) is the real number (not its floor). Equivalently, every realisable answer vector is at Hamming distance at least \(n/4\) from \(x\).
For a fixed input string \(x\), the type of indices \(i \in [n]\) on which the protocol \(p\) errs, i.e. the subtype \(\{ \, i : \mathrm{Fin}\, n \mid p.\mathrm{run}(x, i) \ne \mathrm{IND}_n(x, i) \, \} \).
The type of input pairs \((x, i) \in \{ 0,1\} ^n \times [n]\) on which the protocol \(p\) is incorrect, i.e. the subtype of pairs with \(p.\mathrm{run}(x, i) \ne \mathrm{IND}_n(x, i)\).
The equivalence between the type of incorrect pairs \((x, i)\) of \(p\) and the dependent sum \(\Sigma _{x \in \{ 0,1\} ^n}\, \mathrm{mismatch}(p, x)\) of the per-input mismatch index types, given by \(((x, i), h) \mapsto (x, (i, h))\).
For a fixed input string \(x\), the number of indices \(i\) on which \(p\) errs equals the Hamming distance between \(x\) and the answer vector of Alice’s message on \(x\):
The number of incorrect input pairs \((x, i)\) of \(p\) equals the sum, over all strings \(x \in \{ 0,1\} ^n\), of the number of indices \(i\) on which \(p\) errs at \(x\):
A one-way protocol \(p\) of cost \(c\) realises at most \(2^c\) distinct answer vectors: \(\left\lvert A\right\rvert \le 2^{p.\mathrm{cost}}\).
If \(x\) is a bad input for \(p\), then the Hamming distance from \(x\) to the answer vector of its own message satisfies \(d_H\bigl(x, a(\mathrm{send}(x))\bigr) \ge n/4\) (as real numbers).
Let \(p\) be a deterministic one-way protocol for \(\mathrm{IND}_n\). If at least \(2^{n-1}\) of Alice’s \(2^n\) inputs are bad for \(p\) (no answer vector of \(p\) lies within Hamming distance \(n/4\)), then the distributional error of \(p\) on \(\mathrm{IND}_n\) under the uniform distribution on pairs \((x, i)\) is at least \(1/8\).
For natural numbers \(n, i\) with \(i \lt \lfloor n/4 \rfloor \), one has \(3 \binom {n}{i} \le \binom {n}{i+1}\).
For every \(n\) and every centre \(a \in \{ 0,1\} ^n\), the Hamming ball of radius \(\lfloor n/4 \rfloor \) around \(a\) satisfies
(as real numbers).
The real number \(e = \exp (1)\) satisfies \(e \le 68/25 = 2.72\).
For every natural number \(n \ge 300\), the real ratio \(n / \lfloor n/4 \rfloor \) is at most \(101/25 = 4.04\).
For every natural number \(n \ge 300\),
Let \(\mathrm{good}\) be the set of inputs \(x \in \{ 0,1\} ^n\) that are not bad for \(p\) (those within Hamming distance \(\lt n/4\) of some answer vector). Then
where \(A\) is the answer set of \(p\).
If \(n \ge 300\) and the deterministic one-way protocol \(p\) for \(\mathrm{IND}_n\) has cost at most \(\lfloor n/10 \rfloor \), then at least \(2^{n-1}\) of the \(2^n\) inputs \(x \in \{ 0,1\} ^n\) are bad for \(p\) (no answer vector of \(p\) lies within Hamming distance \(n/4\) of \(x\)).
For \(n \ge 300\), every deterministic one-way protocol \(p\) for \(\mathrm{IND}_n\) with \(p.\mathrm{cost} \le \lfloor n/10 \rfloor \) has distributional error strictly greater than \(1/9\) under the uniform distribution on pairs \((x, i)\).
For a real \(\varepsilon \) and a natural number \(c\), the proposition that every deterministic one-way protocol \(p\) for \(\mathrm{IND}_n\) with \(p.\mathrm{cost} \le c\) has distributional error strictly greater than \(\varepsilon \) under the uniform input distribution CommunicationComplexity.Functions.Indexing.indexingInputDist. This is the hypothesis of the easy direction of Yao’s minimax principle for one-way protocols, specialised to Index.
For \(n \ge 300\), the predicate CommunicationComplexity.Functions.Indexing.deterministicOneWayDistributionalLowerBound holds at error \(\varepsilon = 1/9\) and cost budget \(c = \lfloor n/10 \rfloor \): every deterministic one-way protocol for \(\mathrm{IND}_n\) of cost at most \(\lfloor n/10 \rfloor \) has uniform-distributional error greater than \(1/9\).
If every deterministic one-way protocol for \(\mathrm{IND}_n\) of cost at most \(c\) has uniform-distributional error greater than \(\varepsilon \), then the public-coin one-way communication complexity of \(\mathrm{IND}_n\) at error \(\varepsilon \) is strictly greater than \(c\) (as an extended natural number). This is the easy direction of Yao’s minimax principle for one-way protocols, applied to Index.
If every deterministic one-way protocol for \(\mathrm{IND}_n\) of cost at most \(\lfloor n/10 \rfloor \) has uniform-distributional error greater than \(1/8\), then the public-coin one-way communication complexity of \(\mathrm{IND}_n\) at error \(1/8\) is strictly greater than \(\lfloor n/10 \rfloor \). This is the previous theorem specialised to the source’s constants \(\varepsilon = 1/8\), \(c = \lfloor n/10 \rfloor \).
For \(n \ge 300\), the public-coin one-way communication complexity of \(\mathrm{IND}_n\) at error \(1/9\) is strictly greater than \(\lfloor n/10 \rfloor \):
This is the Kremer–Nisan–Ron linear lower bound with explicit constants.