Q The Query Complexity Zoo
\(P_q\)

Meiburg’s parity-pointer family

A total logarithmic separation of sabotage from conflict, max-conflict, linearised and randomized 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 parity family is $P_q=\mathrm{XOR}_q\circ g_q^q$.

Measure values

MeasureValueNotes
\(\mathrm{RS}(f)\) Sabotage complexity \(O(q^3\log q)\) Meiburg26composition
\(\chi(f)\) Conflict complexity \(\Theta(q^3\log^2 q)\) Meiburg26composition
\(\bar{\chi}(f)\) Max-conflict complexity \(\Theta(q^3\log^2 q)\) Meiburg26composition
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\Theta(q^3\log^2 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 7.5: $\chi(P_q)/\mathrm{RS}(P_q)=\Omega(\log N_q)$. The same family separates each of the larger measures from sabotage.