Q The Query Complexity Zoo
\(G_q\)

Meiburg’s parity-masked majority family

A total square-root-logarithmic separation of linearised from max-conflict complexity.

total composed arity: $N_q=\Theta(q^4\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. Add a parity mask to the majority family: $G_q(x,z)=M_q(x)\oplus\mathrm{XOR}_t(z)$, with $t=\Theta(m_q)$.

Measure values

MeasureValueNotes
\(\mathrm{RS}(f)\) Sabotage complexity \(\Theta(q^3\log q)\) Meiburg26composition
\(\bar{\chi}(f)\) Max-conflict complexity \(\Theta(q^3\log q)\) Meiburg26composition
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\Omega(q^3\log^{3/2}q),\ O(q^3\log^2q)\) Meiburg26composition
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(q^3\log^2q)\) Meiburg26composition

Cited as a witness by

Notes

Theorem 8.3: $\mathrm{LR}(G_q)/\bar\chi(G_q)=\Omega(\sqrt{\log N_q})$. The LR value is a bracket; the paper does not prove a matching upper bound at its lower endpoint.