Correlated-string search
The GLSS19 relational counterexample to composition: $\mathrm{R}=\Theta(\sqrt n)$ but $\mathrm{noisyR}=\Theta(1)$, adaptively and non-adaptively.
relation relational arity: $n$ bits in, $n$ bits out
Description
Given $x \in \{0,1\}^n$, output any $y \in \{0,1\}^n$ with $|x - y| \le n/2 - \sqrt n$, i.e. any string that agrees with $x$ on at least $n/2 + \sqrt n$ coordinates. Total: $y = x$ always works.
Guessing at random gives agreement $n/2 \pm O(\sqrt n)$, so the task is to beat a coin flip by exactly one standard deviation. That is cheap if you are allowed to be a little bit right about every coordinate, and expensive if you have to be exactly right about a few of them -- which is the whole point of the example.
Formal definition
$\{(x,y) : |x \oplus y| \le n/2 - \sqrt n\} \subseteq \{0,1\}^n \times \{0,1\}^n$.
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity | \(\Theta(\sqrt n)\) | Query a uniformly random set $S$ of $c\sqrt n$ coordinates, copy $x$ on $S$ and flip fair coins elsewhere: the distance is $\mathrm{Bin}(n-|S|,1/2) \approx n/2 - c\sqrt n/2$ with deviation $O(\sqrt n)$, so a large enough constant $c$ works. The matching $\Omega(\sqrt n)$ is [GLSS19]. GLSS19 |
| \(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity | \(\Theta(\sqrt n)\) putative | The algorithm above never looks at an answer before choosing the next query, so it is non-adaptive; and $\mathrm{R}^{\mathrm{na}} \ge \mathrm{R} = \Omega(\sqrt n)$. |
| \(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity | \(\Theta(\sqrt n)\) | $\bar{\mathrm{R}}_\varepsilon = \Theta(\mathrm{R}_\varepsilon)$ at constant $\varepsilon$. |
| \(\mathrm{noisyR}(f)\) Noisy randomized query complexity | \(\Theta(1)\) | Buy every coordinate at bias $c/\sqrt n$ and set $y$ to the answers: total cost $n \cdot c^2/n = c^2 = O(1)$, and the expected agreement is $n/2 + c\sqrt n/2$, one standard deviation past the promise for large enough $c$. The lower bound $\Omega(1)$ is Lemma 37 of [BenDavidBlais20composition], which applies because $x=0^n$ and $x=1^n$ have disjoint sets of allowed outputs. BenDavidBlais20composition GLSS19 |
| \(\mathrm{noisyR}^{\mathrm{na}}(f)\) Non-adaptive noisy randomized query complexity | \(\Theta(1)\) | That algorithm commits to all $n$ biases in advance, so the non-adaptive cost is $O(1)$ too; and $\mathrm{noisyR}^{\mathrm{na}} \ge \mathrm{noisyR} = \Omega(1)$. This is exactly the family that makes Theorem 8 false for relations. BenDavidBlais20composition |
| \(\mathrm{D}(f)\) Deterministic query complexity | \(\Theta(n)\) putative | Sharply $\lceil n/2 + \sqrt n\rceil$. Upper: copy $x$ on the queried coordinates and put $0$ elsewhere. Lower: after $q$ queries the output $y$ is determined, and the adversary sets every unqueried $x_i := 1 - y_i$, forcing distance $n-q$; validity needs $n - q \le n/2 - \sqrt n$. |
| \(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity | \(\Theta(n)\) putative | The deterministic algorithm above is non-adaptive, and the adversary argument does not care about adaptivity. |
| \(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity | \(\Theta(n)\) putative | The adversary argument applies to every tree in the support of a zero-error algorithm and to every leaf of it, so all leaves sit at depth $\ge n/2 + \sqrt n$ and even the expected cost is $\Omega(n)$. So $\mathrm{R}_0/\mathrm{R} = \Theta(\sqrt n)$ here: a second unbounded gap, for the same reason as at \(\mathrm{ApproxHW}\) -- there is no witness to verify. |
| \(\mathrm{C}(f)\) Certificate complexity | \(\Theta(n)\) putative | A partial assignment fixing $q$ coordinates forces a valid answer only if some $y$ works for all $2^{n-q}$ completions, and the worst completion is at distance $n-q$ from $y$; so $q \ge n/2 + \sqrt n$, and that many suffice. |
| \(\mathrm{C}_{\min}(f)\) Minimum certificate complexity | \(\Theta(n)\) putative | The count above is input-independent, so $\mathrm{C}_{\min} = \mathrm{C} = \Theta(n)$. |
| \(\mathrm{cbs}(S)\) Critical block sensitivity | \(0\) putative | No input has a unique valid answer -- there are $\binom{n}{\le n/2-\sqrt n}$ of them -- so there are no critical inputs and the maximum in the definition of \(\mathrm{cbs}(S)\) is empty. As at \(\mathrm{ApproxHW}\), the standard route to relational lower bounds is unavailable and [GLSS19] had to argue directly. |
| \(\mathrm{N}_{p}(f)\) Noisy decision tree complexity | \(\Theta(\sqrt n)\) putative | At constant noise rate $p$: read $c\sqrt n$ random coordinates once each and copy the (possibly corrupted) answers, guessing elsewhere. Expected agreement $n/2 + c(1/2-p)\sqrt n$, so $O(\sqrt n)$ noisy queries suffice, and $\mathrm{N}_p \ge \mathrm{R} = \Omega(\sqrt n)$. Note the contrast with $\mathrm{noisyR} = \Theta(1)$: the faulty-oracle model charges $1$ per query whatever the bias, and that single convention is the entire difference. |
| \(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity | \(O(\sqrt n)\) | At most $\mathrm{R}$. No better quantum algorithm is recorded here, and no lower bound beyond $\Omega(1)$. |
Separations its values prove — computed, not recorded
Read straight off the table above by comparing two values: no relation record states these, and where one does and says more, the record wins and the pair is not listed here. 12 in total.
-
\(\mathrm{R}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{cbs}(S)(f_n) = O(1)\)from \(\mathrm{R}_{\varepsilon}(f) = \Theta(\sqrt n)\) against \(\mathrm{cbs}(S) = 0\)
-
\(\bar{\mathrm{R}}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{noisyR}(f_n) = O(1)\)from \(\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(\sqrt n)\) against \(\mathrm{noisyR}(f) = \Theta(1)\)
-
\(\mathrm{N}_{p}(f_n) \to \infty \ \text{ while } \ \mathrm{noisyR}^{\mathrm{na}}(f_n) = O(1)\)from \(\mathrm{N}_{p}(f) = \Theta(\sqrt n)\) against \(\mathrm{noisyR}^{\mathrm{na}}(f) = \Theta(1)\)
-
\(\mathrm{R}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{noisyR}(f_n) = O(1)\)from \(\mathrm{R}_{\varepsilon}(f) = \Theta(\sqrt n)\) against \(\mathrm{noisyR}(f) = \Theta(1)\)
-
\(\bar{\mathrm{R}}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{cbs}(S)(f_n) = O(1)\)from \(\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(\sqrt n)\) against \(\mathrm{cbs}(S) = 0\)
-
\(\mathrm{R}^{\mathrm{na}}(f_n) \to \infty \ \text{ while } \ \mathrm{noisyR}^{\mathrm{na}}(f_n) = O(1)\)from \(\mathrm{R}^{\mathrm{na}}(f) = \Theta(\sqrt n)\) against \(\mathrm{noisyR}^{\mathrm{na}}(f) = \Theta(1)\)
-
\(\mathrm{R}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{noisyR}^{\mathrm{na}}(f_n) = O(1)\)from \(\mathrm{R}_{\varepsilon}(f) = \Theta(\sqrt n)\) against \(\mathrm{noisyR}^{\mathrm{na}}(f) = \Theta(1)\)
-
\(\mathrm{N}_{p}(f_n) \to \infty \ \text{ while } \ \mathrm{cbs}(S)(f_n) = O(1)\)from \(\mathrm{N}_{p}(f) = \Theta(\sqrt n)\) against \(\mathrm{cbs}(S) = 0\)
-
\(\mathrm{R}^{\mathrm{na}}(f_n) \to \infty \ \text{ while } \ \mathrm{noisyR}(f_n) = O(1)\)from \(\mathrm{R}^{\mathrm{na}}(f) = \Theta(\sqrt n)\) against \(\mathrm{noisyR}(f) = \Theta(1)\)
-
\(\bar{\mathrm{R}}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{noisyR}^{\mathrm{na}}(f_n) = O(1)\)from \(\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(\sqrt n)\) against \(\mathrm{noisyR}^{\mathrm{na}}(f) = \Theta(1)\)
-
\(\mathrm{N}_{p}(f_n) \to \infty \ \text{ while } \ \mathrm{noisyR}(f_n) = O(1)\)from \(\mathrm{N}_{p}(f) = \Theta(\sqrt n)\) against \(\mathrm{noisyR}(f) = \Theta(1)\)
-
\(\mathrm{R}^{\mathrm{na}}(f_n) \to \infty \ \text{ while } \ \mathrm{cbs}(S)(f_n) = O(1)\)from \(\mathrm{R}^{\mathrm{na}}(f) = \Theta(\sqrt n)\) against \(\mathrm{cbs}(S) = 0\)
Separations it witnesses
-
Unbounded: $\mathrm{noisyR} = \Theta(1)$ against $\mathrm{R} = \Theta(\sqrt n)$. This is the relational barrier of [BenDavidBlais20composition]: any measure $M$ with $\mathrm{noisyR} = \Omega(M)$ must either be $O(1)$ on this family -- and hence a poor lower bound on $\mathrm{R}$ -- or must use the fact that $f$ is a function.
-
Unbounded: $\mathrm{noisyR}^{\mathrm{na}} = \Theta(1)$ against $\mathrm{R}^{\mathrm{na}} = \Theta(\sqrt n)$, so Theorem 8 ($\mathrm{R}^{\mathrm{na}} = \Theta(\mathrm{noisyR}^{\mathrm{na}})$ for partial Boolean functions) is false for relations. Its proof must therefore notice Boolean-ness somewhere, and it does: the step that fails is the passage from error probability to relative entropy.
-
Unbounded: $\mathrm{R} = \Theta(\sqrt n)$ against $\mathrm{R}_0 = \Theta(n)$.
Cited as a witness by
-
\(\mathrm{noisyR}(\mathrm{AGREE}_n) = \Theta(1) \text{ while } \mathrm{R}(\mathrm{AGREE}_n) = \Theta(\sqrt n)\)
-
\(\mathrm{R}^{\mathrm{na}}(f)\) vs \(\mathrm{noisyR}^{\mathrm{na}}(f)\) relation No bound exists open →\(\mathrm{noisyR}^{\mathrm{na}}(\mathrm{AGREE}_n) = \Theta(1) \text{ while } \mathrm{R}^{\mathrm{na}}(\mathrm{AGREE}_n) = \Theta(\sqrt n)\)