Q The Query Complexity Zoo
\(\mathrm{Corr}_{\varepsilon}(f)\)

Correlated samples complexity

Distributional complexity when the algorithm may query as many independent samples from the same side as it likes.

also written: correlated samples problem, multiple-sample distributional complexity

Definition

Fix an input distribution $D = \tfrac12 D_0 + \tfrac12 D_1$, where $D_b$ is supported on $f^{-1}(b)$; distinguishing $D_0$ from $D_1$ with one sample is exactly the distributional complexity $\mathrm{D}_\varepsilon(f, D)$. Now hand the algorithm $k$ samples drawn from the same side, so that $f^k$ evaluates to $0^k$ or to $1^k$, and let it choose $k$: $$\mathrm{Corr}_\varepsilon(f, D) \;:=\; \min_{k\ge 1}\ \mathrm{D}_\varepsilon\big(f^k,\ \tfrac12 D_0^k + \tfrac12 D_1^k\big), \qquad \mathrm{Corr}_\varepsilon(f) := \max_D \mathrm{Corr}_\varepsilon(f, D).$$ More samples never hurt, so the minimand is non-increasing in $k$, and $k \le n$ is without loss of generality. Unadorned $\mathrm{Corr} := \mathrm{Corr}_{1/3}$.

For a fixed $D$ the extra samples can help enormously; the content of the measure is that against the hardest $D$ they do not.

Parameters

\(\varepsilon\) (eps) default \(1/3\)range \([0, 1/2)\)

Error probability, over the draw of the samples.

Unlike single-sample distributional complexity, this model does admit cheap error reduction: $\mathrm{Corr}_\varepsilon(f, D) \le O(\log(1/\varepsilon)/\delta^2)\cdot \mathrm{Corr}_{1/2-\delta}(f, D)$ (Fact 1 of [BDGHMT20]). Run the weak algorithm on fresh samples and take the majority -- which is legal precisely because all the samples come from the same side. In the single-sample setting the same trick is unavailable, and that failure is the reason $\mathrm{D}_\varepsilon(f,D)$ is so badly behaved at small bias.

Basic facts

  • Theorem 1 of [BDGHMT20]: $\mathrm{Corr}(f) = \Theta(\mathrm{R}(f))$ for every (possibly partial) Boolean $f$. The easy direction is $\mathrm{Corr} \le \mathrm{R}$ (take $k=1$ and apply Yao).
  • Against a fixed distribution the measure genuinely differs: on $\mathrm{XOR}_n$ with Shaltiel's distribution ($0U^{n-1}$ w.p. $99\%$, $1U^{n-2}0$ w.p. $1\%$) one has $\mathrm{D}(\mathrm{XOR}_n, D) = \Omega(n)$ but $\mathrm{Corr}(\mathrm{XOR}_n, D) = O(1)$ -- query the first bit of many samples until an easy one turns up.
  • So Theorem 1 is exactly the statement that Shaltiel examples can be avoided by choosing the distribution well, which is what makes it useful for composition.
  • Lemma 7 of [BDGHMT20]: $\mathrm{Corr}(f, D) = \Theta(\mathrm{biCorr}(f, D))$, the variant where the algorithm must also say which side it thinks the samples came from at every leaf.
  • The application: with $\mathrm{Corr} = \Theta(\mathrm{R})$ in hand, [BDGHMT20] prove $\mathrm{R}(f\circ g) = \Omega(\mathrm{fbs}(f)\mathrm{R}(g))$ -- see comp-R.
  • [BenDavidBlais20minimax] reprove Theorem 1 by a different route (Shaltiel-free minimax theorems), concurrently and independently.

Equivalent / near-equivalent measures

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{Corr}_{\varepsilon}(f)\). “\(\mathrm{Corr}_{\varepsilon}(f)\) in terms of it” is the pair with \(\mathrm{Corr}_{\varepsilon}(f)\) on the left (the matrix row); the other column is the reverse. Each cell gives, per setting, the exponent range a,b of the best bounds known — \(\mathrm{M_1} = \Omega(\mathrm{M_2}^{a})\) below and \(\mathrm{M_1} = O(\mathrm{M_2}^{b})\) above, so \(a = b\) means settled — or a glyph where no polynomial bound exists at all. These are derived, not just read off the exponent table, so they are present for pairs the table does not cover. A cell with no entry for a setting is one where the zoo has nothing at that setting, and a — one where the ordered pair is empty in all three; derived marks a direction with no hand-written relation record behind it, which is the common case and not a hole.

Other measure \(\mathrm{Corr}_{\varepsilon}(f)\) in terms of it It in terms of \(\mathrm{Corr}_{\varepsilon}(f)\)
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity total1,1 partial1,1 open pair → total1,1 partial1,1 derived open pair →
\(\mathrm{Sel}_{\varepsilon}(f)\) Selection complexity total1,1 partial1,1 open pair → total1,1 partial1,1 derived open pair →
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity total1,1 partial1,1 derived open pair → total1,1 partial1,1 derived open pair →
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity total1.1,3 partialexp,? derived open pair → total1,1 partial1,1 derived open pair →

The 4 above are this entry’s hand-picked neighbours; the other 89 are everything else in the zoo, by category.