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

Selection complexity

Cost of solving any one of k independent instances, with k chosen by the algorithm and the instances drawn from the hardest distribution.

also written: selection problem, choose problem

Definition

In the $k$-selection problem for $(f, D)$ the input is $x = (x^1,\dots,x^k) \sim D^k$ and the algorithm must output a pair $(i, f(x^i))$ for some $i$ of its choosing: it picks which instance to be graded on. Writing $k\text{-}\mathrm{Sel}_\varepsilon(f,D)$ for the query complexity of that task, $$\mathrm{Sel}_\varepsilon(f, D) := \min_{k\ge1} k\text{-}\mathrm{Sel}_\varepsilon(f, D), \qquad \mathrm{Sel}_\varepsilon(f) := \max_D \mathrm{Sel}_\varepsilon(f, D).$$ The communication-complexity ancestor of the problem is choose [BBKW14].

Parameters

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

Error probability.

Selection admits no efficient error reduction, in contrast to \(\mathrm{Corr}_{\varepsilon}(f)\): item 3 of Theorem 2 of [BDGHMT20]. Having many instances does not help you check an answer, because the instance you would re-solve is the one you already found hard.

Basic facts

  • Corollary 1 of [BDGHMT20]: $\mathrm{Sel}(f) = \Theta(\mathrm{R}(f))$ for every (possibly partial) Boolean $f$. Being allowed to duck the hard instances is worth nothing against the hardest distribution.
  • Pointwise in the distribution, selection is the harder task: $\mathrm{Corr}(f, D) = O(\mathrm{Sel}(f, D))$ for every $(f,D)$ (Theorem 2.1), and there are $(f,D)$ with $\mathrm{Sel}(f,D) = \Omega(n)$ while $\mathrm{Corr}(f,D) = O(1)$ (Theorem 2.2).
  • Like \(\mathrm{Corr}_{\varepsilon}(f)\), it is subject to Shaltiel examples at a fixed distribution: $\mathrm{Sel}(\mathrm{XOR}_n, D) = O(1)$ for the same $D$, by hunting for an easy instance.
  • The distribution-free collapse $\mathrm{Sel} = \Theta(\mathrm{R})$ is a corollary of $\mathrm{Corr} = \Theta(\mathrm{R})$, not an independent argument.

Equivalent / near-equivalent measures

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{Sel}_{\varepsilon}(f)\). “\(\mathrm{Sel}_{\varepsilon}(f)\) in terms of it” is the pair with \(\mathrm{Sel}_{\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{Sel}_{\varepsilon}(f)\) in terms of it It in terms of \(\mathrm{Sel}_{\varepsilon}(f)\)
\(\mathrm{Corr}_{\varepsilon}(f)\) Correlated samples complexity total1,1 partial1,1 derived open pair → total1,1 partial1,1 open pair →
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query 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 →

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