Meiburg’s total noisy-query separation
Total functions with $\mathrm{R}/\mathrm{noisyR}=\Omega((\log N)^{1/4}/\log\log\log N)$.
total composed arity: $\log N_q=\Theta(q^4)$
Description
The certificate-array totalization of an AND-of-ORs of approximate-index seed problems, using short encoded certificates and a large address table [Meiburg26composition, Section 4].
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity | \(\Omega(q^{11}\log q)\) | Theorem 4.1: substitute u_q=Θ(q^4) and ℓ_q=Θ(log q) in its lower bound. Meiburg26composition |
| \(\mathrm{noisyR}(f)\) Noisy randomized query complexity | \(O(q^{10}\log q\log\log q)\) | Theorem 4.1: its upper bound is O(ℓ_q log(ℓ_q+2) u_q² q²). Meiburg26composition |
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. 1 in total.
-
\(\mathrm{R}_{\varepsilon}(f_n) = \Omega\big(\mathrm{noisyR}(f_n)^{1.1}\big)\)from \(\mathrm{R}_{\varepsilon}(f) = \Omega(q^{11}\log q)\) against \(\mathrm{noisyR}(f) = O(q^{10}\log q\log\log q)\)
Cited as a witness by
-
\(\mathrm{R}(W_q)/\mathrm{noisyR}(W_q)=\Omega((\log N_q)^{1/4}/\log\log\log N_q)\)
Notes
The separation is polylogarithmic in input size, since $\log N_q=\Theta(q^4)$. It refutes constant-factor equality on total functions while remaining consistent with $\mathrm{R}=O(\mathrm{noisyR}\log(N_q+1))$ [PednekarPodder26STOC].