Q The Query Complexity Zoo
\(M_q\)

Meiburg’s majority-pointer family

A total logarithmic separation of randomized from linearised query 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. The majority family is $M_q=\mathrm{MAJ}_q\circ g_q^q$.

Measure values

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

Cited as a witness by

Notes

Theorem 3.5: $\mathrm{R}(M_q)/\mathrm{LR}(M_q)=\Omega(\log N_q)$. The bounds on the smaller measures are upper bounds, not asserted equalities.