Q The Query Complexity Zoo
\(\mathrm{Ts}(G)\)

Tseitin search on an expander

The family critical block sensitivity was invented for: $\mathrm{cbs} = \Theta(n)$, and here it really does match $\mathrm{R}$ and $\mathrm{D}$.

relation relational arity: $n = |E|$ bits, one per edge of a bounded-degree expander $G$— also: Tseitin contradiction, odd-charge search

Description

Fix a connected graph $G = (V,E)$ of bounded degree $d$ that is an expander, and a charge $\chi : V \to \{0,1\}$ of odd total parity. The input assigns a bit to each edge. A vertex $v$ is violated if the bits on its incident edges do not sum to $\chi(v) \bmod 2$. Since $\sum_v \chi(v)$ is odd while every edge is counted twice, some vertex is always violated -- so this is a total search problem. The task: name one.

Formal definition

$$\mathrm{Ts}(G) \;=\; \Big\{\,(x, v) \;:\; x \in \{0,1\}^{E},\ v \in V,\ \textstyle\sum_{e \ni v} x_e \not\equiv \chi(v) \ (\mathrm{mod}\ 2)\,\Big\}.$$

Measure values

MeasureValueNotes
\(\mathrm{cbs}(S)\) Critical block sensitivity \(\Theta(n)\) The theorem the measure exists for. Expansion is what forces it: any solution function must commit to a violated vertex, and flipping the edges along a path to a far-away vertex moves the violation, so no commitment is stable. Contrast \(\mathrm{Search}(\varphi)\) on a random dense formula, where a constant fraction of clauses is falsified, $\mathrm{R} = \Theta(1)$, and therefore $\mathrm{cbs} = \Theta(1)$ as well. HuynhNordstrom12 GoosPitassi14
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(n)\) putative Lower: $\mathrm{R} = \Omega(\mathrm{cbs}) = \Omega(n)$ (\(\mathrm{cbs}(S)\) vs \(\mathrm{R}_{\varepsilon}(f)\)). Upper: read every edge. Sampling -- the trick that makes \(\mathrm{Search}(\varphi)\) easy -- fails here, because an adversarial input can leave exactly one vertex violated. GoosPitassi14
\(\mathrm{D}(f)\) Deterministic query complexity \(\Theta(n)\) Squeezed between $\mathrm{R} = \Theta(n)$ and the trivial $n$. Equivalently, by [LNNW95], the minimum depth of a tree-like resolution refutation of the Tseitin formula, which is $\Omega(n)$ on an expander. Urquhart87 BenSassonWigderson01 LNNW95
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\Theta(n)\) Between $\mathrm{R} = \Theta(n)$ and $\mathrm{D} = \Theta(n)$.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Theta(n)\) Between $\mathrm{R} = \Theta(n)$ and $\mathrm{D} = \Theta(n)$.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(n)\) Between $\mathrm{R} = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}} = n$.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(n\) Between $\mathrm{D} = \Theta(n)$ and the trivial $n$.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta(n)\) By Yao, $\max_\mu \mathrm{D}^\mu = \mathrm{R} = \Theta(n)$.
\(\mathrm{CA}(f)\) Classical adversary bound \(\Theta(n)\) Squeezed: $\mathrm{cbs} = O(\mathrm{CA})$ [ABK21lifting] gives $\Omega(n)$, and $\mathrm{CA} \le \mathrm{R} = \Theta(n)$ closes it. So on this family the classical adversary is tight, which is exactly the contrast with \(\mathrm{Search}(\varphi)\), where it collapses to $\Theta(1)$. ABK21lifting
\(\mathrm{DTsize}(f)\) Decision tree size \(2^{\Theta(n)}\) Decision-tree size for the search problem is tree-like resolution size, and [Urquhart87] gives $2^{\Omega(n)}$ on an expander; $2^n$ is the ceiling. Urquhart87 BenSassonWigderson01
\(\mathrm{C}(f)\) Certificate complexity \(\Theta(1)\) putative The $d = O(1)$ edges incident to a violated vertex certify it. So verification is trivial while $\mathrm{R} = \Theta(n)$ -- the same shape as \(\mathrm{Search}(\varphi)\), and the reason this is a search problem rather than a decision problem in disguise.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(\Theta(1)\) putative At most $\mathrm{C} = O(1)$, at least $1$.
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\Theta(n)\) putative At least $\mathrm{R} = \Theta(n)$ and at most $\mathrm{D} = \Theta(n)$, so pseudo-determinism is free here. Contrast \(\mathrm{Search}(\varphi)\) and \(\mathrm{ApproxHW}\), where it is exactly the expensive part.
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity \(\Theta(1)\) putative Constant against $\mathrm{R} = \Theta(n)$: the hard distribution for Tseitin must be correlated, and $O(1)$ queries suffice against any product $\mu$. Write $t_e = 1-2\Pr_\mu[x_e=1]$ and $T_v = (-1)^{\chi(v)}\prod_{e \ni v} t_e$, so that $\Pr_\mu[v \text{ violated}] = (1-T_v)/2$. Every edge meets exactly two vertices, so $\prod_v T_v = (-1)^{\sum_v \chi(v)}\prod_e t_e^2 = -\prod_e t_e^2 \le 0$, and therefore some $v^*$ has $T_{v^*} \le 0$, i.e. is violated with probability $\ge 1/2$. Query its $d = O(1)$ edges. If it is not violated, delete $v^*$ and fold the revealed bits into the charges of its neighbours: the residual instance on $G - v^*$ has total charge $\sum_v \chi(v) + \sum_{e \ni v^*} x_e \equiv \sum_v \chi(v)$, still odd, and the unqueried edges are still independent. Two rounds leave error $\le 1/4$, so $\mathrm{D}^{\mathrm{prod}} \le 2d = O(1)$.
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(O(\sqrt n)\) Grover over the $\Theta(n)$ vertices, each tested for violation with $d = O(1)$ queries. So the quadratic speedup that \(\mathrm{Search}(\varphi)\) does not need and \(\mathrm{WT}_n\) far exceeds is exactly what Tseitin gets. No matching $\Omega(\sqrt n)$ is recorded: $\mathrm{cbs}$ is a randomized lower bound with no known quantum analogue, and the natural relational adversary is weak here because two inputs with different violated vertices differ only along a path, which in an expander has length $O(\log n)$.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(O(\sqrt n)\) Zero error is free, as it is classically: a candidate vertex is checked with $d = O(1)$ further queries, so $\mathrm{Q}_0 = O(\mathrm{Q} + 1)$, and the $\mathrm{Q}$ row gives $O(\sqrt n)$.
\(\mathrm{rank}(f)\) Decision tree rank \(\Omega(n/\log n),\ O(n)\) putative A depth-$d$ tree of rank $r$ has at most $\sum_{i\le r}\binom di \le (d+1)^r$ leaves [EhrenfeuchtHaussler89]. Here $d \le n$ and $\mathrm{DTsize} = 2^{\Omega(n)}$ [Urquhart87], so $(n+1)^r \ge 2^{\Omega(n)}$ and $r = \Omega(n/\log n)$; the ceiling is $\mathrm{rank} \le \mathrm{D} = \Theta(n)$ (\(\mathrm{rank}(f)\) vs \(\mathrm{D}(f)\)). In Prover-Delayer terms the Delayer scores $\Omega(n/\log n)$ points on an expander Tseitin formula. EhrenfeuchtHaussler89 Urquhart87
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\tilde\Theta(n)\) Between $\mathrm{R} = \Theta(n)$ and $O(\mathrm{R}\log \mathrm{R}) = O(n\log n)$ (\(\mathrm{N}_{p}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)).
\(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity \(\Theta(\log n)\) putative Exponentially cheaper than $\mathrm{D}=\Theta(n)$. For a vertex set $S$, $\sum_{v\in S}(\chi(v)+\sum_{e\ni v}x_e)=\chi(S)+\sum_{e\in\partial S}x_e$ over $\mathbb{F}_2$, since interior edges are counted twice -- one parity query tells whether $S$ contains an odd number of violated vertices. Starting from $S=V$, which is odd because the total charge is odd, halving $S$ each time isolates a violated vertex in $\lceil\log_2|V|\rceil$ queries. Matching lower bound by answer counting: the violation vector is $Ax+\chi$, which ranges over all odd-weight vectors, so each single vertex $v$ is the unique answer for some input and the tree needs $|V|=\Theta(n)$ leaves.
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(O(\sqrt n)\) $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$ is settled in the relation setting (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}=O(\sqrt n)$ by Grover search over the $\Theta(n)$ vertices, one of which is always violated. No lower bound is recorded because none is recorded for $\mathrm{Q}$.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(O(\sqrt n)\) $\mathrm{Adv}\le\mathrm{Adv}^{\pm}=O(\sqrt n)$ (\(\mathrm{Adv}(f)\) vs \(\mathrm{Adv}^{\pm}(f)\)).
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(O(\sqrt n)\)· The multiplicative adversary is also a tight characterisation of $\mathrm{Q}$, so it inherits the $O(\sqrt n)$ ceiling; the characterisation is usually stated for functions, hence the reduced confidence in the relational reading.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(O(\sqrt n)\)· The approximate $\gamma_2$ norm equals $\mathrm{Adv}^{\pm}$ up to constants (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Adv}^{\pm}(f)\)), which is $O(\sqrt n)$ here.
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(O(\sqrt n\log n)\) $\mathrm{Q}^{\mathrm{rob}}=O(\mathrm{Q}\log\mathrm{Q})$ (\(\mathrm{Q}^{\mathrm{rob}}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)) with $\mathrm{Q}=O(\sqrt n)$.
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(O(n)\) $\mathrm{Q}_{\mathrm{E}}\le\mathrm{D}=\Theta(n)$. Reading every edge determines the whole violation vector, and nothing better is known exactly: the Grover algorithm behind $\mathrm{Q}=O(\sqrt n)$ has one-sided error.
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(O(n)\) $\mathrm{prt}_\varepsilon\le2\,\mathrm{R}_\varepsilon=O(n)$ [JainKlauck10], stated for relations. The recorded $\mathrm{CA}=\Theta(n)$ does not close this from below: $\mathrm{CA}\le\mathrm{prt}$ is a partial-function statement. JainKlauck10
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(O(n)\) $\overline{\mathrm{prt}}_\varepsilon\le\mathrm{prt}_\varepsilon\le2\,\mathrm{R}_\varepsilon=O(n)$ [JainKlauck10]. JainKlauck10
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(O(n)\) $\mathrm{cjdeg}_\varepsilon\le\mathrm{R}_\varepsilon=O(n)$ (\(\mathrm{cjdeg}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\), relation setting -- the version used for total search problems).
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(O(\sqrt n)\) Post-selection can only help, so $\mathrm{PostQ}\le\mathrm{Q}=O(\sqrt n)$.

Separations its values prove — computed, not recorded

Read straight off the table above by comparing two values: no relation record states these, and where one does and says more, the record wins and the pair is not listed here. 43 in total, strongest first.

… and 29 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.

Separations it witnesses

Notes

Two false-clause-style search problems sit at opposite ends of the same cell. On a random $\Delta$-dense unsatisfiable CNF (\(\mathrm{Search}(\varphi)\)) a constant fraction of the clauses is falsified, so $\mathrm{R} = \Theta(1)$ while $\mathrm{D} = \Theta(n)$: an unbounded $\mathrm{D}$-vs-$\mathrm{R}$ separation, and $\mathrm{cbs}$ -- being a randomized lower bound -- sees none of it. On Tseitin over an expander the violation can be unique, sampling is useless, and all of $\mathrm{cbs}$, $\mathrm{CA}$, $\mathrm{R}$ and $\mathrm{D}$ line up at $\Theta(n)$. The lifted consequence is the one the measure was built for: $\mathrm{R}^{cc}(\mathrm{Ts}(G) \circ g^n) = \Omega(n)$ for a constant-size gadget [GoosPitassi14].