Q The Query Complexity Zoo
\(\lambda^{\mathrm{cert}}(f)\)

Spectral sensitivity certification

Spectral sensitivity of the hardest known-input certification promise; exactly the square root of sensitivity.

Definition

$\lambda^{\mathrm{cert}}(f)=\max_{z\in D}\lambda(f_z^{\mathrm{cert}})$. The sensitivity graph of this promise is a star centred on $z$ with $\mathrm{s}(f,z)$ leaves, so $\lambda^{\mathrm{cert}}(f)=\sqrt{\mathrm{s}(f)}$ exactly [KLLPV26, Theorem 42]. On a partial function it can be zero.

Basic facts

  • $\lambda^{\mathrm{cert}}\le\lambda$ by restriction monotonicity.

Equivalent / near-equivalent measures

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\lambda^{\mathrm{cert}}(f)\). “\(\lambda^{\mathrm{cert}}(f)\) in terms of it” is the pair with \(\lambda^{\mathrm{cert}}(f)\) on the left (the matrix row); the other column is the reverse. Each cell gives, per setting, the exponent range a,b of the best bounds known — \(\mathrm{M_1} = \Omega(\mathrm{M_2}^{a})\) below and \(\mathrm{M_1} = O(\mathrm{M_2}^{b})\) above, so \(a = b\) means settled — or a glyph where no polynomial bound exists at all. These are derived, not just read off the exponent table, so they are present for pairs the table does not cover. A cell with no entry for a setting is one where the zoo has nothing at that setting, and a — one where the ordered pair is empty in all three; derived marks a direction with no hand-written relation record behind it, which is the common case and not a hole.

Other measure \(\lambda^{\mathrm{cert}}(f)\) in terms of it It in terms of \(\lambda^{\mathrm{cert}}(f)\)
\(\mathrm{s}(f)\) Sensitivity total0.5,0.5 partial0.5,0.5 derived open pair → total2,2 partial2,2 derived open pair →
\(\lambda(f)\) Spectral sensitivity total1,1 partial1,1 open pair → total2,2 partial2,2 derived open pair →
\(\mathrm{QC}(f)\) Quantum certificate complexity total1,1 partial1,1 derived open pair → total2.1308,4 partial2.1308,? derived open pair →
\(\overline{\deg}^{\mathrm{cert}}(f)\) Bounded degree certification complexity total0.8155,1 partial0.6667,1 derived open pair → total2.1308,4 partial4,? derived open pair →

The 4 above are this entry’s hand-picked neighbours; the other 89 are everything else in the zoo, by category.

Known values

FunctionValueNotes
OR total \(\sqrt n\) Theorem 42: λcert=√s, with s=n. KLLPV26
AND total \(\sqrt n\) Theorem 42: λcert=√s, with s=n. KLLPV26
PARITY total \(\sqrt n\) Theorem 42: λcert=√s, with s=n. KLLPV26
MAJORITY total \(\sqrt{(n+1)/2}\) Theorem 42: λcert=√s, with s=(n+1)/2. KLLPV26
ADDRESS / multiplexer total \(\sqrt{k+1}\) Theorem 42: λcert=√s, and s=k+1. KLLPV26