\(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
| Measure | Value | Notes |
|---|---|---|
| \(\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
-
\(\mathrm{R}(P_q)/\mathrm{RS}(P_q)=\Omega(\log N_q)\)
-
\(\bar\chi(P_q)/\mathrm{RS}(P_q)=\Omega(\log N_q)\)
-
\(\chi(P_q)/\mathrm{RS}(P_q)=\Omega(\log N_q)\)
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.