Max-conflict complexity
A strengthening of conflict complexity that dominates sabotage complexity.
Definition
The "max" version of conflict complexity of Gavinsky-Lee-Santha-Sanyal: the adversary may choose the hard distribution pair after seeing the algorithm's behaviour, yielding a larger and better-behaved measure.
Basic facts
- $\mathrm{R}(f\circ g^n) = \Omega(\mathrm{R}(f)\,\bar{\chi}(g))$ [GLSS19].
- $\bar{\chi}(g) = \Omega(\sqrt{\mathrm{R}(g)})$ even for partial $g$ [GLSS19, Thm 6] -- proved there for the smaller measure $\chi$, so it holds a fortiori for $\bar\chi$.
- $\bar{\chi}(g) = \Omega(\mathrm{RS}(g))$ for all partial $g$ [GLSS19, Thm 7]. The two facts together make the gap unbounded on partial functions: the collision problem has $\mathrm{RS} = \Theta(1)$ but $\mathrm{R} = \Theta(\sqrt n)$, hence $\bar\chi = \Omega(n^{1/4})$. Not being able to collapse that way is the whole point of the measure.
- Ordering: $\mathrm{RS} \lesssim \bar{\chi} \lesssim \mathrm{LR} \lesssim \mathrm{R}$; no asymptotic separation among the first three is known for total functions.
- Total families separate $\bar\chi$ from sabotage by $\Omega(\log N)$ and linearised complexity from $\bar\chi$ by $\Omega(\sqrt{\log N})$ [Meiburg26composition]; see \(P_q\) and \(G_q\).
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\bar{\chi}(f)\). “\(\bar{\chi}(f)\) in terms of it” is the pair with \(\bar{\chi}(f)\) on the left (the matrix row); the other column is the reverse. Each cell gives, per setting, the exponent range a,b of the best bounds known — \(\mathrm{M_1} = \Omega(\mathrm{M_2}^{a})\) below and \(\mathrm{M_1} = O(\mathrm{M_2}^{b})\) above, so \(a = b\) means settled — or a glyph where no polynomial bound exists at all. These are derived, not just read off the exponent table, so they are present for pairs the table does not cover. A cell with no entry for a setting is one where the zoo has nothing at that setting, and a — one where the ordered pair is empty in all three; derived marks a direction with no hand-written relation record behind it, which is the common case and not a hole.
The 4 above are this entry’s hand-picked neighbours; the other 89 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| OR total | \(\Theta(n)\) | Sandwiched: $\mathrm{s}^0(f) \le \bar{\chi}(f) \le \mathrm{D}(f)$, with both ends $n$ here. |
| AND total | \(\Theta(n)\) | Sandwiched: $\mathrm{s}^1(f) \le \bar{\chi}(f) \le \mathrm{D}(f)$, with both ends $n$ here. |
| PARITY total | \(\Theta(n)\) | Sandwiched: $\mathrm{s}(f) \le \bar{\chi}(f) \le \mathrm{D}(f)$, with both ends $n$ here. |
| MAJORITY total | \(\Theta(n)\) | Sandwiched: $\mathrm{RS}(f) \le \bar{\chi}(f) \le \mathrm{D}(f)$, with $\mathrm{RS}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here. |
| Threshold total | \(\Theta(n)\) | Squeezed: $\mathrm{RS}(f) = O(\bar{\chi}(f))$ and $\bar{\chi}(f) = O(\mathrm{R}(f))$, with both ends $\Theta(n)$. GLSS19 |
| Symmetric functions (general) total | \(\Theta(n)\) | Sandwiched: $\mathrm{RS}(f) = O(\bar{\chi}(f))$ and $\bar{\chi}(f) = O(\mathrm{R}(f))$, with both ends $\Theta(n)$ here. GLSS19 |
| EXACT-HALF total | \(\Theta(n)\) | Sandwiched: $\mathrm{s}^1(f) \le \bar{\chi}(f) \le \mathrm{D}(f)$, with both ends $n$ here. |
| ODD-MAX-BIT total | \(\Theta(n)\) | Sandwiched: $\mathrm{RS}(f) = O(\bar{\chi}(f))$ and $\bar{\chi}(f) = O(\mathrm{R}(f))$, with both ends $\Theta(n)$ here. GLSS19 |
| ADDRESS / multiplexer total | \(\Theta(k+1)\) | Sandwiched: $\mathrm{s}(f) \le \bar{\chi}(f) \le \mathrm{D}(f)$, with both ends $k+1$ here. |
| Binary tree navigation total | \(\Theta(k)\) | Sandwiched: $\mathrm{RS}(f) = O(\bar{\chi}(f))$ and $\bar{\chi}(f) = O(\mathrm{R}(f))$, with both ends $\Theta(k)$ here. GLSS19 |
| TRIBES total | \(\Theta(n)\) | Sandwiched: $\mathrm{RS}(f) = O(\bar{\chi}(f))$ and $\bar{\chi}(f) = O(\mathrm{R}(f))$, with both ends $\Theta(n)$ here. GLSS19 |
| AND-OR tree (depth 2) total | \(\Theta(n^2)\) | Theorem 9.1; for LR use max-conflict ≤ O(LR) ≤ O(R). The conflict bound is the theorem’s bracket, not the stronger introduction-table upper bound. Meiburg26composition |
| NAND tree (balanced AND-OR formula) total | \(\Omega(\sqrt N),\ O\!\big(N^{\,0.753\ldots}\big)\) | Above $\chi = \Omega(\mathrm{bs})$ and above the recorded $\mathrm{RS} = \Omega(\sqrt N)$; below $\mathrm{LR} \le \mathrm{R} = O(N^{0.753\ldots})$ [GLSS19]. GLSS19 |
| Recursive MAJORITY-of-3 total | \(\Omega(2^{\,d}),\ O(2.64944^{\,d})\) | Above $\chi = \Omega(\mathrm{bs})$ and above the recorded $\mathrm{RS} = \Omega(2^d)$; below $\mathrm{LR} \le \mathrm{R}$ [GLSS19]. GLSS19 |
| Kushilevitz's function (iterated) total | \(\Theta(N)\) | Sandwiched: $\mathrm{bs}(f) \le \bar{\chi}(g) \le \mathrm{D}(f)$, with both ends $N$ here. |
| Rubinstein's function total | \(\Theta(N)\) | Squeezed between $\chi = \Omega(\mathrm{bs}) = \Omega(N)$ and $\mathrm{LR} \le \mathrm{R} = O(N)$; also consistent with the recorded $\mathrm{RS} = \Theta(N) \le \bar\chi$ [GLSS19]. GLSS19 |
| Ambainis-Sun function total | \(\Theta(N)\) | Between $\chi = \Omega(\mathrm{bs}) = \Omega(N)$ and $\mathrm{LR} \le \mathrm{R} = O(N)$ [GLSS19]. GLSS19 |
| AND composed with NOT-EXACT-HALF total | \(\Theta(n^2)\) | Sandwiched: $\mathrm{s}(f) \le \bar{\chi}(g) \le \mathrm{D}(f)$, with both ends $\Theta(n^2)$ here. |
| Meiburg's tournament-subcube function total | \(\Omega(14011^{\,d})\) putative | $\bar\chi \ge \chi = \Omega(\mathrm{bs}) = \Omega(14011^{\,d})$; the recorded $\mathrm{RS} \le \bar\chi$ [GLSS19] gives the same bound. GLSS19 |
| Pointer functions total | \(\widetilde\Theta(\sqrt n)\) | Variant $f_{2m,m}$: squeezed between $\mathrm{RS}=\widetilde\Theta(\sqrt n)$ and $\mathrm{R}=\widetilde O(\sqrt n)$ along the chain $\mathrm{RS}\lesssim\bar\chi\lesssim\mathrm{LR}\lesssim\mathrm{R}$ [GLSS19]. GLSS19 |
| Cheat-sheet functions total | \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) | Squeezed along $\mathrm{RS}\lesssim\bar\chi\lesssim\mathrm{LR}\lesssim\mathrm{R}$ [GLSS19]: the floor is the $\mathrm{RS}$ floor $\widetilde\Omega(\sqrt n)$ and the ceiling is $\mathrm{R}=\widetilde O(n)$. GLSS19 |
| Low-sensitivity function from unambiguous certificates total | \(\widetilde\Omega(n^{3/2})\) | Squeeze: $\bar\chi=\Omega(\mathrm{RS})=\widetilde\Omega(n^{3/2})$ along the chain $\mathrm{RS}\lesssim\bar\chi\lesssim\mathrm{LR}\lesssim\mathrm{R}$ [GLSS19]; equivalently $\bar\chi=\Omega(\sqrt{\mathrm{R}})$ directly. GLSS19 |
| Unambiguous-DNF / Alon-Saks-Seymour function total | \(\widetilde\Omega(n^{4/3}),\ \widetilde O(n^2)\) | Squeezed along $\mathrm{RS}\lesssim\bar\chi\lesssim\mathrm{LR}\lesssim\mathrm{R}$ [GLSS19] between $\mathrm{RS}=\widetilde\Omega(n^{4/3})$ and $\mathrm{R}=\widetilde O(n^2)$. GLSS19 |
| Gilmer-Saks-Srinivasan functions total | \(\Omega(n),\ O(n^2)\) | Squeezed along $\mathrm{RS}\lesssim\bar\chi\lesssim\mathrm{LR}\lesssim\mathrm{R}$ [GLSS19] between $\mathrm{RS}=\Omega(n)$ and $\mathrm{R}=O(n^2)$. GLSS19 |
| Goos-Pitassi-Watson partition-number function total | \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) | Squeezed along $\mathrm{RS}\lesssim\bar\chi\lesssim\mathrm{LR}\lesssim\mathrm{R}$ [GLSS19] between $\mathrm{RS}=\widetilde\Omega(\sqrt n)$ and $\mathrm{R}=\widetilde O(n)$. GLSS19 |
| Goos-Jayram-Pitassi-Watson function total | \(\widetilde\Omega(n^{1/3}),\ \widetilde O(n^{2/3})\) | Squeezed along $\mathrm{RS}\lesssim\bar\chi\lesssim\mathrm{LR}\lesssim\mathrm{R}$ [GLSS19]; equivalently $\bar\chi=\Omega(\sqrt{\mathrm{R}})=\widetilde\Omega(n^{1/3})$. GLSS19 |
| Ambainis' exact-quantum function total | \(\Theta(3^d)\) | Squeeze: $\bar\chi=\Omega(\mathrm{RS})=\Omega(3^d)$ [GLSS19] and $\bar\chi=O(\mathrm{LR})\le O(\mathrm{R})=O(3^d)$. GLSS19 |
| FORRELATION partial | \(\widetilde\Omega(n^{1/4})\) | $\mathrm{R} = O(\bar\chi^2)$ for partial $g$, so $\bar\chi = \Omega(\sqrt{\mathrm{R}}) = \widetilde\Omega(n^{1/4})$; and $\bar\chi = O(\mathrm{LR}) \le \mathrm{R}$. |
| k-FORRELATION partial | \(\widetilde\Omega\!\big(n^{1/2-1/(2k)}\big)\) | $\bar\chi = \Omega(\sqrt{\mathrm{R}})$ even for partial $g$; and $\bar\chi = O(\mathrm{LR}) \le \mathrm{R}$. |
| Simon's problem partial | \(\Omega(2^{n/4})\) | $\bar\chi = \Omega(\sqrt{\mathrm{R}})$ even for partial $g$; and $\bar\chi = O(\mathrm{LR}) \le \mathrm{R}$. |
| Deutsch-Jozsa partial | \(\Theta(1)\) | Sandwiched: $\Omega(\sqrt{\mathrm{R}}) \le \bar\chi = O(\mathrm{LR}) = O(1)$. |
| Bernstein-Vazirani partial | \(\Omega(\sqrt n)\) | $\bar\chi = \Omega(\sqrt{\mathrm{R}})$, and $\bar\chi = O(\mathrm{LR}) \le \mathrm{R} = O(n)$. |
| Gap-Majority partial | \(\Theta\!\big(\min(\sqrt n, 1/\delta)\big)\)· | At most $\mathrm{LR}$, and at least $\Omega(\sqrt{\mathrm{R}})$ -- the bound $\mathrm{R} = O(\bar\chi^2)$ holds for partial $g$, unlike its $\chi$ analogue -- so both ends meet. Since $\bar\chi$ is the quantity that appears in the composition theorem $\mathrm{R}(f \circ g^n) = \Omega(\mathrm{R}(f)\bar\chi(g))$, gapped majority as an inner function loses a square root -- which is precisely why $\mathrm{R}$ does not compose. GLSS19 |
| Gap-Majority at constant gap partial | \(\Theta(1)\)· | Between $\Omega(\sqrt{\mathrm{R}})$ and $\mathrm{LR}$. GLSS19 |
| Approximate index partial | \(\Omega\big((k\log k)^{1/4}\big)\) | From $\mathrm{R} = O(\bar\chi^2)$, which holds for partial $g$; and $\bar\chi = O(\mathrm{LR}) \le \mathrm{R} = O(\sqrt{k\log k})$. |
| Collision problem partial | \(\Omega(n^{1/4})\) | $\mathrm{R} = O(\bar\chi^2)$ holds for partial $g$, so $\bar\chi = \Omega(\sqrt{\mathrm{R}}) = \Omega(n^{1/4})$; and $\bar\chi = O(\mathrm{LR}) \le \mathrm{R} = O(\sqrt n)$. |
| Element distinctness total | \(\Theta(n)\) | Squeezed between $\chi = \Theta(n)$ and $\mathrm{LR} \le \mathrm{R} = O(n)$, so the whole composition-theorem family is tight here and $\mathrm{R}(f \circ \mathrm{ED}^m) = \Omega(\mathrm{R}(f)\,n)$. GLSS19 |
| Ambainis-Belovs function partial | \(\Omega(n^{1/6})\) | $\bar\chi = \Omega(\sqrt{\mathrm{R}})$ holds for partial $g$ as well, and $\mathrm{R} = \Omega(n^{1/3})$. Above, $\bar\chi = O(\mathrm{LR}) \le \mathrm{R} = O(n)$. |
| Surjectivity total | \(\Theta(n)\) | Sandwiched: $\mathrm{s}(f) \le \bar{\chi}(g) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. The lower end of this sandwich is itself the zoo's own argument (see the note on $\mathrm{s}$), so this value inherits its status. |
| $k$-distinctness total | \(\Theta(n)\) | Sandwiched: $\mathrm{s}(f) \le \bar{\chi}(g) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(n)$ here. |
| Triangle finding total | \(\Theta(m^2) = \Theta(n)\) | Sandwiched: $\mathrm{s}(f) \le \bar{\chi}(g) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(m^2) = \Theta(n)$ here. |
| Ordered search partial | \(\Theta(\log n)\) | $\bar\chi=\Omega(\mathrm{RS})=\Omega(\log n)$ [GLSS19] with the \(\mathrm{RS}(f)\) entry, and $\bar\chi=O(\mathrm{LR})\le O(\mathrm{R})=O(\log n)$ (\(\bar{\chi}(f)\) vs \(\mathrm{LR}(f)\)). GLSS19 |
| Inner product mod 2 total | \(\Theta(n)\) | Sandwiched: $\mathrm{s}(f) \le \bar{\chi}(g) \le \mathrm{D}(f)$, with both ends $n$ here. |
| Minsky-Papert one-in-a-box total | \(\Theta(m^3) = \Theta(N)\) | Sandwiched: $\bar\chi(g) = \Omega(\mathrm{RS}(g))$ and $\bar\chi \le \mathrm{LR} \le \mathrm{R}$, with $\mathrm{RS} = \Theta(m^3) = \mathrm{R}$ here. |
| Sink of a tournament total | \(\Theta(m) = \Theta(\sqrt N)\) | Sandwiched: $\mathrm{bs}(f) \le \bar{\chi}(g) \le \mathrm{D}(f)$, with both ends $\Theta(m) = \Theta(\sqrt N)$ here. |
| Scorpion graphs total | \(\Theta(m)\) | Squeezed inside the chain $\mathrm{RS} \lesssim \bar\chi \lesssim \mathrm{LR} \lesssim \mathrm{R}$, with $\mathrm{RS} = \Theta(m)$ and $\mathrm{R} = \Theta(m)$. |
| Graph connectivity total | \(\Theta(m^2) = \Theta(N)\) | Squeezed inside $\mathrm{RS} \lesssim \bar\chi \lesssim \mathrm{LR} \lesssim \mathrm{R}$, with $\mathrm{RS} = \Theta(m^2)$ and $\mathrm{R} = \Theta(m^2)$. |
| Meiburg’s parity-pointer family total | \(\Theta(q^3\log^2 q)\) | Meiburg26composition |
| Meiburg’s majority-pointer family total | \(O(q^3\log q)\) | Meiburg26composition |
| Meiburg’s parity-masked majority family total | \(\Theta(q^3\log q)\) | Meiburg26composition |