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
| Measure | Value | Notes |
|---|---|---|
| \(\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.
-
\(\mathrm{D}^{\oplus}(f_n) \to \infty \ \text{ while } \ \deg_2(f_n) = O(1)\)from \(\mathrm{D}^{\oplus}(f) = \ge n/2 + 1\) against \(\deg_2(f) = 2\)
-
\(\mathrm{RC}(f_n) \to \infty \ \text{ while } \ \mathrm{MaxInf}(f_n) = O(1)\)from \(\mathrm{RC}(f) = \Theta(n)\) against \(\mathrm{MaxInf}(f) = 1/2\)
-
\(\hat{L}_1(f_n) = 2^{\Omega(\mathrm{SP}(f_n))}\)from \(\hat{L}_1(f) = 2^{n/2}\) against \(\mathrm{SP}(f) = n\)
-
\(\mathrm{D}^{\oplus}(f_n) \to \infty \ \text{ while } \ \mathrm{MaxInf}(f_n) = O(1)\)from \(\mathrm{D}^{\oplus}(f) = \ge n/2 + 1\) against \(\mathrm{MaxInf}(f) = 1/2\)
-
\(\mathrm{RC}(f_n) \to \infty \ \text{ while } \ \deg_2(f_n) = O(1)\)from \(\mathrm{RC}(f) = \Theta(n)\) against \(\deg_2(f) = 2\)
-
\(\hat{L}_1(f_n) = 2^{\Omega(\mathrm{D}^{\mathrm{na}}(f_n))}\)from \(\hat{L}_1(f) = 2^{n/2}\) against \(\mathrm{D}^{\mathrm{na}}(f) = n\)
-
\(\hat{L}_1(f_n) \to \infty \ \text{ while } \ \deg_2(f_n) = O(1)\)from \(\hat{L}_1(f) = 2^{n/2}\) against \(\deg_2(f) = 2\)
-
\(\mathrm{spar}(f_n) \to \infty \ \text{ while } \ \mathrm{MaxInf}(f_n) = O(1)\)from \(\mathrm{spar}(f) = 2^n\) against \(\mathrm{MaxInf}(f) = 1/2\)
-
\(\mathrm{sdeg}(f_n) = \Omega\big(\mathrm{RC}(f_n)\big)\)from \(\mathrm{sdeg}(f) = \Theta(n)\) against \(\mathrm{RC}(f) = \Theta(n)\)
-
\(\hat{L}_1(f_n) \to \infty \ \text{ while } \ \mathrm{MaxInf}(f_n) = O(1)\)from \(\hat{L}_1(f) = 2^{n/2}\) against \(\mathrm{MaxInf}(f) = 1/2\)
-
\(\mathrm{spar}(f_n) \to \infty \ \text{ while } \ \deg_2(f_n) = O(1)\)from \(\mathrm{spar}(f) = 2^n\) against \(\deg_2(f) = 2\)
-
\(\widetilde{\deg}_{+}(f_n) = \Omega\big(\mathrm{RC}(f_n)\big)\)from \(\widetilde{\deg}_{+}(f) = \Theta(n)\) against \(\mathrm{RC}(f) = \Theta(n)\)
-
\(\dim_{\mathbb{F}_2}(f_n) \to \infty \ \text{ while } \ \deg_2(f_n) = O(1)\)from \(\dim_{\mathbb{F}_2}(f) = n\) against \(\deg_2(f) = 2\)
-
\(\hat{L}_1(f_n) = 2^{\Omega(\mathrm{R}^{\mathrm{na}}(f_n))}\)from \(\hat{L}_1(f) = 2^{n/2}\) against \(\mathrm{R}^{\mathrm{na}}(f) = \Theta(n)\)
… and 6 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.
Separations it witnesses
-
The extreme case: $\deg = n$ against $\deg_2 = 2$. Real degree and $\mathbb{F}_2$-degree are unrelated in this direction.
-
Both at their maxima simultaneously: $\mathrm{spar} = 2^n$ and $\mathrm{L}_1 = 2^{n/2} = \sqrt{\mathrm{spar}}$, which is the equality case of $\mathrm{L}_1 \le \sqrt{\mathrm{spar}}$.
Cited as a witness by
-
\(\mathrm{D}^{\oplus}(\mathrm{IP}_n) = \ge n/2 + 1 \to \infty, \qquad \mathrm{NS}_{\delta}(\mathrm{IP}_n) = \tfrac12\big(1-(1-\delta)^n\big) \to \tfrac12\)
-
\(\hat{L}_1(\mathrm{IP}_n) = 2^{n/2} \to \infty, \qquad \mathrm{NS}_{\delta}(\mathrm{IP}_n) = \tfrac12\big(1-(1-\delta)^n\big) \to \tfrac12\)
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.