Q The Query Complexity Zoo
\(\mathrm{IP}_n\)

Inner product mod 2

Everything combinatorial is $n$ and everything Fourier is as spread out as it can be: the flat spectrum makes $\mathrm{L}_1 = 2^{n/2}$ with $\mathrm{spar} = 2^n$.

total basic arity: $n = 2m$ bits, read as a pair $(x,y)\in\{0,1\}^m\times\{0,1\}^m$— also: IP2, the bent function, x \cdot y \bmod 2

Description

$\mathrm{IP}_n(x,y) = \bigoplus_{i=1}^{m} x_i \wedge y_i$. As a $\pm1$-valued function $F(x,y) = (-1)^{x\cdot y}$ it is bent: every one of its $2^n$ Fourier coefficients has the same magnitude $2^{-n/2}$, the flattest a Boolean spectrum can be. That single fact fixes every Fourier quantity below.

IP is the standard gadget in lifting theorems, and the standard example of a function that is trivial over $\mathbb{F}_2$ ($\deg_2 = 2$) and maximally hard over $\mathbb{R}$ ($\deg = n$).

Formal definition

$$\mathrm{IP}_n(x,y) = \sum_{i=1}^{m} x_i y_i \bmod 2, \qquad n = 2m.$$

Measure values

MeasureValueNotes
\(\mathrm{D}(f)\) Deterministic query complexity \(n\) From $\deg = n$ below, and $\deg \le \mathrm{D}$.
\(\deg(f)\) Exact degree \(n\) The multilinear extension is $\tfrac12\big(1 - \prod_{i=1}^{m}(1-2x_iy_i)\big)$, whose leading term $-\tfrac12(-2)^{m}\prod_i x_iy_i$ has degree $2m = n$ and does not cancel.
\(\deg_2(f)\) Mod-2 degree \(2\) Over $\mathbb{F}_2$ it is literally $\sum_i x_iy_i$. The gap between this and $\deg = n$ is the whole reason IP is used as a lifting gadget.
\(\mathrm{s}(f)\) Sensitivity \(n\) Flipping $x_i$ changes the value iff $y_i = 1$, and symmetrically, so $\mathrm{s}(x,y) = |x| + |y|$; at $x = y = 1^m$ that is $n$.
\(\mathrm{bs}(f)\) Block sensitivity \(n\) Pinned: $\mathrm{s} \le \mathrm{bs} \le \mathrm{D}$ and both ends are $n$. The same sandwich fixes $\mathrm{fbs}$, $\mathrm{C}$, $\mathrm{RC}$, $\mathrm{UC}$ and $\mathrm{Dna}$ at $n$.
\(\mathrm{C}(f)\) Certificate complexity \(n\) As above.
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(n\) As above.
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(n)\) Sandwiched: $\mathrm{bs} \le 3\mathrm{R}$ (indeed $\mathrm{R} = \Omega(\mathrm{s})$) and $\mathrm{R} \le \mathrm{D} = n$.
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity \(\Theta(n)\) The zoo's own \(\mathrm{noisyR}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\) entry records $\mathrm{R}(f)=\Theta(n)\Rightarrow\mathrm{noisyR}(f)=\Theta(\mathrm{R}(f))$ [CKMPSS23], and the recorded $\mathrm{R}$ is linear in the arity here -- the function reads all $n$ bits, so buying unbiased copies buys nothing. CKMPSS23
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Theta(n)\) Sandwiched: $\mathrm{Q} \ge \widetilde{\deg}/2 \ge \mathrm{sdeg}/2 \ge n/4$ and $\mathrm{Q} \le \mathrm{D} = n$.
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(\Theta(n)\) Sandwiched: $\mathrm{Q}_E \ge \deg/2 = n/2$ and $\mathrm{Q}_E \le \mathrm{D} = n$. (With a parity oracle the answer would be $m+1$ or so; see $\mathrm{D}^{\oplus}$ below.)
\(\mathrm{sdeg}(f)\) Sign degree \(\Theta(n)\) Restricting $y = 1^m$ leaves $\mathrm{PARITY}_m$, so $\mathrm{sdeg} \ge \mathrm{sdeg}(\mathrm{PARITY}_{n/2}) = n/2$; and $\mathrm{sdeg} \le \deg = n$.
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(\Theta(n)\) Between $\mathrm{sdeg} = \Omega(n)$ and $\deg = n$.
\(\mathrm{spar}(f)\) Fourier sparsity \(2^n\) Bent: no Fourier coefficient vanishes. This is the maximum possible, and with \(\oplus_n\) (where $\mathrm{spar} = 1$) it brackets the range.
\(\hat{L}_1(f)\) Spectral norm \(2^{n/2}\) $2^n$ coefficients of magnitude $2^{-n/2}$ each. Bent functions maximise $\mathrm{L}_1$ among all Boolean functions, so this is the extreme point of $\mathrm{L}_1 \le 2^{n/2}$.
\(\dim_{\mathbb{F}_2}(f)\) Fourier dimension \(n\) The support is all of $\mathbb{F}_2^n$, so its span is everything.
\(\mathrm{I}(f)\) Total influence (L2 influence) \(n/2\) $\mathrm{I}(f) = \sum_S |S|\hat f(S)^2 = 2^{-n}\sum_{S}|S| = 2^{-n}\cdot n2^{n-1}$.
\(\mathrm{MaxInf}(f)\) Maximum influence \(1/2\) Every coordinate has $\mathrm{Inf}_i = \sum_{S \ni i}\hat f(S)^2 = 2^{-n}2^{n-1} = 1/2$; the spectrum is flat, so no coordinate is special.
\(\mathrm{Var}(f)\) Variance \(1-2^{-n}\) $4p(1-p)$ at $p = \tfrac12 - 2^{-n/2-1}$; equivalently $1-\mathrm{Stab}_0$ from the \(\mathrm{Stab}_{\rho}(f)\) entry.
\(\mathrm{osss}(f)\) OSSS number \(2(1-2^{-n})\) putative $\mathrm{MaxInf} = 1/2$ on a flat spectrum, so the ratio is $2\mathrm{Var}$. Two queries against $\mathrm{D} = n$: OSSS is blind to a function all of whose coordinates look alike.
\(\mathrm{nsr}(f)\) Noise robustness \(n/\ln 2\,(1+o(1)) = \Theta(n)\) putative $\tfrac12(1-(1-\delta)^n) = \mathrm{Var}/4$ at $(1-\delta)^n \to \tfrac12$. Tight against $\mathrm{s} = \mathrm{D} = n$, and the exact complement of the \(\mathrm{osss}(f)\) reading: the same flat spectrum that makes OSSS useless makes the critical noise rate optimal.
\(\mathrm{Stab}_{\rho}(f)\) Noise stability \(\big(\tfrac{1+\rho}{2}\big)^{n}\) $\mathrm{Stab}_\rho = \sum_S \rho^{|S|}\hat f(S)^2 = 2^{-n}\sum_S \rho^{|S|} = 2^{-n}(1+\rho)^n$. Exponentially unstable: at any fixed $\rho < 1$ the correlation dies at a constant rate per bit.
\(\mathrm{NS}_{\delta}(f)\) Noise sensitivity \(\tfrac12\big(1 - (1-\delta)^{n}\big)\) Substituting $\rho = 1-2\delta$ into $\mathrm{Stab}$ above. So $\mathrm{NS}_\delta \to 1/2$ once $\delta \gg 1/n$ -- IP is as noise-sensitive as a random function.
\(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity \(\ge n/2 + 1\) The granularity of IP is exactly $2^{-n/2}$, so [ChistopolskayaPodolskii18] gives $\mathrm{D}^{\oplus} \ge n/2 + 1$. Upper bound: the trivial $n$. The factor $2$ is open as far as I know -- note $\mathrm{D}^{\oplus} \ge n/2$ also follows from bentness, since an affine subspace on which a bent function is constant has dimension at most $n/2$. ChistopolskayaPodolskii18
\(\mathrm{RC}(f)\) Randomized certificate complexity \(\Theta(n)\) Sandwiched: $\mathrm{fbs}(f) \le \mathrm{RC}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
\(\mathrm{FC}(f)\) Fractional certificate complexity \(n\) Sandwiched: $\mathrm{s}(f) \le \mathrm{FC}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(n\) Sandwiched: $\mathrm{s}(f) \le \mathrm{R}_{0}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
\(\mathrm{CA}(f)\) Classical adversary bound \(\Theta(n)\) $\mathrm{CA}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$ (\(\mathrm{CA}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = n$ here.
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) \(\Theta(n)\) $\mathrm{CG}^{\mathrm{pub}}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$ (\(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = n$ here.
\(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity \(\Theta(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)\) 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{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\Theta(n)\) Sandwiched: $\mathrm{Q}_{\varepsilon}(f) \le \mathrm{Q}_{0}(f) \le \mathrm{D}(f)$, with $\mathrm{Q}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\Theta(n)\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(n)$ here.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Theta(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(n)$ here.
\(\widetilde{\deg}_{+}(f)\) One-sided approximate degree \(\Theta(n)\) Sandwiched: $\mathrm{sdeg}(f) \le \widetilde{\deg}_{+}(f) \le \mathrm{D}(f)$, with $\mathrm{sdeg}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \bar{\mathrm{R}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
\(\chi(f)\) Conflict complexity \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \chi(g) \le \mathrm{D}(f)$, with both ends $n$ here.
\(\bar{\chi}(f)\) Max-conflict complexity \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \bar{\chi}(g) \le \mathrm{D}(f)$, with both ends $n$ here.
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{LR}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate \(\Theta(n)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}^{*}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) \(\Theta(n^2)\) putative Sandwiched: $\mathrm{Adv}(f)^2 \le \mathrm{CG}(f) \le \mathrm{C}^0(f)\,\mathrm{C}^1(f)$ [CGLMSG23], with $\mathrm{Adv} = \Theta(n)$ and $\mathrm{C}^0\mathrm{C}^1 = \Theta(n^2)$ here. Note that this is above the arity: the private-coin game is the one certificate-game variant that is not bounded by $\mathrm{D}$. Inner product behaves exactly like \(\oplus_n\) here, and for the same reason -- distance-$1$ pairs force both players to guess the same index out of $\Theta(n)$ candidates independently. CGLMSG23
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Theta(n)\) Sandwiched: $\mathrm{Q}_{\varepsilon}(f) \le \mathrm{MAdv}(f) \le \mathrm{D}(f)$, with $\mathrm{Q}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(\Theta(n)\) Sandwiched: $\mathrm{sdeg}(f) \le \mathrm{cjdeg}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\mathrm{sdeg}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
\(\deg_p(f)\) Mod-p degree \(2 \text{ for } p = 2;\ n \text{ for } p > 2\) Over $\mathbb{F}_2$ the inner product literally is $\sum_{i} x_i y_i$, a quadratic form -- degree $2$ on $n = 2m$ variables. Over any other field the representation is $\tfrac12\big(1 - \prod_i (1 - 2x_iy_i)\big)$ and the degree is $n$. Together with $\deg = n$, $\mathrm{s} = n$ and $\mathrm{D} = n$, this makes IP the standard example that $\deg_2$ carries no information about query complexity.
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(\Theta(n)\)· Sandwiched: $\mathrm{s}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $n$ here. The lower end is the zoo's own observation that the [JainKlauck10] techniques survive the relaxation of the completeness constraint (see the $\mathrm{RC}\to\overline{\mathrm{prt}}$ record); the upper end is unconditional.
\(\lambda(f)\) Spectral sensitivity \(n/\sqrt2\) Write $\mathrm{IP}_n = \mathrm{PARITY}_{m} \circ \mathrm{AND}_2$ with $m = n/2$ and use exact multiplicativity of $\lambda$ [ABKRT21]: $\lambda = m \cdot \sqrt 2 = n/\sqrt2$. Consistent with $\sqrt{\mathrm{s}} \le \lambda \le \mathrm{s}$ at $\mathrm{s} = n$, and with $\mathrm{Q} = \Theta(n) = \Omega(\lambda)$; like \(\oplus_n\) and unlike \(\mathrm{AND}_n\), the inner product sits at the top of that range.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(n/2\) putative A certificate must kill every term $x_iy_i$: for each $i$ it must fix $x_i=0$, or $y_i=0$, or both $x_i=y_i=1$. So $\mathrm{C}(x,y) = m + |x \wedge y|$ exactly. The minimum is $m = n/2$, attained at every input with $x \wedge y = 0$ (e.g. $x = 0^m$), and the maximum is $2m = n$ at $x=y=1^m$ -- which is where the recorded $\mathrm{C} = n$ comes from.
\(\mathrm{C}^0(f)\) 0-certificate complexity \(\Theta(n)\) putative From $\mathrm{C}(x,y) = m + |x\wedge y|$: the top value $n$ needs $x = y = 1^m$, which has $\mathrm{IP} = m \bmod 2$, and the best the other side can do is $|x\wedge y| = m-1$. So $\{\mathrm{C}^0, \mathrm{C}^1\} = \{n,\, n-1\}$, in an order set by the parity of $m$.
\(\mathrm{C}^1(f)\) 1-certificate complexity \(\Theta(n)\) putative See $\mathrm{C}^0$: the pair is $\{n, n-1\}$ and which side gets which depends only on the parity of $m$.
\(\mathrm{s}^0(f)\) 0-sensitivity \(\Theta(n)\) putative From $\mathrm{s}(x,y) = |x|+|y|$: the maximum $n$ is only at $x=y=1^m$ (value $m \bmod 2$) and the other side tops out at $n-1$. So $\{\mathrm{s}^0,\mathrm{s}^1\} = \{n, n-1\}$.
\(\mathrm{s}^1(f)\) 1-sensitivity \(\Theta(n)\) putative See $\mathrm{s}^0$.
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(\Theta(n)\) Between $\mathrm{s}^0 = \Theta(n)$ and $\mathrm{bs} = n$.
\(\mathrm{bs}^1(f)\) 1-block sensitivity \(\Theta(n)\) Between $\mathrm{s}^1 = \Theta(n)$ and $\mathrm{bs} = n$.
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(n\) putative The natural decision tree -- for each $i$ read $x_i$, and read $y_i$ only if $x_i=1$ -- is a subcube partition, hence an unambiguous certificate family, of width $\max_x (m + |x\wedge y|) = n$. And $\mathrm{UC} \ge \mathrm{C} = n$.
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(n/2\) putative That same partition gives the input $x = 0^m$ a certificate of size $m$, and no certificate anywhere is smaller than $\mathrm{C}_{\min} = m$.
\(\mathrm{SP}(f)\) Subcube partition complexity \(n\) A width-$w$ subcube partition is in particular an unambiguous family, so $\mathrm{UC} \le \mathrm{SP} \le \mathrm{D}$, and both ends are $n$ here.
\(\mathrm{EC}(f)\) Expectational certificate complexity \(n\) Between $\mathrm{fbs} = n$ and $\mathrm{C} = n$.
\(\mathrm{rank}(f)\) Decision tree rank \(n/2\) putative Upper: in the natural tree, the node handling index $i$ has one child of rank $r$ (the branch $x_i=0$) and one of rank $r+1$ (the branch $x_i=1$, which then splits on $y_i$), so the rank grows by exactly $1$ per index: $m = n/2$. Lower: a Delayer who defers on every query survives at least $\mathrm{C}_{\min}$ rounds, so $\mathrm{rank}(f) \ge \mathrm{C}_{\min}(f) = m$. A clean factor-$2$ gap below $\mathrm{D} = n$: half of IP's depth is caterpillar.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(n\) Every variable is relevant, so non-adaptively you read all of them.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(n)\) Between $\mathrm{R} = \Theta(n)$ and $n$.
\(\mathrm{cbs}(S)\) Critical block sensitivity \(n\) For a Boolean function every input is critical and the solution function is forced, so $\mathrm{cbs}$ degenerates to $\mathrm{bs}$ (\(\mathrm{cbs}(S)\) vs \(\mathrm{bs}(f)\)); here $\mathrm{bs} = n$.
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\Theta(n)\) For a Boolean function the canonical answer is forced, so $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$ (\(\mathrm{psD}(S)\) vs \(\mathrm{R}_{\varepsilon}(f)\)); here $\mathrm{R} = \Theta(n)$.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta(n)\) Worst case over $\mu$: Yao's minimax gives $\max_\mu \mathrm{D}^{\mu}_{\varepsilon}(f) = \mathrm{R}_{\varepsilon}(f) = \Theta(n)$. Yao77
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity \(\Theta(n)\) putative The uniform distribution is already hard, and it is a product distribution. A depth-$d$ tree leaves at least $m-d$ index pairs $(x_i,y_i)$ entirely free, and conditioned on any leaf the value is the XOR of that many independent $\mathrm{Bernoulli}(1/4)$ terms, whose bias is $2^{-(m-d)}$; error $\le 1/3$ therefore forces $d \ge m-1 = n/2 - 1$. Upper: $\mathrm{D}^{\mathrm{prod}} \le \mathrm{R} = \Theta(n)$.
\(\mathrm{RS}(f)\) Sabotage complexity \(\Theta(n)\) Sandwiched: $\mathrm{CA}(f) \le \mathrm{RS}(f) \le \mathrm{R}(f)/(1-2\varepsilon)$, and $\mathrm{CA} = \Theta(\mathrm{fbs}) = \Theta(n)$ meets $\mathrm{R} = \Theta(n)$.
\(\mathrm{QC}(f)\) Quantum certificate complexity \(\Theta(\sqrt n)\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{RC}(f)}) = \Theta(\sqrt{\mathrm{fbs}(f)})$ for every $f$ [Aaronson08], and $\mathrm{fbs} = n$ here. So quantum certificate complexity is a full square root below $\mathrm{Q} = \Theta(n)$: verification is cheap even though computation is not. Aaronson08
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\Theta(n\log n)\) Pinned from both sides. Lower: $\mathrm{N}_p(f) = \Omega(\mathrm{I}(f)\log \mathrm{I}(f))$ [GLX26noisy] with $\mathrm{I} = n/2$. Upper: $\mathrm{N}_p(f) = O(\mathrm{R}(f)\log \mathrm{R}(f))$ with $\mathrm{R} = \Theta(n)$. IP therefore pays the same $\log$ tax as \(\oplus_n\), and for the same reason -- its influence is maximal. GLX26noisy FRPU94
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\Theta(n)\) Lower: $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(n)$. Upper: $n$ noisy quantum queries recover all $n$ input bits with high probability [BNRdW05], so no function on $n$ bits costs more. Unlike the classical $\mathrm{N}_p = \Theta(n\log n)$ above, there is no $\log$ -- the same quantum-vs-classical noise gap as for \(\oplus_n\). BNRdW05
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(\Theta(n)\) Sandwiched: $\lambda(f) \le \mathrm{Adv}(f) \le \mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}(f))$, with $\lambda = n/\sqrt2$ and $\mathrm{Q} = \Theta(n)$. Comfortably below the certificate barrier $\sqrt{\mathrm{C}^0\mathrm{C}^1} = \Theta(n)$, which is also $\Theta(n)$ here.
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree \(\Theta(n)\) putative Lower: a rational $1/3$-approximation $p/q$ makes $(p - q/2)\,q$ a sign-representing polynomial of degree $\le 2\,\mathrm{rdeg}_{\varepsilon}$, so $\mathrm{rdeg}_{\varepsilon}(f) \ge \mathrm{sdeg}(f)/2 = \Omega(n)$. Upper: $\mathrm{rdeg}_{\varepsilon} \le \widetilde{\deg} = \Theta(n)$. Post-selection buys nothing on the bent function.
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(\Theta(n)\) $\mathrm{PostQ}_{\varepsilon}(f) = \Theta(\mathrm{rdeg}_{\varepsilon}(f))$ [MahadevdeWolf15], and the approximate rational degree is $\Theta(n)$ here. MahadevdeWolf15
\(\mathrm{rdeg}(f)\) Rational degree \(\Theta(n)\) Sandwiched: $\mathrm{rdeg}_{\varepsilon}(f) \le \mathrm{rdeg}(f) \le \mathrm{C}(f)$, with $\mathrm{rdeg}_{\varepsilon} = \Theta(n)$ and $\mathrm{C} = n$. So IP is one of the functions on which Fortnow's question -- is $\mathrm{rdeg} = \deg^{\Omega(1)}$? -- has the most boring possible answer.
\(\mathrm{I}^{1}(f)\) Total L1 influence \(n/2\) For a Boolean-valued function the $L_1$ and $L_2$ influences coincide term by term, so $\mathrm{I}^{1}(f) = \mathrm{I}(f) = n/2$.
\(\mathrm{ndeg}(f)\) Nondeterministic degree \(\Theta(n)\) putative Upper: $p = 1 - \prod_{i}(1-2x_iy_i) = 1-(-1)^{x\cdot y}$ is nonzero exactly on $\mathrm{IP}^{-1}(1)$, degree $n$. Lower: any nondeterministic polynomial $p$ gives a sign-representing one -- $q(x) := \delta - p(x)^2$ is $>0$ on $f^{-1}(0)$ and $<0$ on $f^{-1}(1)$ for any $\delta$ below the least positive value of $p^2$ -- so $\mathrm{sdeg}(f) \le 2\,\mathrm{ndeg}(f)$ always, and $\mathrm{sdeg} = \Theta(n)$ here. Bentness leaves no room for a nondeterministic shortcut.
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity \(\Theta(n)\) $\mathrm{NQ}(f) = \lceil \mathrm{ndeg}(f)/2\rceil$ (\(\mathrm{NQ}(f)\) vs \(\mathrm{ndeg}(f)\)), and $\mathrm{ndeg} = \Theta(n)$ here. Nondeterminism buys at most a factor $2$ on the bent function -- contrast \(\mathrm{MP}_m\), where $\mathrm{NQ} = \Theta(N^{1/3})$ against $\mathrm{Q} = \Theta(\sqrt N)$. deWolf03
\(\mathrm{DTsize}(f)\) Decision tree size \(2^{\Theta(n)}\) putative Upper: the natural tree has three continuations per index ($x_i=0$; $x_i=1,y_i=0$; $x_i=1,y_i=1$), so $3^{m} = 3^{n/2}$ leaves. Lower: every leaf-subcube is monochromatic, hence of codimension $\ge \mathrm{C}_{\min} = n/2$, so there are at least $2^{n/2}$ of them.

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

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

Separations it witnesses

Cited as a witness by

Notes

Why bent is the extreme. Parseval gives $\sum_S \hat f(S)^2 = 1$, so by Cauchy-Schwarz $\mathrm{L}_1(f) = \sum_S|\hat f(S)| \le \sqrt{\mathrm{spar}(f)} \le 2^{n/2}$, with equality exactly when the spectrum is flat and full -- the definition of a bent function. Bent functions exist only for even $n$.

As a lifting gadget. $\mathrm{IP}_b$ with $b = O(\log n)$ is the gadget in the deterministic and randomized lifting theorems; the relevant parameter there is the discrepancy $2^{-b/2}$, again a restatement of bentness.