\(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
| Measure | Value | Notes |
|---|---|---|
| \(\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
-
\(\mathrm{R}^{*}(H_q)=\Theta(\mathrm{R}(H_q)\log\mathrm{R}(H_q))\)
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.