Q The Query Complexity Zoo
\(\mathrm{Tribes}_{w,s}\)

TRIBES

Balanced read-once DNF; the KKL / max-influence extremal example.

total basic arity: $n = ws$ bits

Description

An OR of $s$ disjoint ANDs of $w$ variables each, with $w,s$ chosen so that $\Pr[\mathrm{Tribes}=1] \approx 1/2$, i.e. $s \approx 2^w \ln 2$.

Formal definition

$$\mathrm{Tribes}_{w,s}(x) = \bigvee_{j=1}^{s} \bigwedge_{i=1}^{w} x_{(j-1)w+i}, \qquad w \approx \log_2 n - \log_2\ln n,\ \ s = n/w .$$

Measure values

MeasureValueNotes
\(\mathrm{D}(f)\) Deterministic query complexity \(n\)
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(n)\)
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity \(\Theta(n)\) From $\mathrm{R}(f) = \Theta(n) \Rightarrow \mathrm{noisyR}(f) = \Theta(\mathrm{R}(f))$ [CKMPSS23] -- see the \(\mathrm{noisyR}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\) record. At the top of the range there is no room for fractional queries to help.
\(\mathrm{s}^1(f)\) 1-sensitivity \(\Theta(\log n)\) Flip any bit of the unique all-ones tribe.
\(\mathrm{s}^0(f)\) 0-sensitivity \(\Theta(n/\log n)\) Every tribe missing exactly one bit.
\(\mathrm{s}(f)\) Sensitivity \(\Theta(n/\log n)\)
\(\mathrm{bs}(f)\) Block sensitivity \(\Theta(n/\log n)\)
\(\mathrm{C}^1(f)\) 1-certificate complexity \(\Theta(\log n)\)
\(\mathrm{C}^0(f)\) 0-certificate complexity \(\Theta(n/\log n)\)
\(\mathrm{C}(f)\) Certificate complexity \(\Theta(n/\log n)\)
\(\mathrm{I}(f)\) Total influence (L2 influence) \(\Theta(\log n)\)
\(\mathrm{MaxInf}(f)\) Maximum influence \(\Theta(\log n / n)\) Extremal for the KKL theorem: no variable has influence more than $O(\log n/n)$. KKL88
\(\mathrm{Var}(f)\) Variance \(\Theta(1)\) Exactly $1-o(1)$: the width is chosen so that $\Pr[f = 1] \to \tfrac12$. It also follows from the recorded $\mathrm{NS}_\delta = \tfrac12-o(1)$ and $\mathrm{NS}_\delta \le \mathrm{Var}/2$.
\(\mathrm{osss}(f)\) OSSS number \(\Theta(n/\log n)\) putative $\mathrm{Var} = 1-o(1)$ over $\mathrm{MaxInf} = \Theta(\log n/n)$. The extremal case: KKL says no function beats $O(n/\log n)$, and TRIBES attains it, so this is the largest lower bound OSSS can ever produce. It coincides with $\mathrm{s} = \mathrm{bs} = \Theta(n/\log n)$ here, and falls a $\log$ short of $\mathrm{D} = n$.
\(\mathrm{nsr}(f)\) Noise robustness \(\Theta(\log n)\) putative Upper: $\mathrm{nsr}\le 4\mathrm{I}/\mathrm{Var} = \Theta(\log n)$. Lower: a uniform input has $\Theta(\log n)$ tribes that are a single $0$ away from firing, so at $\delta = c/\log n$ one of them flips with constant probability and $\mathrm{NS}_\delta = \Omega(1)$. Note $\mathrm{osss}\cdot\mathrm{nsr} = \Theta(n)$, as for every transitive function whose $\mathrm{NS}_\delta \le \delta\mathrm{I}$ bound is tight.
\(\deg(f)\) Exact degree \(n\) The multilinear polynomial $1-\prod_j(1-\prod_{i\in T_j} x_i)$ has the full monomial.
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(\Theta(n/\log n)\)
\(\mathrm{bs}^1(f)\) 1-block sensitivity \(\Theta(\log n)\) At most $\mathrm{C}^1 = w$, and the $w$ singletons inside the satisfied tribe achieve it.
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(\Theta(n/\log n)\) Between $\mathrm{bs}$ and $\mathrm{C}$, which agree up to constants.
\(\mathrm{FC}(f)\) Fractional certificate complexity \(\Theta(n/\log n)\) Equal to $\mathrm{fbs}$ by LP duality.
\(\mathrm{RC}(f)\) Randomized certificate complexity \(\Theta(n/\log n)\) $\mathrm{RC}=\Theta(\mathrm{fbs})$. Aaronson08
\(\mathrm{EC}(f)\) Expectational certificate complexity \(\Theta(n/\log n)\) Between $\mathrm{fbs}$ and $\mathrm{C}$, which agree up to constants. GJKKLSSV17
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(\Theta(\log n)\) The cheapest input to certify is a $1$-input: one satisfied tribe, $w=\Theta(\log n)$ bits.
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\Theta(n)\) Between $\mathrm{R}=\Theta(n)$ and $\mathrm{D}=n$.
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Theta(\sqrt n)\) Grover over the $s$ tribes, Grover inside each: $\sqrt s\cdot\sqrt w = \sqrt n$. Tight, since $\widetilde{\deg}=\Theta(\sqrt n)$. Grover96 BT22
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(\Theta(\sqrt n)\) As for any depth-two AND-OR tree on $n$ variables. BT22
\(\lambda(f)\) Spectral sensitivity \(\Theta(\sqrt n)\) At most $\sqrt{\mathrm{s}^0\mathrm{s}^1} = \sqrt{\Theta(n/\log n)\cdot\Theta(\log n)} = \Theta(\sqrt n)$, and at least $\sqrt{\deg} = \sqrt n$ by Huang. Huang19 ABKRT21
\(\mathrm{NS}_{\delta}(f)\) Noise sensitivity \(\tfrac12 - o(1)\) For any fixed $\delta>0$: TRIBES is the standard example of a noise-sensitive monotone function, because all its influences are $O(\log n/n)$. ODonnell14
\(\mathrm{I}^{1}(f)\) Total L1 influence \(\Theta(\log n)\) Boolean-valued, so equal to $\mathrm{I}(f)$.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(n\) Every variable is relevant.
\(\mathrm{CA}(f)\) Classical adversary bound \(\Theta(n/\log n)\) Sandwiched: $\mathrm{RC}(f) \le \mathrm{CA}(f) \le \mathrm{fbs}(f)$, with both ends $\Theta(n/\log n)$ here.
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) \(\Theta(n/\log n)\) Sandwiched: $\mathrm{RC}(f) \le \mathrm{CG}^{\mathrm{pub}}(f) \le \mathrm{fbs}(f)$, with both ends $\Theta(n/\log n)$ here.
\(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity \(\Theta(n/\log n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
\(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity \(\Theta(n/\log n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(n)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{\mathrm{na}}(f) \le \mathrm{D}^{\mathrm{na}}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}}(f) = n$ here.
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\Theta(\sqrt n)\) Sandwiched: $\lambda(f) \le \mathrm{Adv}^{\pm}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with both ends $\Theta(\sqrt n)$ here.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Theta(\sqrt n)\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(\sqrt n)$ here.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(\Theta(\sqrt n)\) Sandwiched: $\lambda(f) \le \mathrm{Adv}(f) \le \mathrm{Adv}^{\pm}(f)$, with both ends $\Theta(\sqrt n)$ here.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Theta(n)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \bar{\mathrm{R}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\Theta(n)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(\Theta(n)\) Sandwiched: $\deg(f)/2 \le \mathrm{Q}_{\mathrm{E}}(f) \le \mathrm{D}(f)$ -- a $t$-query exact algorithm gives an exact polynomial of degree at most $2t$, so the degree bound is halved -- with $\deg(f) = n$ and $\mathrm{D}(f) = n$ here, hence $n/2 \le \mathrm{Q}_{\mathrm{E}} \le n$.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Theta(\sqrt n)\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with both ends $\Theta(\sqrt n)$ here.
\(\deg_2(f)\) Mod-2 degree \(n\) putative Over $\mathbb{F}_2$, $\bigvee_j y_j = 1 + \prod_j(1+y_j)$ contributes the monomial $\prod_j y_j$ with coefficient $1$, and each $y_j$ is the product of its tribe's variables. So the full monomial $x_1\cdots x_n$ survives, exactly as over $\mathbb{R}$.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\Omega(n/\log n),\ O(n)\) Not $\Theta(n)$ on the evidence the zoo has: $\deg/2$ floors $\mathrm{Q}_{\mathrm{E}}$, not $\mathrm{Q}_0$, whose floor is $\mathrm{rdeg}/2 = \Theta(n/\log n)$. The same bound comes from a restriction: fixing all but one bit of every tribe to $1$ leaves $\mathrm{OR}_w$ on the free bits, and $\mathrm{Q}_0(\mathrm{OR}_w) = w = \Theta(n/\log n)$ [BCWZ99]. Ceiling $\mathrm{D} = n$. So $\mathrm{Q}_0$ is pinned only to within the $\log n$, still a full quadratic above $\mathrm{Q} = \Theta(\sqrt n)$. BCWZ99
\(\mathrm{RS}(f)\) Sabotage complexity \(\Theta(n)\) putative At most $\mathrm{R} = \Theta(n)$. For the lower bound take the sabotaged input in which every tribe has exactly one $0$ except one distinguished tribe, which is all $1$s apart from a single $\ast$; the value is undetermined. Ruling out a tribe means finding its unique $0$, which costs $\Omega(w)$ queries, and a constant fraction of the $s$ tribes must be ruled out, so $\Omega(sw) = \Omega(n)$. BenDavidKothari18
\(\bar{\chi}(f)\) Max-conflict complexity \(\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
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\Theta(n)\) Sandwiched: $\bar{\chi}(f) = O(\mathrm{LR}(f)) \le \mathrm{R}(f)$, with both ends $\Theta(n)$ here. BBGM22
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate \(\Theta(n)\) Sandwiched: $\mathrm{LR}(f) = O(\mathrm{R}^{*}(f)) \le \mathrm{R}(f)$, with both ends $\Theta(n)$ here. BBGM22
\(\mathrm{QC}(f)\) Quantum certificate complexity \(\Theta(\sqrt{n/\log n})\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{RC}(f)})$ for every $f$, and $\mathrm{RC}(f) = \Theta(n/\log n)$ here. Strictly below $\mathrm{Q} = \Theta(\sqrt n)$ by a $\sqrt{\log n}$ factor. Aaronson08
\(\mathrm{rank}(f)\) Decision tree rank \(\Theta(n/\log n)\)· putative Equal to the number of tribes $s$. Write $h(m,r)$ for the rank of $\mathrm{AND}_m \vee G$ with $\mathrm{rank}(G) = r$ on disjoint variables: $h(1,r) = r$ (the $\mathrm{AND}_1$ variable has a constant branch) and $h(m,r) = r+1$ for $m \ge 2$, since querying a tribe variable gives branches of rank $r$ and $r$ or $r+1$. Iterating over the $s$ tribes from $\mathrm{rank}(\mathrm{AND}_w) = 1$ gives $s$. Checked by hand at $w = s = 2$, where the rank is $2$.
\(\mathrm{ndeg}(f)\) Nondeterministic degree \(\Theta(\log n)\) putative Exactly $w$. Upper: $p(x) = \sum_j \prod_{i \in T_j} x_i$ is a sum of nonnegative terms that vanishes precisely when no tribe is all-ones, and has degree $w$. Lower: kill all but one tribe by planting a $0$ in each of the others; the restriction is $\mathrm{AND}_w$, whose nondeterministic degree is $w$ because a polynomial vanishing on all but one point of the cube needs full degree. Contrast $\deg = n$: the \(\mathrm{rdeg}(f)\) gap comes entirely from the other side.
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity \(\Theta(\log n)\) $\mathrm{NQ}(f) = \lceil \mathrm{ndeg}(f)/2\rceil$, and $\mathrm{ndeg}(f) = w = \Theta(\log n)$ here. deWolf03
\(\deg_p(f)\) Mod-p degree \(n\) putative For every prime $p$. Over $\mathbb{F}_p$ the representation is still $1 - \prod_j(1 - \prod_{i\in T_j} x_i)$, whose top monomial $x_1\cdots x_n$ has coefficient $(-1)^{s+1} \ne 0$ in every characteristic. Consistent with the $\deg_2 = n$ entry above.
\(\dim_{\mathbb{F}_2}(f)\) Fourier dimension \(n\) putative TRIBES is monotone, so $\hat f(\{i\}) = \mathrm{Inf}_i > 0$ for every $i$: the Fourier support contains all $n$ singletons and therefore spans $\mathbb{F}_2^n$.
\(\mathrm{Stab}_{\rho}(f)\) Noise stability \(o(1)\) For every fixed $\rho \in (-1,1)$, from $\mathrm{Stab}_\rho = 1 - 2\,\mathrm{NS}_{(1-\rho)/2}$ and $\mathrm{NS}_\delta \to 1/2$. TRIBES is balanced and noise sensitive, so correlation between $f(x)$ and $f(y)$ vanishes -- the extreme opposite of \(\mathrm{MAJ}_n\). ODonnell14
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\Theta(\sqrt n)\)· putative At least $\mathrm{Q} = \Omega(\sqrt n)$. The matching upper bound is the ordinary $\sqrt s \cdot \sqrt w$ algorithm with both Grover layers replaced by robust amplitude amplification, which tolerates bounded-error inputs with no log overhead. So the quantum speedup over $\mathrm{R} = \Theta(n)$ survives noisy oracles intact. HoyerMoscadeWolf03 BNRdW05
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(n\) putative A parity obstruction. An unambiguous $b$-cover partitions $f^{-1}(b)$ into subcubes of sizes $2^{n-c_i}$, so if $|f^{-1}(b)|$ is odd some $c_i$ must equal $n$. Here $|f^{-1}(0)| = (2^w-1)^s$ is a power of an odd number, hence odd, and $|f^{-1}(1)| = 2^n - (2^w-1)^s$ is odd too. So $\mathrm{UC}^0 = \mathrm{UC}^1 = n$, far above $\mathrm{C} = \Theta(n/\log n)$ and $\mathrm{C}^1 = \Theta(\log n)$.
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(n\) putative Both sides are $n$ by the parity argument on the \(\mathrm{UC}(f)\) line, so the one-sided minimum does not help. TRIBES is therefore useless as a witness for the [BHT17] $\mathrm{C}$-vs-$\mathrm{UC}_{\min}$ question, despite its very lopsided certificate complexities. BHT17
\(\mathrm{SP}(f)\) Subcube partition complexity \(n\) putative A subcube partition induces an unambiguous cover on each side, so $\mathrm{SP} \ge \mathrm{UC} = n$ by the parity argument on the \(\mathrm{UC}(f)\) line; and $\mathrm{SP} \le \mathrm{D} = n$. The $\Theta(\log n)$-size $1$-certificates cannot be assembled into a partition.
\(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity \(n\) putative At most $\mathrm{D} = n$. For the lower bound, the $0/1$ representation $1-\prod_j(1-\prod_{i\in T_j}x_i)$ has top monomial coefficient $(-1)^{s+1} = \pm1$, so the $\pm1$-valued $g = 1-2f$ has $\hat g([n]) = \pm2^{-(n-1)}$ -- the largest granularity an $n$-bit function can have -- and $\mathrm{D}^{\oplus} \ge \mathrm{gran}+1 = n$ [ChistopolskayaPodolskii18]. Parity queries buy nothing. ChistopolskayaPodolskii18
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) \(\Theta(n)\) Squeezed by the [CGLMSG23] sandwich $\max\{\mathrm{Adv}^2,\mathrm{R}_0\} \le \mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$: below, $\mathrm{Adv}^2 = \Theta(n)$ and $\mathrm{R}_0 = \Theta(n)$; above, $\mathrm{C}^0\mathrm{C}^1 = \Theta(n/\log n)\cdot\Theta(\log n) = \Theta(n)$. The lopsidedness of the two certificate complexities is exactly what makes this cell close, unlike \(\mathrm{OMB}_n\) where the same sandwich leaves a quadratic gap. CGLMSG23
\(\mathrm{rdeg}(f)\) Rational degree \(\Theta(n/\log n)\) putative Exactly $s$. From $\mathrm{rdeg}(f) = \max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\}$ with $\mathrm{ndeg}(f) = w$ recorded above: $\bar f$ is an AND of ORs, and $\prod_j\big(\sum_{i \in T_j}(1-x_i)\big)$ is nonzero exactly when every tribe contains a $0$, giving $\mathrm{ndeg}(\bar f) \le s$; setting $w-1$ bits of each tribe to $1$ restricts $\bar f$ to $\mathrm{AND}_s$, whose nondeterministic degree is $s$, giving the match. So $\mathrm{rdeg} = \Theta(n/\log n)$ against $\deg = n$ -- a genuine, if only logarithmic, rational-vs-exact degree gap on a monotone function.
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity \(\Theta(n/\log n)\)· putative Equal to $\Theta(s)$, strictly below $\mathrm{R} = \Theta(n)$: product distributions are provably not worst case for TRIBES. Lower: under the uniform distribution a depth-$m$ tree touches at most $m$ tribes, and each of the $\ge s-m$ untouched tribes is independently all-ones with probability $2^{-w} = \Theta(1/s)$, so for $m = \varepsilon s$ the answer is still an almost-fair coin at every leaf. Upper: for any product distribution, resolve tribes one at a time, querying each tribe's bits in increasing order of $\Pr[x_i=1]$; the expected cost of resolving a tribe with all-ones probability $q_j$ is at most $\sum_{t<w} q_j^{t/w}$, which is $O(1)$ in the only hard regime $q_j = \Theta(1/s)$ (larger $q_j$ makes some tribe satisfied almost surely, smaller makes the answer almost surely $0$). $O(s)$ queries then resolve every tribe except with probability $e^{-\Omega(s)}$. Marked medium confidence because the upper bound is a case analysis over product distributions rather than a single clean argument.
\(\mathrm{spar}(f)\) Fourier sparsity \(\Theta(2^n)\) putative Full support, or one short of it. Write $\mathrm{Tribes} = 1 - \prod_{j=1}^{s}(1-A_j)$ with $A_j = \prod_{i \in T_j}x_i = 2^{-w}\prod_{i \in T_j}(1-\chi_i)$. The tribes are on disjoint variables, so the Fourier coefficient of $\chi_S$ in the product factorises over $j$, the factor being $1-2^{-w}$ when $S \cap T_j = \emptyset$ and $-(-1)^{|S \cap T_j|}2^{-w}$ otherwise -- never zero. So every nonempty $S$ carries a nonzero coefficient. The empty set is the only possible exception: in the $\pm1$ encoding $\hat g(\emptyset) = 2(1-2^{-w})^{s}-1$, which vanishes exactly when the function is perfectly balanced. Maximal sparsity, in contrast with the $2^{n-1}$ of \(\mathrm{MAJ}_n\) and \(\mathrm{EH}_n\), which are forced down by a symmetry.
\(\widetilde{\deg}_{+}(f)\) One-sided approximate degree \(\Omega(\sqrt{\log n}),\ O(\log n)\) putative Upper: $p(x) = \sum_j \prod_{i \in T_j} x_i$ has degree $w$, equals $0$ on every $0$-input (each tribe has a zero) and is $\ge 1$ on every $1$-input -- a one-sided approximant of degree $w = \Theta(\log n)$, exponentially below $\widetilde{\deg} = \Theta(\sqrt n)$. Lower: restricting all but one tribe to contain a $0$ leaves $\mathrm{AND}_w$, and $\mathrm{odeg}(\mathrm{AND}_w) = \widetilde{\deg}(\mathrm{AND}_w) = \Theta(\sqrt w)$ by the single-slice normalisation argument spelled out on the \(\mathrm{EH}_n\) $\mathrm{odeg}$ line. This is the zoo's cleanest illustration that one-sidedness is worth an exponential factor for a monotone DNF.
\(\mathrm{sdeg}(f)\) Sign degree \(\Omega(\sqrt{\log n}),\ O(\log n)\) putative Upper: $\mathrm{sdeg} \le \mathrm{odeg} \le w = \Theta(\log n)$, since a one-sided approximant minus $1/2$ sign-represents. Lower: restrict to $m = \sqrt w$ tribes (force a $0$ into each of the others), leaving $\mathrm{OR}_m \circ \mathrm{AND}_{m^2}$, the negation of the Minsky--Papert function, whose threshold degree is $\Omega(m)$ [MinskyPapert69]. Threshold degree is negation-invariant, so $\mathrm{sdeg}(\mathrm{Tribes}) = \Omega(\sqrt{\log n})$. MinskyPapert69
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(\Omega(n/\log n),\ O(n)\)· putative Upper: $\mathrm{cjdeg}_{\varepsilon}(f) \le \mathrm{D}(f) = n$. Lower: fixing $w-1$ variables of each tribe to $1$ leaves $\vee_s$ on the remaining $s = \Theta(n/\log n)$ variables, and a conical junta restricts to a conical junta of no larger width, so the \(\mathrm{OR}_n\) line gives $\mathrm{cjdeg} = \Omega(s)$. This beats the $\widetilde{\deg}_{\varepsilon} = \Theta(\sqrt n)$ lower bound; whether the truth is $\Theta(n)$ is open.
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(\Omega(\sqrt n),\ O(n)\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{D}(f)$. The truth is presumably $\Theta(n)$, matching $\mathrm{R}$, but the partition bound is not known to reach $\mathrm{R}$ for TRIBES and the recorded $\mathrm{RC} = \Theta(n/\log n)$ is already below $\mathrm{R}$, so no better lower bound is claimed here.
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(\Omega(\sqrt n),\ O(n)\)· Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$. Same caveat as the \(\mathrm{prt}_{\varepsilon}(f)\) line above.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta(n)\) Yao's minimax: $\max_\mu \mathrm{D}^{\mu}_{1/3}(f) = \mathrm{R}_{1/3}(f) = \Theta(n)$. Worth contrasting with the \(\mathrm{D}^{\mathrm{prod}}(f)\) line, $\Theta(n/\log n)$: no product distribution is hard enough, so the maximising $\mu$ must correlate the variables inside a tribe. Yao77
\(\mathrm{cbs}(S)\) Critical block sensitivity \(\Theta(n/\log n)\) Degenerate for Boolean functions: every input is critical and the only solution function is $f$ itself, so $\mathrm{cbs}(f) = \mathrm{bs}(f)$, which is $\Theta(n/\log n)$ here by the \(\mathrm{bs}(f)\) line. GoosPitassi14
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\Theta(n)\) Degenerate for Boolean functions: there is a single correct output, so the canonical answer is forced and $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$ $= \Theta(n)$. CDM23
\(\chi(f)\) Conflict complexity \(\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
\(\hat{L}_1(f)\) Spectral norm \(2^{\Theta(n/\log n)}\) putative Exactly $2^{s(1\pm o(1))}$ with $s = \Theta(n/\log n)$ tribes. Write $f = 1 - \prod_j (1-A_j)$ with $A_j = \prod_{i \in T_j} x_i$. In the $\pm1$ basis $A_j = 2^{-w}\prod_{i \in T_j}(1-\chi_i)$ has $\hat L_1(A_j) = 1$, so $\hat L_1(1-A_j) = (1-2^{-w}) + (1-2^{-w}) = 2 - 2^{1-w}$; the tribes are variable-disjoint, so the norms multiply and $\hat L_1\big(\prod_j (1-A_j)\big) = (2-2^{1-w})^s$. Subtracting the product from $1$ changes only the constant term. Since $w = \Theta(\log n)$, this is $2^{\Theta(n/\log n)}$ -- exponentially large, but exponentially far below the maximum $2^{\mathrm{D}} = 2^n$. ODonnell14
\(\mathrm{DTsize}(f)\) Decision tree size \(2^{\Omega(n/\log n)},\ 2^{O(n\log\log n/\log n)}\) putative Lower: the subcube of a $0$-leaf must contain a $0$ in each of the $s$ tribes, so it has codimension at least $s$ and measure at most $2^{-s}$; the $0$-leaves cover a set of measure $\Pr[f=0] \to 1/2$, so there are at least $2^{s-1}$ of them, and $s = \Theta(n/\log n)$. Upper: the natural tree reads one tribe at a time, stopping at the first $0$ inside a tribe, and its leaf count satisfies $T(j) = w\,T(j-1)+1$, giving $T(s) \le 2w^s = 2^{O(s\log w)} = 2^{O(n\log\log n/\log n)}$. The $\log\log n$ gap is left open.
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\Omega(n),\ O(n\log n)\)· Lower: $\mathrm{N}_p \ge \mathrm{R} = \Theta(n)$. Upper: $O(\mathrm{R}\log\mathrm{R})$ by repeating each query. The influence-based bound $\mathrm{N}_p = \Omega(\mathrm{I}\log\mathrm{I})$ [GLX26noisy] gives only $\Omega(\log n\log\log n)$ here, since $\mathrm{I} = \Theta(\log n)$, so as at \(\mathrm{OMB}_n\) there is no evidence that the repetition log is needed. FRPU94 GLX26noisy
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree \(O(\log n)\) putative Upper bound only, and it is $w$: put $S(x) = \sum_j \prod_{i \in T_j} x_i$, of degree $w$, and take $r = 3S/(1+3S)$. On $0$-inputs no tribe is all-ones, so $S = 0$ and $r = 0$; on $1$-inputs $S \ge 1$ and $r \ge 3/4$. No lower bound beyond the trivial $1$ is known -- the restriction to a single tribe only gives $\mathrm{rdeg}_{\varepsilon}(\wedge_w) = 1$, as at \(\mathrm{AND}_n\). MahadevdeWolf15
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(O(\log n)\) $\mathrm{PostQ}_{\varepsilon}(f) = \Theta(\mathrm{rdeg}_{\varepsilon}(f))$ [MahadevdeWolf15] applied to the \(\mathrm{rdeg}_{\varepsilon}(f)\) line, hence an upper bound only. Postselection brings TRIBES from $\mathrm{R} = \Theta(n)$ down to at most $O(\log n)$. MahadevdeWolf15

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. 130 in total, strongest first.

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

Separations it witnesses

  • Unbounded, and on a monotone read-once DNF: $\mathrm{s}^0 = \Theta(n/\log n)$ against $\mathrm{s}^1 = \Theta(\log n)$, a ratio of $n/\log^2 n$. The same asymmetry runs through $\mathrm{bs}^0$ vs $\mathrm{bs}^1$ and $\mathrm{C}^0$ vs $\mathrm{C}^1$; it is the reason TRIBES is the KKL extremal example.
  • Unbounded: $\mathrm{C} = \Theta(n/\log n)$ at a $0$-input (every tribe must be shown to fail) against $\mathrm{C}_{\min} = \Theta(\log n)$ at a $1$-input (exhibit one satisfied tribe).

Cited as a witness by