Q The Query Complexity Zoo
\(\mathrm{noisyR}^{\mathrm{na}}(f)\)

Non-adaptive noisy randomized query complexity

The bias-purchasing model with the whole schedule of biases committed to in advance.

Definition

As \(\mathrm{noisyR}(f)\), but non-adaptively: the algorithm draws, from a distribution of its choosing, a vector of biases $(\gamma_1,\dots,\gamma_n)$; it then receives one copy of each $x_i$ through a binary symmetric channel of bias $\gamma_i$, all at once, and must output an answer. The cost is $\sum_i \gamma_i^2$ and the error must be at most $1/3$.

Setting every $\gamma_i \in \{0,1\}$ recovers \(\mathrm{R}^{\mathrm{na}}(f)\), so $\mathrm{noisyR}^{\mathrm{na}} \le \mathrm{R}^{\mathrm{na}}$.

Basic facts

  • Theorem 8 of [BenDavidBlais20composition]: $\mathrm{noisyR}^{\mathrm{na}}(f) = \Theta(\mathrm{R}^{\mathrm{na}}(f))$ for every (possibly partial) Boolean $f$. Non-adaptively, buying cheap bias buys nothing at all.
  • This is false for relations: on the \(\mathrm{AGREE}_n\) family of [GLSS19], $\mathrm{noisyR}^{\mathrm{na}} = O(1)$ while $\mathrm{R}^{\mathrm{na}} = \Omega(\sqrt n)$. The proof of Theorem 8 therefore has to "notice" that $f$ is a function, which is unusual in query complexity.
  • The adaptive analogue is exactly Is …?, and is false as an exact $\Theta$ for partial $f$ (\(\mathrm{ApproxIndex}_k\)).
  • The proof goes through Samorodnitsky's inequality [Samorodnitsky16, PolyanskiyWu17]: a noisy copy at bias $\rho$ tells you at least as much about $f(X)$ as an erasure copy that survives with probability $\rho^2$. Erasures are honest queries, so the noisy budget can be converted into a query budget -- and it is the entropy-to-error step (Fano / [HellmanRaviv70]) that breaks for relations.

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{noisyR}^{\mathrm{na}}(f)\). “\(\mathrm{noisyR}^{\mathrm{na}}(f)\) in terms of it” is the pair with \(\mathrm{noisyR}^{\mathrm{na}}(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{noisyR}^{\mathrm{na}}(f)\) in terms of it It in terms of \(\mathrm{noisyR}^{\mathrm{na}}(f)\)
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity totalexp,? partialexp,? relationexp,? open pair → total1,1 partial1,1 relation1,1 open pair →
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity total1,1 partial1,1 relation1,1 open pair → total1,1 partial1,1 relation∞ open pair →
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity totalexp,? partialexp,? relationexp,? derived open pair → total1,1 partial1,1 relation∞ derived open pair →
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity total1,1 partial1,1 relation1,1 derived open pair → total1,? partial∞ relation∞ derived open pair →

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

Known values

FunctionValueNotes
OR total \(\Theta(n)\) By Theorem 8, $\mathrm{noisyR}^{\mathrm{na}} = \Theta(\mathrm{R}^{\mathrm{na}})$ for every partial Boolean function. Buying $n$ coordinates at bias $\gamma$ costs $n\gamma^2$, and distinguishing $0^n$ from a random $e_i$ needs $\gamma = \Omega(1)$ on the special coordinate, which a non-adaptive schedule cannot aim at. BenDavidBlais20composition
ADDRESS / multiplexer total \(\Theta(2^k)\) Theorem 8: $\mathrm{noisyR}^{\mathrm{na}} = \Theta(\mathrm{R}^{\mathrm{na}})$ for partial Boolean functions. Against $\mathrm{noisyR} \le \mathrm{R} = \Theta(k)$, this is an exponential separation between the adaptive and non-adaptive noisy models -- adaptivity is what lets the algorithm aim its bias budget at the addressed cell, exactly as in the noiseless case. BenDavidBlais20composition
Deutsch-Jozsa partial \(\Theta(1)\) Squeezed: $\mathrm{noisyR} = \Theta(1) \le \mathrm{noisyR}^{\mathrm{na}} \le \mathrm{R}^{\mathrm{na}} = \Theta(1)$. Also what Theorem 8 of [BenDavidBlais20composition] predicts -- $\mathrm{noisyR}^{\mathrm{na}} = \Theta(\mathrm{R}^{\mathrm{na}})$ holds for partial functions. BenDavidBlais20composition
Unstructured search (relation) relation \(\Theta(n)\) Squeezed: $\mathrm{noisyR} = \Theta(n) \le \mathrm{noisyR}^{\mathrm{na}} \le \mathrm{R}^{\mathrm{na}} = \Theta(n)$. Theorem 8 of [BenDavidBlais20composition] is unavailable here -- it fails for relations, see \(\mathrm{AGREE}_n\) -- but nothing is lost by committing to the biases in advance at the top of the range.
FIND-1 under a density promise relation \(\Theta(1)\) Squeezed: $\mathrm{noisyR} = \Theta(1) \le \mathrm{noisyR}^{\mathrm{na}} \le \mathrm{R}^{\mathrm{na}} = \Theta(1)$. Against $\mathrm{psD} = \Theta(n)$ this is an unbounded gap: committing to a canonical answer is what is expensive, not adaptivity or query strength.
Approximate Hamming weight relation \(\Theta(1)\) Squeezed: $\mathrm{noisyR} = \Theta(1) \le \mathrm{noisyR}^{\mathrm{na}} \le \mathrm{R}^{\mathrm{na}} = \Theta(1)$. Against $\mathrm{C}^1 = \mathrm{rank} = \mathrm{psD} = \Theta(n)$ this is an unbounded gap in each case -- the cheapest relational witness the zoo has for those three against the non-adaptive noisy model.
Correlated-string search relation \(\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
SearchCNF relation \(\Theta(1)\) Squeezed: $\mathrm{noisyR} = \Theta(1) \le \mathrm{noisyR}^{\mathrm{na}} \le \mathrm{R}^{\mathrm{na}} = \Theta(1)$.
Gap-Majority partial \(\Theta(\min(n, 1/\delta^2))\) Squeezed between $\mathrm{noisyR}$ and $\mathrm{R}^{\mathrm{na}}$, which coincide here; equivalently, Theorem 8 of [BenDavidBlais20composition] applied to a partial function. Every corner of the square -- adaptive or not, noisy or not -- costs $\Theta(\min(n,1/\delta^2))$, which is part of what makes $\mathrm{GapMaj}$ the right universal inner function. BenDavidBlais20composition
Gap-Majority at constant gap partial \(\Theta(1)\) Every corner of the adaptive/noisy square costs $\Theta(1)$ here. BenDavidBlais20composition