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
| Measure | Value | Notes |
|---|---|---|
| \(\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.
-
\(\mathrm{D}^{\mu}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{D}^{\mathrm{prod}}(f_n) = O(1)\)from \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \Theta(n)\) against \(\mathrm{D}^{\mathrm{prod}}(f) = \Theta(1)\)
-
\(\mathrm{cbs}(S)(f_n) \to \infty \ \text{ while } \ \mathrm{C}(f_n) = O(1)\)from \(\mathrm{cbs}(S) = \Theta(n)\) against \(\mathrm{C}(f) = \Theta(1)\)
-
\(\mathrm{D}(f_n) = 2^{\Omega(\mathrm{D}^{\oplus}(f_n))}\)from \(\mathrm{D}(f) = \Theta(n)\) against \(\mathrm{D}^{\oplus}(f) = \Theta(\log n)\)
-
\(\mathrm{DTsize}(f_n) = 2^{\Omega(\mathrm{D}^{\mathrm{na}}(f_n))}\)from \(\mathrm{DTsize}(f) = 2^{\Theta(n)}\) against \(\mathrm{D}^{\mathrm{na}}(f) = n\)
-
\(\mathrm{R}_{\varepsilon}(f_n) = \Omega\big(\mathrm{Q}_{0}(f_n)^{2}\big)\)from \(\mathrm{R}_{\varepsilon}(f) = \Theta(n)\) against \(\mathrm{Q}_{0}(f) = O(\sqrt n)\)
-
\(\mathrm{cbs}(S)(f_n) \to \infty \ \text{ while } \ \mathrm{D}^{\mathrm{prod}}(f_n) = O(1)\)from \(\mathrm{cbs}(S) = \Theta(n)\) against \(\mathrm{D}^{\mathrm{prod}}(f) = \Theta(1)\)
-
\(\mathrm{CA}(f_n) \to \infty \ \text{ while } \ \mathrm{C}(f_n) = O(1)\)from \(\mathrm{CA}(f) = \Theta(n)\) against \(\mathrm{C}(f) = \Theta(1)\)
-
\(\mathrm{DTsize}(f_n) = 2^{\Omega(\mathrm{D}(f_n))}\)from \(\mathrm{DTsize}(f) = 2^{\Theta(n)}\) against \(\mathrm{D}(f) = \Theta(n)\)
-
\(\mathrm{D}^{\mu}_{\varepsilon}(f_n) = 2^{\Omega(\mathrm{D}^{\oplus}(f_n))}\)from \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \Theta(n)\) against \(\mathrm{D}^{\oplus}(f) = \Theta(\log n)\)
-
\(\bar{\mathrm{R}}_{\varepsilon}(f_n) = \Omega\big(\mathrm{Q}_{0}(f_n)^{2}\big)\)from \(\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(n)\) against \(\mathrm{Q}_{0}(f) = O(\sqrt n)\)
-
\(\mathrm{R}_{\varepsilon}(f_n) \to \infty \ \text{ while } \ \mathrm{D}^{\mathrm{prod}}(f_n) = O(1)\)from \(\mathrm{R}_{\varepsilon}(f) = \Theta(n)\) against \(\mathrm{D}^{\mathrm{prod}}(f) = \Theta(1)\)
-
\(\mathrm{DTsize}(f_n) = 2^{\Omega(\mathrm{Q}_{\mathrm{E}}(f_n))}\)from \(\mathrm{DTsize}(f) = 2^{\Theta(n)}\) against \(\mathrm{Q}_{\mathrm{E}}(f) = O(n)\)
-
\(\mathrm{cbs}(S)(f_n) = 2^{\Omega(\mathrm{D}^{\oplus}(f_n))}\)from \(\mathrm{cbs}(S) = \Theta(n)\) against \(\mathrm{D}^{\oplus}(f) = \Theta(\log n)\)
-
\(\mathrm{D}^{\mu}_{\varepsilon}(f_n) = \Omega\big(\mathrm{Q}_{0}(f_n)^{2}\big)\)from \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \Theta(n)\) against \(\mathrm{Q}_{0}(f) = O(\sqrt n)\)
… and 29 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.
Separations it witnesses
-
The tight case: $\mathrm{cbs} = \Theta(\mathrm{R}) = \Theta(n)$, so the general bound $\mathrm{cbs} = O(\mathrm{R})$ cannot be improved.
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].