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.
The 4 above are this entry’s hand-picked neighbours; the other 89 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| 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 |