Q The Query Complexity Zoo
\(H_q\)

Meiburg’s maximal composition-rate separation

$\mathrm{R}^{*}/\mathrm{R}=\Theta(\log\mathrm{R})$, the maximal logarithmic gap.

total composed arity: $N_q=\Theta(q^6\log q)$ bits

Description

The encoded pointer block $g_q$ is the succinct total pointer function in [Meiburg26composition, Section 3], with an exact one-sided detector. Write $m_q=q^3\log q$; $q$ is odd for the majority families. Let $A_q=\mathrm{AND}_{q^2}\circ\mathrm{MAJ}_q$, on $q^3$ bits. The rotated composition is $H_q=g_q\circ A_q$.

Measure values

MeasureValueNotes
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(q^5\log q)\) Meiburg26composition
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate \(\Theta(q^5\log^2 q)\) Meiburg26composition

Cited as a witness by

Notes

Theorem 10.7: $\mathrm{R}^{*}(H_q)/\mathrm{R}(H_q)=\Theta(\log q)=\Theta(\log N_q)=\Theta(\log\mathrm{R}(H_q))$. Here the limit exceeds one-level randomized complexity.