Q The Query Complexity Zoo
\(\chi(f)\)

Conflict complexity

A measure of how hard it is for a decision tree to distinguish a random 0-input from a random 1-input, one query at a time.

Definition

Introduced to prove composition theorems. Informally: sample $x \sim \mu_0$ and $y \sim \mu_1$ from hard distributions on $g^{-1}(0)$ and $g^{-1}(1)$, and run a deterministic tree simultaneously on both, "resolving" a conflict when the tree queries a coordinate on which $x$ and $y$ differ. $\chi(g)$ measures the expected number of queries before a conflict, maximised over distributions and minimised over trees.

Basic facts

  • $\mathrm{R}(f\circ g^n) = \Omega(\mathrm{R}(f)\,\chi(g))$ [Sanyal18; AGJKLMSS17].
  • $\chi(g) = \Omega(\mathrm{bs}(g))$ -- more precisely $\chi(f)\ge(\mathrm{bs}(f)+1)/2$ for total $f$ [Li18, Thm 1].
  • $\chi(g) = \Omega(\sqrt{\mathrm{R}(g)})$.
  • $\chi\le\mathrm{D}$ gives $\chi\le\mathrm{C}^2$ and $\chi\le\mathrm{bs}^3$. The standard chain $\chi\le\bar\chi\le O(\mathrm{LR})\le O(\mathrm{R})$ also upper-bounds conflict complexity.
  • Both comparisons in Is … for total functions? are refuted. \(\mathrm{AIKuD}\) has $\mathrm{C}=\Theta(\chi^2)$, derived from [AIK26] and the standard inequalities; \(\mathrm{AND}_n \circ \mathrm{OR}_n\) has $\chi=\Omega(\mathrm{C}^2/\log^2\mathrm{C})$ [Meiburg26composition].
  • Conflict and sabotage are incomparable on total functions. \(P_q\) gives $\chi/\mathrm{RS}=\Omega(\log N)$; \(\mathrm{AND}_n \circ \mathrm{OR}_n\) gives $\mathrm{RS}/\chi=\Omega(\sqrt{\log N})$. Also $\chi$ is not $O(\mathrm{C})$ and fails perfect composition [Meiburg26composition].

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\chi(f)\). “\(\chi(f)\) in terms of it” is the pair with \(\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.

Other measure \(\chi(f)\) in terms of it It in terms of \(\chi(f)\)
\(\bar{\chi}(f)\) Max-conflict complexity total1,1 partial1,1 open pair → total1,2 partial1,? open pair →
\(\mathrm{RS}(f)\) Sabotage complexity total1,2 partial1,? open pair → total1,2 partial1,? open pair →
\(\mathrm{LR}(f)\) Linearised randomized complexity total1,1 partial1,1 derived open pair → total1,2 partial1,? derived open pair →
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity total1,1 partial1,1 derived open pair → total1,2 partial1,? open pair →
\(\mathrm{bs}(f)\) Block sensitivity total2,3 partial2,? open pair → total1,1 partial1,? derived open pair →

The 5 above are this entry’s hand-picked neighbours; the other 88 are everything else in the zoo, by category.

Known values

FunctionValueNotes
OR total \(\Theta(n)\) Sandwiched: $\mathrm{s}^0(f) \le \chi(f) \le \mathrm{D}(f)$, with both ends $n$ here.
AND total \(\Theta(n)\) Sandwiched: $\mathrm{s}^1(f) \le \chi(f) \le \mathrm{D}(f)$, with both ends $n$ here.
PARITY total \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \chi(f) \le \mathrm{D}(f)$, with both ends $n$ here.
MAJORITY total \(\Theta(n)\) Sandwiched: $\chi(f) = \Omega(\mathrm{bs}(f))$ and $\chi(f) = O(\mathrm{R}(f))$, with both ends $\Theta(n)$ here. Li18
Threshold total \(\Theta(n)\) Squeezed: $\chi(f) = \Omega(\mathrm{bs}(f))$ and $\chi(f) = O(\mathrm{R}(f))$, with both ends $\Theta(n)$. Li18
Symmetric functions (general) total \(\Theta(n)\) Sandwiched: $\chi(f) = \Omega(\mathrm{bs}(f))$ and $\chi(f) = O(\mathrm{R}(f))$, with both ends $\Theta(n)$ here. Li18
EXACT-HALF total \(\Theta(n)\) Sandwiched: $\mathrm{s}^1(f) \le \chi(f) \le \mathrm{D}(f)$, with both ends $n$ here.
ODD-MAX-BIT total \(\Theta(n)\) Sandwiched: $\chi(f) = \Omega(\mathrm{bs}(f))$ and $\chi(f) = O(\mathrm{R}(f))$, with both ends $\Theta(n)$ here. Li18
ADDRESS / multiplexer total \(\Theta(k+1)\) Sandwiched: $\mathrm{s}(f) \le \chi(f) \le \mathrm{D}(f)$, with both ends $k+1$ here.
Binary tree navigation total \(\Theta(k)\) Sandwiched: $\chi(f) = \Omega(\mathrm{bs}(f))$ and $\chi(f) = O(\mathrm{R}(f))$, with both ends $\Theta(k)$ here. Li18
TRIBES total \(\Omega(n/\log n),\ O(n)\) Lower: $\chi(g) = \Omega(\mathrm{bs}(g))$ [Li18] and $\mathrm{bs} = \Theta(n/\log n)$. Upper: $\chi \le \bar\chi = \Theta(n)$ by the \(\bar{\chi}(f)\) line. The gap is the same $\log n$ that separates $\mathrm{bs}$ from $\mathrm{R}$ here, and closing it would say which of the two the composition theorem really sees. Li18
AND-OR tree (depth 2) total \(\Omega(n^2/\log^2 n),\ O(n^2/\log^{1/2}n)\) 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)\) $\chi = \Omega(\mathrm{bs}) = \Omega(\sqrt N)$ [Li18], and $\chi \le \bar\chi = O(\mathrm{LR}) \le \mathrm{R}$. Li18
Recursive MAJORITY-of-3 total \(\Omega(2^{\,d}),\ O(2.64944^{\,d})\) $\chi = \Omega(\mathrm{bs}) = \Omega(2^d)$ [Li18], and $\chi \le \bar\chi = O(\mathrm{LR}) \le \mathrm{R} = O(1.007\cdot 2.64944^{\,d})$. Li18
Kushilevitz's function (iterated) total \(\Theta(N)\) Sandwiched: $\mathrm{bs}(f) \le \chi(g) \le \mathrm{D}(f)$, with both ends $N$ here.
Rubinstein's function total \(\Theta(N)\) Pinned: $\chi = \Omega(\mathrm{bs}) = \Omega(N/2)$ [Li18] from below, and $\chi \le \bar\chi = O(\mathrm{LR}) \le \mathrm{R} = O(N)$ from above. Li18
Ambainis-Sun function total \(\Theta(N)\) Pinned: $\chi = \Omega(\mathrm{bs}) = \Omega(6k^2) = \Omega(N)$ [Li18], and $\chi \le \bar\chi = O(\mathrm{LR}) \le \mathrm{R} = O(N)$. Li18
AND composed with NOT-EXACT-HALF total \(\Theta(n^2)\) Sandwiched: $\mathrm{s}(f) \le \chi(g) \le \mathrm{D}(f)$, with both ends $\Theta(n^2)$ here.
Meiburg's tournament-subcube function total \(\Omega(14011^{\,d})\) putative Conflict complexity dominates block sensitivity, $\chi = \Omega(\mathrm{bs})$ [Li18], and $\mathrm{bs} = 14011^{\,d}$. Li18
Pointer functions total \(\widetilde\Theta(\sqrt n)\) Variant $f_{2m,m}$. Floor $\chi\ge\Omega(\mathrm{bs})=\widetilde\Omega(\sqrt n)$ [Li18]; ceiling $\chi=O(\mathrm{R})=\widetilde O(\sqrt n)$, since $\mathrm{R}(f\circ g)=\Omega(\mathrm{R}(f)\chi(g))$ would otherwise beat $\mathrm{R}(f\circ g)=O(\mathrm{R}(f)\mathrm{R}(g))$. Li18 Sanyal18
Cheat-sheet functions total \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) Floors: $\chi\ge\Omega(\mathrm{bs})=\widetilde\Omega(\sqrt n)$ [Li18], and $\mathrm{R}=O(\chi^2)$ [Sanyal18] with $\mathrm{R}=\widetilde\Theta(n)$ gives the same. Ceiling $\chi=O(\mathrm{R})=\widetilde O(n)$. Li18 Sanyal18
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n^{3/2})\) Floor from $\mathrm{R}=O(\chi^2)$ [Sanyal18] against $\mathrm{R}=\widetilde\Omega(n^3)$. This beats the block-sensitivity floor $\chi=\Omega(\mathrm{bs})=\widetilde\Omega(n)$ [Li18] by half a power. Sanyal18 Li18
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Omega(n^{4/3}),\ \widetilde O(n^2)\) Floor $\chi=\Omega(\mathrm{bs})=\widetilde\Omega(n^{4/3})$ [Li18] (the alternative $\chi=\Omega(\sqrt{\mathrm{R}})$ only gives $\widetilde\Omega(n^{2/3})$); ceiling $\chi=O(\mathrm{R})=\widetilde O(n^2)$. Li18
Gilmer-Saks-Srinivasan functions total \(\Omega(n),\ O(n^2)\) Floor $\chi=\Omega(\mathrm{bs})=\Omega(n)$ [Li18]; ceiling $\chi=O(\mathrm{R})=O(n^2)$. The composition-friendly relaxation of $\mathrm{R}$ therefore sees the $\mathrm{bs}$ scale, not the $\mathrm{C}$ scale. Li18
Goos-Pitassi-Watson partition-number function total \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) Floor $\chi=\Omega(\mathrm{bs})=\widetilde\Omega(\sqrt n)$ [Li18]; ceiling $\chi=O(\mathrm{R})=\widetilde O(n)$. Li18
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Omega(n^{1/3}),\ \widetilde O(n^{2/3})\) Two floors that agree: $\chi=\Omega(\mathrm{bs})=\widetilde\Omega(n^{1/3})$ [Li18] and $\mathrm{R}=O(\chi^2)$ [Sanyal18] with $\mathrm{R}=\widetilde\Theta(n^{2/3})$. Ceiling $\chi=O(\mathrm{R})=\widetilde O(n^{2/3})$. Li18 Sanyal18
Ambainis' exact-quantum function total \(\Theta(3^d)\) Squeeze: $\chi=\Omega(\mathrm{bs})=\Omega(3^d)$ [Li18], and $\chi\le\bar\chi=O(\mathrm{LR})=O(\mathrm{R}^{*})\le O(\mathrm{R})=O(3^d)$. All four inner measures of randomized composition collapse to the arity here. Li18
FORRELATION partial \(\widetilde O(\sqrt n)\) $\chi \le \bar\chi = O(\mathrm{LR}) \le \mathrm{R}$ for partial $g$. The familiar lower bound $\chi = \Omega(\mathrm{bs})$ is a total-function statement [Li18] and gives only $\Omega(1)$ here in any case, since $\mathrm{bs} = O(1)$.
k-FORRELATION partial \(\widetilde O\!\big(n^{1-1/k}\big)\) $\chi \le \bar\chi = O(\mathrm{LR}) \le \mathrm{R}$ for partial $g$.
Simon's problem partial \(O(2^{n/2})\) $\chi \le \bar\chi = O(\mathrm{LR}) \le \mathrm{R}$.
Deutsch-Jozsa partial \(\Theta(1)\) At most $\bar\chi = \Theta(1)$, and at least $1$.
Bernstein-Vazirani partial \(O(n)\) $\chi \le \bar\chi = O(\mathrm{LR}) \le \mathrm{R} = O(n)$. The total-function lower bound $\chi = \Omega(\mathrm{bs})$ [Li18] would only give $\Omega(1)$ anyway.
Gap-Majority partial \(O(\min(\sqrt n, 1/\delta))\) $\chi \le \bar\chi$. The matching lower bounds $\chi = \Omega(\mathrm{bs})$ [Li18] and $\mathrm{R} = O(\chi^2)$ are both total-function statements -- and the first is false here, since $\mathrm{bs} = \Theta(\min(n,1/\delta))$ can be quadratically larger.
Gap-Majority at constant gap partial \(O(1)\) $\chi \le \bar\chi$. The total-function bound $\chi = \Omega(\mathrm{bs})$ is false here.
Approximate index partial \(O(\sqrt{k\log k})\) $\chi \le \bar\chi = O(\mathrm{LR}) \le \mathrm{R}$.
Collision problem partial \(O(\sqrt n)\) $\chi \le \bar\chi = O(\mathrm{LR}) \le \mathrm{R} = O(\sqrt n)$. The lower bound $\chi = \Omega(\mathrm{bs})$ [Li18] is total-only and would give only $\Omega(1)$ anyway.
Element distinctness total \(\Theta(n)\) $\chi = \Omega(\mathrm{bs}) = \Omega(n)$ for total functions [Li18], and $\chi \le \bar\chi \le \mathrm{LR} \le \mathrm{R} = O(n)$. Li18
Ambainis-Belovs function partial \(O(n)\) $\chi \le \bar\chi = O(\mathrm{LR}) \le \mathrm{R} = O(n)$.
Surjectivity total \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \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 \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 \chi(g) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(m^2) = \Theta(n)$ here.
Ordered search partial \(O(\log n)\) $\chi\le\bar\chi=\Theta(\log n)$ (\(\chi(f)\) vs \(\bar{\chi}(f)\)). No lower bound: the route $\mathrm{R}=O(\chi^2)$ is recorded only for total functions.
Inner product mod 2 total \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \chi(g) \le \mathrm{D}(f)$, with both ends $n$ here.
Minsky-Papert one-in-a-box total \(\Omega(m^2),\ O(m^3)\) Sandwiched: $\chi(g) = \Omega(\mathrm{bs}(g))$ (\(\chi(f)\) vs \(\mathrm{bs}(f)\)) gives $\Omega(m^2)$ -- the $\mathrm{R} = O(\chi^2)$ route only gives $\Omega(m^{3/2})$ -- and $\chi \le \bar\chi = \Theta(m^3)$ (\(\chi(f)\) vs \(\bar{\chi}(f)\)). The gap here is exactly the gap between $\mathrm{bs}$ and $\mathrm{R}$ on a read-once AND-OR tree, which is why $\mathrm{MP}$ is a natural test case for whether conflict complexity is $\Theta(\bar\chi)$.
Sink of a tournament total \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{bs}(f) \le \chi(g) \le \mathrm{D}(f)$, with both ends $\Theta(m) = \Theta(\sqrt N)$ here.
Scorpion graphs total \(\Theta(m)\) Sandwiched: $\chi(f) = \Omega(\mathrm{bs}(f))$ and $\chi(f) \lesssim \mathrm{RS}(f)$, with $\mathrm{bs} = \Theta(m)$ and $\mathrm{RS} = \Theta(m)$ here. The whole inner-measure chain $\chi \lesssim \mathrm{RS} \lesssim \bar\chi \lesssim \mathrm{LR} \lesssim \mathrm{R}$ collapses to $\Theta(m)$ on this function.
Graph connectivity total \(\Theta(m^2) = \Theta(N)\) Sandwiched: $\chi(f) = \Omega(\mathrm{bs}(f))$ and $\chi(f) \lesssim \mathrm{RS}(f)$, both $\Theta(m^2)$ here. The whole inner-measure chain $\chi \lesssim \mathrm{RS} \lesssim \bar\chi \lesssim \mathrm{LR} \lesssim \mathrm{R}$ collapses on a randomised-evasive function.
Ambainis–Iraids–Kokainis unambiguous DNF total \(\Theta(n)\) putative Derived: AIK26 gives C=Θ(n²), R=Θ(n). The chain χ≤χ̄=O(LR)=O(R) gives χ=O(n); C≤bs² and χ≥(bs+1)/2 give χ=Ω(n). Thus C=Θ(χ²), refuting χ=Ω(C). AIK26 Nisan91 Li18 BBGM22
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