Q The Query Complexity Zoo

Relations

Every ordered pair \((M_1,M_2)\) the zoo has something to say about, with the best recorded upper bound per setting. Rows are ordered by category. Filter by typing a measure id, or click a status chip.

\(M_1\)\(M_2\)total Best upper bound recordedpartialrelationcell
\(\mathrm{D}(f)\) \(\mathrm{D}(f)\) \(\mathrm{D}(f\circ g^n) \le \mathrm{D}(f)\,\mathrm{D}(g)\) relation Settled
\(\mathrm{D}(f)\) \(\mathrm{D}^{\mathrm{na}}(f)\) Settled \(\mathrm{D}(f) \le \mathrm{D}^{\mathrm{na}}(f)\) relation Settled
\(\mathrm{D}(f)\) \(\mathrm{DTsize}(f)\) \(\mathrm{D}(f) \le \mathrm{DTsize}(f) - 1\) relation Settled
\(\mathrm{D}(f)\) \(\mathrm{rank}(f)\) No bound exists separations only →
\(\mathrm{D}(f)\) \(\mathrm{R}_{\varepsilon}(f)\) Gap \(\mathrm{D}(f) \le 27\,\mathrm{R}(f)^3\) No bound exists 2,3
\(\mathrm{D}(f)\) \(\mathrm{R}_{0}(f)\) Settled \(\mathrm{D}(f) = O(\mathrm{R}_0(f)^2)\) No bound exists 2,2
\(\mathrm{D}(f)\) \(\mathrm{R}^{1}(f)\) Settled \(\mathrm{D}(f) = O\big(\mathrm{R}^{1}(f)^2\big)\)
\(\mathrm{D}(f)\) \(\mathrm{psD}(S)\) \(\mathrm{D}(S) = O\big(\mathrm{psD}(S)^3\big) \quad (S \text{ a \emph{total} search problem})\) relation Gap
\(\mathrm{D}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) Settled \(\mathrm{D}(f) = O(\mathrm{Q}(f)^4)\) 4,4
\(\mathrm{D}(f)\) \(\mathrm{Q}_{\mathrm{E}}(f)\) Gap \(\mathrm{D}(f) \le 2\deg(f)^3 \le 16\,\mathrm{Q}_E(f)^3\) 2,3
\(\mathrm{D}(f)\) \(\deg(f)\) Gap \(\mathrm{D}(f) \le \mathrm{bs}(f)\cdot\deg(f) \le 2\deg(f)^3\) 2,3
\(\mathrm{D}(f)\) \(\widetilde{\deg}_{\varepsilon}(f)\) Settled \(\mathrm{D}(f) = O(\widetilde{\deg}(f)^4)\) 4,4
\(\mathrm{D}(f)\) \(\mathrm{rdeg}(f)\) Gap \(\mathrm{D}(f) \le 4\,\deg_{\pm}(f)^2\,\mathrm{rdeg}(f)^2 \le 16\,\mathrm{rdeg}(f)^4\) 2,4
\(\mathrm{D}(f)\) \(\mathrm{s}(f)\) Gap \(\mathrm{D}(f) \le \mathrm{bs}(f)\cdot\deg(f) \le 2\deg(f)^3 \le 2\,\mathrm{s}(f)^6\) 3,6
\(\mathrm{D}(f)\) \(\mathrm{bs}(f)\) Gap \(\mathrm{D}(f) \le \mathrm{s}(f)\,\mathrm{bs}(f)^2 \le \mathrm{bs}(f)^3\) 2,3
\(\mathrm{D}(f)\) \(\mathrm{fbs}(f)\) Gap \(\mathrm{D}(f) \le \mathrm{C}^{(1)}(f)\cdot\mathrm{bs}(f) = O\big(\mathrm{fbs}(f)^3\big)\)
\(\mathrm{D}(f)\) \(\mathrm{cbs}(S)\) separations only → No bound exists
\(\mathrm{D}(f)\) \(\lambda(f)\) separations only → 4,6
\(\mathrm{D}(f)\) \(\mathrm{C}(f)\) Settled \(\mathrm{D}(f) \le \mathrm{C}^{(0)}(f)\cdot \mathrm{C}^{(1)}(f) \le \mathrm{C}(f)^2\) 2,2
\(\mathrm{D}(f)\) \(\mathrm{UC}_{\min}(f)\) Settled \(\mathrm{D}(f) \le \mathrm{UC}_{\min}(f)^2\)
\(\mathrm{D}(f)\) \(\mathrm{SP}(f)\) Settled \(\mathrm{D}(f) \le \mathrm{C}^{0}(f)\,\mathrm{C}^{1}(f) \le \mathrm{SP}(f)^2\)
\(\mathrm{D}(f)\) \(\mathrm{RC}(f)\) separations only → 2,3
\(\mathrm{D}(f)\) \(\mathrm{MaxInf}(f)\) Gap \(\mathrm{D}(f) \;\ge\; \frac{\mathrm{Var}(f)}{\mathrm{MaxInf}(f)}\)
\(\mathrm{D}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{D}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{D}(f)\) \(\mathrm{CG}(f)\) Gap \(\mathrm{D}(f) = O\big(\mathrm{CG}(f)^2\big)\)
\(\mathrm{D}^{\mathrm{na}}(f)\) \(\mathrm{D}(f)\) Settled \(\mathrm{D}^{\mathrm{na}}(f) \le 2^{\mathrm{D}(f)} - 1\) relation Settled
\(\mathrm{D}^{\mathrm{na}}(f)\) \(\mathrm{DTsize}(f)\) \(\mathrm{D}^{\mathrm{na}}(f) \le \mathrm{DTsize}(f) - 1\) relation Settled
\(\mathrm{D}^{\mathrm{na}}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{D}^{\mathrm{na}}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{DTsize}(f)\) \(\mathrm{D}(f)\) \(\mathrm{DTsize}(f) \le 2^{\mathrm{D}(f)}\) relation Settled
\(\mathrm{DTsize}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) \(\mathrm{Q}_{2/5}(S) = O\big(\sqrt{\mathrm{DTsize}(S)}\big)\) relation Settled
\(\mathrm{DTsize}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{DTsize}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{rank}(f)\) \(\mathrm{D}(f)\) Settled \(\mathrm{rank}(f) \le \mathrm{D}(f)\) relation Settled
\(\mathrm{rank}(f)\) \(\mathrm{DTsize}(f)\) Settled \(\mathrm{rank}(f) \le \log_2 \mathrm{DTsize}(f)\) relation Settled
\(\mathrm{rank}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{rank}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{D}^{\oplus}(f)\) \(\mathrm{D}(f)\) \(\mathrm{D}^{\oplus}(f) \le \mathrm{D}(f)\) relation Settled
\(\mathrm{D}^{\oplus}(f)\) \(\mathrm{psD}(S)\) separations only → Gap
\(\mathrm{D}^{\oplus}(f)\) \(\mathrm{cbs}(S)\) separations only → Gap
\(\mathrm{D}^{\oplus}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{D}^{\oplus}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{D}^{\oplus}(f)\) \(\mathrm{spar}(f)\) Gap \(\mathrm{D}^{\oplus}(f) = O\big(\sqrt{\mathrm{spar}(f)}\,\log \mathrm{spar}(f)\big)\)
\(\mathrm{D}^{\mathrm{prod}}(f)\) \(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{D}^{\mathrm{prod}}_{\varepsilon}(f) \le \mathrm{R}_{\varepsilon}(f)\) relation Settled
\(\mathrm{D}^{\mathrm{prod}}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{D}^{\mathrm{prod}}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{D}^{\mathrm{prod}}(f)\) \(\mathrm{RS}(f)\) Settled \(\mathrm{D}^{\mathrm{prod}}(g) = \tilde O\big(\mathrm{RS}(g)\big)\)
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) \(\mathrm{DTsize}(f)\) Gap separations only →
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) \(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{D}^{\mu}_{\varepsilon}(f) \le \mathrm{R}_{\varepsilon}(f) \quad\text{for every } \mu\) relation Settled
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{D}(f)\) Gap \(\mathrm{R}(f) \le \mathrm{R}_0(f) \le \mathrm{D}(f)\) relation Settled 1,1
\(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{D}^{\mathrm{prod}}(f)\) Wide open separations only →
\(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{R}_{\varepsilon}(f)\) Settled \(\text{Any } \gamma^3\mathrm{R}(f)k/11 \text{-query algorithm computes } f^{\otimes k} \text{ correctly with probability} < (1/2+\gamma)^k\) Settled Settled
\(\mathrm{R}_{\varepsilon}(f)\) \(\bar{\mathrm{R}}_{\varepsilon}(f)\) Settled \(\mathrm{R}(\mathrm{MAJ}_n\circ g^n) = O\big(n\cdot \bar{\mathrm{R}}_{1/n}(g)\big)\) Settled
\(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{R}^{\mathrm{na}}(f)\) Settled \(\mathrm{R}_\varepsilon(f) \le \mathrm{R}^{\mathrm{na}}_\varepsilon(f)\) relation Settled
\(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{R}_{0}(f)\) Settled \(\mathrm{R}_{1/3}(f) \le \tfrac32\,\mathrm{R}_0(f)\) relation Settled 1,1
\(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{R}^{1}(f)\) \(\mathrm{R}(f) \le \mathrm{R}^{1}(f)\) partial Settled
\(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{R}_{\mathrm{RP}}(f)\) \(\mathrm{R}(f)\le\mathrm{R}_{\mathrm{RP}}(f)\) partial Gap
\(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{N}_{p}(f)\) \(\mathrm{R}(f) = O\big(\mathrm{N}_p(f)\big)\) relation Settled
\(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) Settled \(\mathrm{R}(f) \le \mathrm{D}(f) = O(\mathrm{Q}(f)^4)\) No bound exists 4,4
\(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{Q}_{\mathrm{E}}(f)\) separations only → 1.5,3
\(\mathrm{R}_{\varepsilon}(f)\) \(\deg(f)\) separations only → 2,3
\(\mathrm{R}_{\varepsilon}(f)\) \(\widetilde{\deg}_{\varepsilon}(f)\) Settled \(\mathrm{R}(f) = O(\widetilde{\deg}(f)^4)\) 4,4
\(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{rdeg}(f)\) separations only → 2,4
\(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{s}(f)\) separations only → 3,6
\(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{bs}(f)\) separations only → 2,3
\(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{fbs}(f)\) Gap \(\mathrm{R}(f) \le \mathrm{R}_0(f) \le \mathrm{D}(f) = O\big(\mathrm{fbs}(f)^3\big)\)
\(\mathrm{R}_{\varepsilon}(f)\) \(\lambda(f)\) separations only → 4,6
\(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{C}(f)\) separations only → 2,2
\(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{SP}(f)\) Settled \(\mathrm{R}(f) \le \mathrm{D}(f) = O(\mathrm{SP}(f)^2)\)
\(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{RC}(f)\) separations only → 2,3
\(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{prt}_{\varepsilon}(f)\) Wide open separations only →
\(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{RS}(f)\) Gap \(\mathrm{R}_\varepsilon(f) \ge \bar{\mathrm{R}}_\varepsilon(f) \ge (1-2\varepsilon)\,\mathrm{RS}(f)\) No bound exists
\(\mathrm{R}_{\varepsilon}(f)\) \(\chi(f)\) Settled \(\mathrm{R}(g) = O\big(\chi(g)^2\big)\)
\(\mathrm{R}_{\varepsilon}(f)\) \(\bar{\chi}(f)\) \(\mathrm{R}(g) = O\big(\bar\chi(g)^2\big)\) partial Settled
\(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{LR}(f)\) Gap \(\mathrm{R}(f) = O\big(\mathrm{LR}(f)^2\big)\) partial Settled
\(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{noisyR}(f)\) Gap \(\mathrm{R}(f)\le C\log(n+1)\mathrm{noisyR}(f)\) partial Gap No bound exists
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) \(\mathrm{D}^{\mu}_{\varepsilon}(f)\) \(\bar{\mathrm{R}}_\varepsilon(f) = \Theta\big(\max_\mu \mathrm{D}^{\mu}_{\varepsilon}(f)\big)\ \text{ for constant } \varepsilon\) relation Gap Settled
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{R}^{\mathrm{na}}(f)\) \(\mathrm{D}^{\mathrm{na}}(f)\) Gap \(\mathrm{R}^{\mathrm{na}}(f) \le \mathrm{D}^{\mathrm{na}}(f)\) relation Settled
\(\mathrm{R}^{\mathrm{na}}(f)\) \(\mathrm{R}_{\varepsilon}(f)\) Settled \(\mathrm{R}^{\mathrm{na}}_\varepsilon(f) \le 2^{\mathrm{R}_\varepsilon(f)} - 1\) relation Settled
\(\mathrm{R}^{\mathrm{na}}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{R}^{\mathrm{na}}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{R}^{\mathrm{na}}(f)\) \(\mathrm{noisyR}^{\mathrm{na}}(f)\) separations only → No bound exists
\(\mathrm{R}_{0}(f)\) \(\mathrm{D}(f)\) Settled \(\mathrm{R}_0(f) \le \mathrm{D}(f)\) relation Settled 1,1
\(\mathrm{R}_{0}(f)\) \(\mathrm{R}_{\varepsilon}(f)\) Settled \(\mathrm{R}_0(f) = O\big(\mathrm{R}(f)^2\log \mathrm{R}(f)\big)\) Gap 2,2
\(\mathrm{R}_{0}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) Settled \(\mathrm{R}_0(f)\le\mathrm{D}(f)=O(\mathrm{Q}(f)^4)\) 4,4
\(\mathrm{R}_{0}(f)\) \(\mathrm{Q}_{\mathrm{E}}(f)\) separations only → 2,3
\(\mathrm{R}_{0}(f)\) \(\mathrm{Q}_{0}(f)\) Gap \(\mathrm{R}_0(f) = O\big(\mathrm{Q}(f)^2\,\mathrm{Q}_0(f)\log n\big)\)
\(\mathrm{R}_{0}(f)\) \(\deg(f)\) separations only → 2,3
\(\mathrm{R}_{0}(f)\) \(\widetilde{\deg}_{\varepsilon}(f)\) separations only → 4,4
\(\mathrm{R}_{0}(f)\) \(\mathrm{rdeg}(f)\) separations only → 2,4
\(\mathrm{R}_{0}(f)\) \(\mathrm{s}(f)\) separations only → 3,6
\(\mathrm{R}_{0}(f)\) \(\mathrm{bs}(f)\) separations only → 2,3
\(\mathrm{R}_{0}(f)\) \(\lambda(f)\) separations only → 4,6
\(\mathrm{R}_{0}(f)\) \(\mathrm{C}(f)\) Gap \(\mathrm{R}_0(f) \le \mathrm{C}(f)^2\) 2,2
\(\mathrm{R}_{0}(f)\) \(\mathrm{RC}(f)\) separations only → 2,3
\(\mathrm{R}_{0}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{R}_{0}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{R}_{0}(f)\) \(\mathrm{CG}(f)\) Settled \(\mathrm{R}_0(f) = O\big(\mathrm{CG}(f)\big)\)
\(\mathrm{R}^{1}(f)\) \(\mathrm{R}_{0}(f)\) \(\mathrm{R}^{1}(f) \le \mathrm{R}_{0}(f)\) partial Settled
\(\mathrm{R}^{1}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{R}^{1}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{R}_{\mathrm{RP}}(f)\) \(\mathrm{R}_{0}(f)\) \(\mathrm{R}_{\mathrm{RP}}(f)=O(\mathrm{R}_0(f))\) partial Gap
\(\mathrm{psD}(S)\) \(\mathrm{D}(f)\) \(\mathrm{psD}(S) \le \mathrm{D}(S)\) relation Settled
\(\mathrm{psD}(S)\) \(\mathrm{D}^{\oplus}(f)\) separations only → No bound exists
\(\mathrm{psD}(S)\) \(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{R}(S) \le \mathrm{psD}(S) \le \mathrm{D}(S)\) relation Settled
\(\mathrm{N}_{p}(f)\) \(\mathrm{R}_{\varepsilon}(f)\) Settled \(\mathrm{N}_p(f) = O\big(\mathrm{R}(f)\log \mathrm{R}(f)\big)\) relation Settled
\(\mathrm{N}_{p}(f)\) \(\mathrm{psD}(S)\) separations only → Gap
\(\mathrm{N}_{p}(f)\) \(\mathrm{N}_{p}(f)\) \(\mathrm{N}_p(f) = O\!\left(\frac{\mathrm{R}(f)\log \mathrm{R}(f)}{(1-2p)^2}\right)\) relation Settled
\(\mathrm{N}_{p}(f)\) \(\mathrm{cbs}(S)\) separations only → Gap
\(\mathrm{N}_{p}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{N}_{p}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{Q}_{\varepsilon}(f)\) \(\mathrm{D}(f)\) Settled \(\mathrm{Q}(f) \le \mathrm{R}(f) \le \mathrm{R}_0(f) \le \mathrm{D}(f) \le n\) relation Settled 1,1
\(\mathrm{Q}_{\varepsilon}(f)\) \(\mathrm{R}_{\varepsilon}(f)\) Settled \(\mathrm{Q}(f) \le \mathrm{R}(f)\) relation Settled 1,1
\(\mathrm{Q}_{\varepsilon}(f)\) \(\mathrm{R}_{0}(f)\) separations only → 1,1
\(\mathrm{Q}_{\varepsilon}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) Gap \(\mathrm{Q}(f^{\otimes k}) = O\big(k\,\mathrm{Q}(f)\log k\big)\) Settled
\(\mathrm{Q}_{\varepsilon}(f)\) \(\mathrm{Q}_{\mathrm{E}}(f)\) separations only → 1,1
\(\mathrm{Q}_{\varepsilon}(f)\) \(\mathrm{Q}_{0}(f)\) Settled \(\mathrm{Q}(f) \le \mathrm{Q}_0(f)\) relation Settled
\(\mathrm{Q}_{\varepsilon}(f)\) \(\mathrm{QS}_{\mathrm{weak}}(f)\) Gap \(\mathrm{Q}(f)=\widetilde O(\mathrm{QS}_{\mathrm{weak}}(f)^6)\)
\(\mathrm{Q}_{\varepsilon}(f)\) \(\mathrm{Q}^{\mathrm{rob}}(f)\) \(\mathrm{Q}(f) \le \mathrm{Q}^{\mathrm{rob}}(f)\) relation Settled
\(\mathrm{Q}_{\varepsilon}(f)\) \(\mathrm{QS}_{\mathrm{str}}(f)\) Gap \(\mathrm{Q}(f)=\widetilde O(\mathrm{QS}_{\mathrm{str}}(f)^6)\)
\(\mathrm{Q}_{\varepsilon}(f)\) \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f)\) Gap \(\mathrm{Q}(f)=\widetilde O(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f)^6)\)
\(\mathrm{Q}_{\varepsilon}(f)\) \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f)\) Gap \(\mathrm{Q}(f)=\widetilde O(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f)^6)\)
\(\mathrm{Q}_{\varepsilon}(f)\) \(\deg(f)\) Gap \(\mathrm{Q}(f) \le \mathrm{D}(f) \le 2\deg(f)^3\) 2,3
\(\mathrm{Q}_{\varepsilon}(f)\) \(\widetilde{\deg}_{\varepsilon}(f)\) Settled \(\mathrm{Q}(f) = O(\widetilde{\deg}(f)^4)\) 4,4
\(\mathrm{Q}_{\varepsilon}(f)\) \(\mathrm{rdeg}(f)\) separations only → 2,4
\(\mathrm{Q}_{\varepsilon}(f)\) \(\mathrm{s}(f)\) separations only → 3,6
\(\mathrm{Q}_{\varepsilon}(f)\) \(\mathrm{bs}(f)\) separations only → 2,3
\(\mathrm{Q}_{\varepsilon}(f)\) \(\lambda(f)\) Settled \(\lambda(f) \le \mathrm{Q}(f)\cdot O(1) \quad\text{i.e.}\quad \mathrm{Q}(f) = \Omega(\lambda(f))\) partial Settled 4,6
\(\mathrm{Q}_{\varepsilon}(f)\) \(\mathrm{C}(f)\) separations only → 2,2
\(\mathrm{Q}_{\varepsilon}(f)\) \(\mathrm{SP}(f)\) Gap \(\mathrm{Q}(f) \le \mathrm{D}(f) = O(\mathrm{SP}(f)^2)\)
\(\mathrm{Q}_{\varepsilon}(f)\) \(\mathrm{RC}(f)\) separations only → 2,3
\(\mathrm{Q}_{\varepsilon}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{Q}_{\varepsilon}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{Q}_{\varepsilon}(f)\) \(\mathrm{Adv}^{\pm}(f)\) Settled \(\mathrm{Q}(f\circ g) = O(\mathrm{Q}(f)\,\mathrm{Q}(g))\) partial Settled Settled
\(\mathrm{Q}_{\mathrm{E}}(f)\) \(\mathrm{D}(f)\) Settled \(\mathrm{Q}_E(f) \le \mathrm{D}(f)\) relation Settled 1,1
\(\mathrm{Q}_{\mathrm{E}}(f)\) \(\mathrm{R}_{\varepsilon}(f)\) separations only → 1.33,3
\(\mathrm{Q}_{\mathrm{E}}(f)\) \(\mathrm{R}_{0}(f)\) separations only → 1.33,2
\(\mathrm{Q}_{\mathrm{E}}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) separations only → 2,4
\(\mathrm{Q}_{\mathrm{E}}(f)\) \(\mathrm{Q}_{\mathrm{E}}(f)\) No bound exists \(\mathrm{Q}_{\mathrm{E}}(f\circ g)=O(\mathrm{Q}_{\mathrm{E}}(f)\mathrm{Q}_{\mathrm{E}}(g))\)
\(\mathrm{Q}_{\mathrm{E}}(f)\) \(\deg(f)\) separations only → 2,3
\(\mathrm{Q}_{\mathrm{E}}(f)\) \(\widetilde{\deg}_{\varepsilon}(f)\) separations only → 4,4
\(\mathrm{Q}_{\mathrm{E}}(f)\) \(\mathrm{rdeg}(f)\) separations only → 2,4
\(\mathrm{Q}_{\mathrm{E}}(f)\) \(\mathrm{s}(f)\) separations only → 3,6
\(\mathrm{Q}_{\mathrm{E}}(f)\) \(\mathrm{bs}(f)\) separations only → 2,3
\(\mathrm{Q}_{\mathrm{E}}(f)\) \(\lambda(f)\) separations only → 4,6
\(\mathrm{Q}_{\mathrm{E}}(f)\) \(\mathrm{C}(f)\) separations only → 2,2
\(\mathrm{Q}_{\mathrm{E}}(f)\) \(\mathrm{RC}(f)\) separations only → 2,3
\(\mathrm{Q}_{\mathrm{E}}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{Q}_{\mathrm{E}}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{Q}_{0}(f)\) \(\mathrm{R}_{0}(f)\) \(\mathrm{Q}_0(f) \le 2\,\mathrm{R}_0(f)\) relation Settled
\(\mathrm{Q}_{0}(f)\) \(\mathrm{Q}_{\mathrm{E}}(f)\) Gap \(\mathrm{Q}(f) \le \mathrm{Q}_0(f) \le \mathrm{Q}_E(f) \le \mathrm{D}(f)\) relation Settled
\(\mathrm{Q}_{0}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{Q}_{0}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{PostQ}_{\varepsilon}(f)\) \(\mathrm{DTsize}(f)\) Gap separations only →
\(\mathrm{PostQ}_{\varepsilon}(f)\) \(\mathrm{rdeg}_{\varepsilon}(f)\) \(\mathrm{PostQ}_\varepsilon(f) = \Theta(\mathrm{rdeg}_\varepsilon(f))\) partial Settled
\(\mathrm{PostQ}_{\varepsilon}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{PostQ}_{\varepsilon}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{QC}(f)\) \(\mathrm{QS}_{\mathrm{weak}}(f)\) \(\mathrm{QC}(f)=O(\mathrm{QS}_{\mathrm{weak}}(f))\) partial Gap
\(\mathrm{QC}(f)\) \(\mathrm{QS}_{\mathrm{str}}(f)\) \(\mathrm{QC}(f)=O(\mathrm{QS}_{\mathrm{str}}(f))\) partial Gap
\(\mathrm{QC}(f)\) \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f)\) \(\mathrm{QC}(f)=O(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f))\) partial Gap
\(\mathrm{QC}(f)\) \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f)\) \(\mathrm{QC}(f)=O(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f))\) partial Gap
\(\mathrm{QC}(f)\) \(\mathrm{Q}_{0}^{\mathrm{cert}}(f)\) \(\mathrm{QC}(f)=O(\mathrm{Q}_0^{\mathrm{cert}}(f)^{1})\) partial Gap
\(\mathrm{QC}(f)\) \(\mathrm{fbs}(f)\) \(\mathrm{QC}(f) = \Theta\big(\sqrt{\mathrm{fbs}(f)}\big)\) partial Settled
\(\mathrm{QC}(f)\) \(\mathrm{RC}(f)\) \(\mathrm{QC}(f) = \Theta\big(\sqrt{\mathrm{RC}(f)}\big) = \Theta\big(\sqrt{\mathrm{fbs}(f)}\big)\) partial Settled
\(\mathrm{QC}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{QC}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{NQ}(f)\) \(\mathrm{ndeg}(f)\) \(\mathrm{NQ}(f) = \lceil \mathrm{ndeg}(f)/2\rceil\) partial Settled
\(\mathrm{NQ}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{NQ}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{QS}_{\mathrm{weak}}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) Gap \(\mathrm{QS}_{\mathrm{weak}}(f)=O(\mathrm{Q}(f)^4)\)
\(\mathrm{QS}_{\mathrm{weak}}(f)\) \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f)\) \(\mathrm{QS}_{\mathrm{weak}}(f)=O(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f))\) partial Gap
\(\mathrm{QS}_{\mathrm{weak}}(f)\) \(\mathrm{fbs}(f)\) Gap separations only →
\(\mathrm{QS}_{\mathrm{weak}}(f)\) \(\mathrm{RS}(f)\) \(\mathrm{QS}_{\mathrm{weak}}(f)=O(\mathrm{RS}(f))\) partial Gap
\(\mathrm{Q}^{\mathrm{rob}}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) Gap \(\mathrm{Q}^{\mathrm{rob}}(\mathrm{PARITY}_n) = \Theta(n)\) Gap
\(\mathrm{Q}^{\mathrm{rob}}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{Q}^{\mathrm{rob}}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{QS}_{\mathrm{str}}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) \(\mathrm{QS}_{\mathrm{str}}(f)=O(\mathrm{Q}(f))\) partial Gap
\(\mathrm{QS}_{\mathrm{str}}(f)\) \(\mathrm{QS}_{\mathrm{weak}}(f)\) \(\mathrm{QS}_{\mathrm{str}}(f)=O(\mathrm{QS}_{\mathrm{weak}}(f))\) partial Gap
\(\mathrm{QS}_{\mathrm{str}}(f)\) \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f)\) \(\mathrm{QS}_{\mathrm{str}}(f)=O(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f))\) partial Gap
\(\mathrm{QS}_{\mathrm{str}}(f)\) \(\mathrm{fbs}(f)\) Gap separations only →
\(\mathrm{QS}_{\mathrm{str}}(f)\) \(\mathrm{RS}(f)\) \(\mathrm{QS}_{\mathrm{str}}(f)=O(\mathrm{RS}(f))\) partial Gap
\(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) Gap \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f)=O(\mathrm{Q}(f)^4)\)
\(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f)\) \(\mathrm{fbs}(f)\) Gap separations only →
\(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f)\) \(\mathrm{RS}(f)\) \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f)=O(\mathrm{RS}(f))\) partial Gap
\(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f)=O(\mathrm{Q}(f)^{3/2})\) partial Gap
\(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f)\) \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f)\) \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f)=O(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f))\) partial Gap
\(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f)\) \(\mathrm{fbs}(f)\) Gap separations only →
\(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f)\) \(\mathrm{RS}(f)\) \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f)=O(\mathrm{RS}(f))\) partial Gap
\(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) Gap separations only →
\(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f)\) \(\mathrm{Q}_{\mathrm{E}}(f)\) \(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f)=O(\mathrm{Q}_{\mathrm{E}}(f)^{1})\) partial Gap
\(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f)\) \(\mathrm{QC}(f)\) Gap separations only →
\(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f)\) \(\mathrm{C}(f)\) \(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f)=O(\mathrm{C}(f)^{1})\) partial Gap
\(\mathrm{Q}_{0}^{\mathrm{cert}}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) Gap separations only →
\(\mathrm{Q}_{0}^{\mathrm{cert}}(f)\) \(\mathrm{Q}_{0}(f)\) \(\mathrm{Q}_0^{\mathrm{cert}}(f)=O(\mathrm{Q}_0(f)^{1})\) partial Gap
\(\mathrm{Q}_{0}^{\mathrm{cert}}(f)\) \(\mathrm{QC}(f)\) Gap separations only →
\(\deg(f)\) \(\mathrm{D}(f)\) Settled \(\deg(f) \le \mathrm{D}(f)\) partial Settled 1,1
\(\deg(f)\) \(\mathrm{R}_{\varepsilon}(f)\) separations only → 1.33,2
\(\deg(f)\) \(\mathrm{R}_{0}(f)\) separations only → 1.33,2
\(\deg(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) Settled \(\deg(f) = O(\mathrm{Q}(f)^2)\) 2,2
\(\deg(f)\) \(\mathrm{Q}_{\mathrm{E}}(f)\) Settled \(\deg(f) \le 2\,\mathrm{Q}_E(f)\) partial Settled 1,1
\(\deg(f)\) \(\deg(f)\) Settled \(\deg(f\circ g) \le \deg(f)\,\deg(g)\)
\(\deg(f)\) \(\widetilde{\deg}_{\varepsilon}(f)\) Settled \(\deg(f) = O(\widetilde{\deg}(f)^2)\) 2,2
\(\deg(f)\) \(\mathrm{rdeg}(f)\) Gap \(\deg(f) = O\big(\mathrm{rdeg}(f)\deg_{\pm}(f)^2\log \mathrm{rdeg}(f)\big) = \widetilde O(\mathrm{rdeg}(f)^3)\) 2,3
\(\deg(f)\) \(\overline{\deg}(f)\) \(\deg(f)=O(\overline{\deg}(f)^{1})\) partial Gap
\(\deg(f)\) \(\overline{\deg}^{\mathrm{cert}}(f)\) Gap separations only →
\(\deg(f)\) \(\mathrm{s}(f)\) Settled \(\deg(f) \le \mathrm{s}(f)^2\) 2,2
\(\deg(f)\) \(\mathrm{bs}(f)\) separations only → 2,2
\(\deg(f)\) \(\lambda(f)\) Settled \(\deg(f) \le \lambda(f)^2\) 2,2
\(\deg(f)\) \(\mathrm{C}(f)\) separations only → 2,2
\(\deg(f)\) \(\mathrm{RC}(f)\) separations only → 2,2
\(\deg(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\deg(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\deg(f)\) \(\mathrm{spar}(f)\) No bound exists separations only →
\(\widetilde{\deg}_{\varepsilon}(f)\) \(\mathrm{D}(f)\) separations only → 1,1
\(\widetilde{\deg}_{\varepsilon}(f)\) \(\mathrm{R}_{\varepsilon}(f)\) Settled \(\widetilde{\deg}(f) \le \mathrm{R}(f) \text{ and } \widetilde{\deg}(f)\le 2\mathrm{Q}(f),\ \text{ for total AND partial } f\) partial Settled 1,1
\(\widetilde{\deg}_{\varepsilon}(f)\) \(\mathrm{R}_{0}(f)\) separations only → 1,1
\(\widetilde{\deg}_{\varepsilon}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) Settled \(\widetilde{\deg}_\varepsilon(f) \le 2\,\mathrm{Q}_\varepsilon(f) \text{ still holds}\) partial No bound exists 1,1
\(\widetilde{\deg}_{\varepsilon}(f)\) \(\mathrm{Q}_{\mathrm{E}}(f)\) separations only → 1,1
\(\widetilde{\deg}_{\varepsilon}(f)\) \(\deg(f)\) Settled \(\widetilde{\deg}(f) \le \deg(f)\) No bound exists 1,1
\(\widetilde{\deg}_{\varepsilon}(f)\) \(\widetilde{\deg}_{\varepsilon}(f)\) Settled \(\widetilde{\deg}(f\circ g) = O\big(\widetilde{\deg}(f)\,\widetilde{\deg}(g)\big)\) Settled
\(\widetilde{\deg}_{\varepsilon}(f)\) \(\widetilde{\deg}_{+}(f)\) No bound exists separations only →
\(\widetilde{\deg}_{\varepsilon}(f)\) \(\mathrm{rdeg}(f)\) Gap separations only → 2,3
\(\widetilde{\deg}_{\varepsilon}(f)\) \(\mathrm{cjdeg}_{\varepsilon}(f)\) \(\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{cjdeg}_{\varepsilon}(f)\) partial Settled
\(\widetilde{\deg}_{\varepsilon}(f)\) \(\overline{\mathrm{osdeg}}^{\,0}_{\varepsilon}(f)\) \(\widetilde{\deg}(f)=O(\overline{\mathrm{osdeg}}^{\,0}(f)^{1})\) partial Gap
\(\widetilde{\deg}_{\varepsilon}(f)\) \(\overline{\mathrm{osdeg}}^{\,1}_{\varepsilon}(f)\) \(\widetilde{\deg}(f)=O(\overline{\mathrm{osdeg}}^{\,1}(f)^{1})\) partial Gap
\(\widetilde{\deg}_{\varepsilon}(f)\) \(\overline{\mathrm{osdeg}}_{\varepsilon}(f)\) \(\widetilde{\deg}(f)=O(\overline{\mathrm{osdeg}}(f)^{1})\) partial Gap
\(\widetilde{\deg}_{\varepsilon}(f)\) \(\mathrm{s}(f)\) separations only → 2,2
\(\widetilde{\deg}_{\varepsilon}(f)\) \(\mathrm{bs}(f)\) separations only → 2,2
\(\widetilde{\deg}_{\varepsilon}(f)\) \(\lambda(f)\) separations only → 2,2
\(\widetilde{\deg}_{\varepsilon}(f)\) \(\mathrm{C}(f)\) separations only → 2,2
\(\widetilde{\deg}_{\varepsilon}(f)\) \(\mathrm{RC}(f)\) Gap \(\widetilde{\deg}(f) = \Omega\big(\sqrt{\mathrm{RC}(f)}\big),\ \text{ i.e. } \mathrm{RC}(f) = O\big(\widetilde{\deg}(f)^2\big)\) 2,2
\(\widetilde{\deg}_{\varepsilon}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\widetilde{\deg}_{\varepsilon}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\widetilde{\deg}_{\varepsilon}(f)\) \(\mathrm{Adv}(f)\) separations only → No bound exists
\(\widetilde{\deg}_{\varepsilon}(f)\) \(\mathrm{prt}_{\varepsilon}(f)\) \(\widetilde{\deg}_{2\varepsilon}(f) \le \mathrm{prt}_{\varepsilon}(f) + \log(1/\varepsilon)\) partial Settled
\(\widetilde{\deg}_{\varepsilon}(f)\) \(\overline{\mathrm{prt}}_{\varepsilon}(f)\) \(\widetilde{\deg}_{2\varepsilon}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) + \log(1/\varepsilon)\) partial Settled
\(\widetilde{\deg}_{+}(f)\) \(\deg(f)\) \(\widetilde{\deg}_+(f) \le \deg(f)\) partial Settled
\(\widetilde{\deg}_{+}(f)\) \(\widetilde{\deg}_{\varepsilon}(f)\) Settled \(\widetilde{\deg}_+(f) \le \widetilde{\deg}(f)\) partial Settled
\(\widetilde{\deg}_{+}(f)\) \(\mathrm{sdeg}(f)\) No bound exists separations only →
\(\widetilde{\deg}_{+}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\widetilde{\deg}_{+}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{sdeg}(f)\) \(\mathrm{DTsize}(f)\) Gap separations only →
\(\mathrm{sdeg}(f)\) \(\deg(f)\) \(\mathrm{sdeg}(f) \le \deg(f)\) partial Settled
\(\mathrm{sdeg}(f)\) \(\widetilde{\deg}_{+}(f)\) Settled \(\mathrm{sdeg}(f) \le \widetilde{\deg}_+(f)\) partial Settled
\(\mathrm{sdeg}(f)\) \(\mathrm{rdeg}(f)\) \(\deg_{\pm}(f) \le 2\,\mathrm{rdeg}(f)\) partial Settled
\(\mathrm{sdeg}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{sdeg}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{rdeg}(f)\) \(\overline{\deg}^{\mathrm{cert}}(f)\) \(\mathrm{rdeg}(f)=O(\overline{\deg}^{\mathrm{cert}}(f)^{1})\) partial Gap
\(\mathrm{rdeg}(f)\) \(\overline{\mathrm{osdeg}}_{\varepsilon}(f)\) \(\mathrm{rdeg}(f)=O(\overline{\mathrm{osdeg}}(f)^{1})\) partial Gap
\(\mathrm{rdeg}(f)\) \(\mathrm{C}(f)\) Settled \(\mathrm{rdeg}(f) \le \mathrm{C}(f)\) partial Settled
\(\mathrm{rdeg}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{rdeg}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{rdeg}_{\varepsilon}(f)\) \(\mathrm{DTsize}(f)\) Gap separations only →
\(\mathrm{rdeg}_{\varepsilon}(f)\) \(\widetilde{\deg}_{\varepsilon}(f)\) Gap \(\mathrm{rdeg}_\varepsilon(f) \le \widetilde{\deg}_\varepsilon(f)\) partial Gap
\(\mathrm{rdeg}_{\varepsilon}(f)\) \(\mathrm{rdeg}(f)\) \(\mathrm{rdeg}_\varepsilon(f) \le \mathrm{rdeg}(f)\) partial Gap
\(\mathrm{rdeg}_{\varepsilon}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{rdeg}_{\varepsilon}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{ndeg}(f)\) \(\deg(f)\) \(\mathrm{ndeg}(f) \le \deg(f)\) partial Settled
\(\mathrm{ndeg}(f)\) \(\mathrm{rdeg}(f)\) \(\mathrm{ndeg}(f) \le \mathrm{rdeg}(f)\) partial Settled
\(\mathrm{ndeg}(f)\) \(\mathrm{C}^1(f)\) \(\mathrm{ndeg}(f) \le \mathrm{C}^1(f)\) partial Settled
\(\mathrm{ndeg}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{ndeg}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\deg_2(f)\) \(\mathrm{D}^{\oplus}(f)\) Gap \(\deg_2(f) \le \mathrm{D}^{\oplus}(f) \le \mathrm{D}(f)\)
\(\deg_2(f)\) \(\deg(f)\) Settled \(\deg_2(f) \le \deg(f)\)
\(\deg_2(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\deg_2(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\deg_2(f)\) \(\mathrm{spar}(f)\) Settled \(\deg_2(f) \le \log_2\big(\mathrm{spar}(f)+1\big)\)
\(\deg_p(f)\) \(\deg(f)\) \(\deg_p(f) \le \deg(f)\) partial Gap
\(\deg_p(f)\) \(\mathrm{MaxInf}(f)\) No bound exists separations only →
\(\deg_p(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\deg_p(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\deg_p(f)\) \(\mathrm{spar}(f)\) No bound exists separations only →
\(\mathrm{cjdeg}_{\varepsilon}(f)\) \(\mathrm{DTsize}(f)\) Gap separations only →
\(\mathrm{cjdeg}_{\varepsilon}(f)\) \(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{cjdeg}_{\varepsilon}(f) \le \mathrm{R}_{\varepsilon}(f)\) relation Gap
\(\mathrm{cjdeg}_{\varepsilon}(f)\) \(\mathrm{psD}(S)\) separations only → Gap
\(\mathrm{cjdeg}_{\varepsilon}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) separations only → No bound exists
\(\mathrm{cjdeg}_{\varepsilon}(f)\) \(\mathrm{cbs}(S)\) separations only → Gap
\(\mathrm{cjdeg}_{\varepsilon}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{cjdeg}_{\varepsilon}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\overline{\deg}(f)\) \(\mathrm{Q}_{\mathrm{E}}(f)\) \(\overline{\deg}(f)=O(\mathrm{Q}_{\mathrm{E}}(f)^{1})\) partial Gap
\(\overline{\deg}^{\mathrm{cert}}(f)\) \(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f)\) \(\overline{\deg}^{\mathrm{cert}}(f)=O(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f)^{1})\) partial Gap
\(\overline{\deg}^{\mathrm{cert}}(f)\) \(\mathrm{Q}_{0}^{\mathrm{cert}}(f)\) \(\overline{\deg}^{\mathrm{cert}}(f)=O(\mathrm{Q}_0^{\mathrm{cert}}(f)^{1})\) partial Gap
\(\overline{\deg}^{\mathrm{cert}}(f)\) \(\mathrm{rdeg}(f)\) Gap separations only →
\(\overline{\deg}^{\mathrm{cert}}(f)\) \(\overline{\deg}(f)\) \(\overline{\deg}^{\mathrm{cert}}(f)=O(\overline{\deg}(f)^{1})\) partial Gap
\(\overline{\deg}^{\mathrm{cert}}(f)\) \(\overline{\mathrm{osdeg}}_{\varepsilon}(f)\) \(\overline{\deg}^{\mathrm{cert}}(f)=O(\overline{\mathrm{osdeg}}(f)^{1})\) partial Gap
\(\overline{\deg}^{\mathrm{cert}}(f)\) \(\mathrm{C}(f)\) \(\overline{\deg}^{\mathrm{cert}}(f)=O(\mathrm{C}(f)^{1})\) partial Gap
\(\overline{\mathrm{osdeg}}^{\,0}_{\varepsilon}(f)\) \(\overline{\mathrm{osdeg}}_{\varepsilon}(f)\) \(\overline{\mathrm{osdeg}}^{\,0}(f)=O(\overline{\mathrm{osdeg}}(f)^{1})\) partial Gap
\(\overline{\mathrm{osdeg}}^{\,1}_{\varepsilon}(f)\) \(\overline{\mathrm{osdeg}}_{\varepsilon}(f)\) \(\overline{\mathrm{osdeg}}^{\,1}(f)=O(\overline{\mathrm{osdeg}}(f)^{1})\) partial Gap
\(\overline{\mathrm{osdeg}}_{\varepsilon}(f)\) \(\mathrm{Q}_{0}(f)\) \(\overline{\mathrm{osdeg}}(f)=O(\mathrm{Q}_0(f)^{1})\) partial Gap
\(\overline{\mathrm{osdeg}}_{\varepsilon}(f)\) \(\widetilde{\deg}_{\varepsilon}(f)\) Gap separations only →
\(\overline{\mathrm{osdeg}}_{\varepsilon}(f)\) \(\overline{\deg}(f)\) \(\overline{\mathrm{osdeg}}(f)=O(\overline{\deg}(f)^{1})\) partial Gap
\(\mathrm{s}(f)\) \(\mathrm{D}(f)\) Settled \(\mathrm{s}(f) \le \mathrm{bs}(f) \le \mathrm{C}(f) \le \mathrm{D}(f)\) partial Settled 1,1
\(\mathrm{s}(f)\) \(\mathrm{R}_{\varepsilon}(f)\) separations only → 1,1
\(\mathrm{s}(f)\) \(\mathrm{R}_{0}(f)\) separations only → 1,1
\(\mathrm{s}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) separations only → 2,2
\(\mathrm{s}(f)\) \(\mathrm{Q}_{\mathrm{E}}(f)\) separations only → 1.15,2
\(\mathrm{s}(f)\) \(\deg(f)\) separations only → 1.63,2
\(\mathrm{s}(f)\) \(\widetilde{\deg}_{\varepsilon}(f)\) separations only → 2,2
\(\mathrm{s}(f)\) \(\mathrm{rdeg}(f)\) Gap \(\mathrm{s}(f) = O\big(\mathrm{rdeg}(f)\deg_{\pm}(f)^2\log \mathrm{rdeg}(f)\big) = \widetilde O(\mathrm{rdeg}(f)^3)\) 2,3
\(\mathrm{s}(f)\) \(\mathrm{bs}(f)\) Settled \(\mathrm{s}(f) \le \mathrm{bs}(f)\) partial Settled 1,1
\(\mathrm{s}(f)\) \(\lambda(f)\) separations only → 2,2
\(\mathrm{s}(f)\) \(\mathrm{C}(f)\) separations only → 1,1
\(\mathrm{s}(f)\) \(\mathrm{RC}(f)\) separations only → 1,1
\(\mathrm{s}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{s}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{s}^0(f)\) \(\mathrm{bs}^0(f)\) Settled \(\mathrm{s}^0(f) \le \mathrm{bs}^0(f)\) partial Settled
\(\mathrm{s}^0(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{s}^0(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{s}^1(f)\) \(\mathrm{bs}^1(f)\) Settled \(\mathrm{s}^1(f) \le \mathrm{bs}^1(f)\) partial Settled
\(\mathrm{s}^1(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{s}^1(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{bs}(f)\) \(\mathrm{D}(f)\) separations only → 1,1
\(\mathrm{bs}(f)\) \(\mathrm{R}_{\varepsilon}(f)\) Settled \(\mathrm{bs}(f) \le 3\,\mathrm{R}(f)\) partial Settled 1,1
\(\mathrm{bs}(f)\) \(\mathrm{R}_{0}(f)\) separations only → 1,1
\(\mathrm{bs}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) separations only → 2,2
\(\mathrm{bs}(f)\) \(\mathrm{Q}_{\mathrm{E}}(f)\) separations only → 1.15,2
\(\mathrm{bs}(f)\) \(\deg(f)\) Settled \(\mathrm{bs}(f) \le 2\deg(f)^2\) 1.63,2
\(\mathrm{bs}(f)\) \(\widetilde{\deg}_{\varepsilon}(f)\) Settled \(\mathrm{bs}(f) \le 6\,\widetilde{\deg}(f)^2\) 2,2
\(\mathrm{bs}(f)\) \(\mathrm{rdeg}(f)\) separations only → 2,4
\(\mathrm{bs}(f)\) \(\overline{\deg}^{\mathrm{cert}}(f)\) \(\mathrm{bs}(f)=O(\overline{\deg}^{\mathrm{cert}}(f)^{2})\) partial Gap
\(\mathrm{bs}(f)\) \(\mathrm{s}(f)\) Gap \(\mathrm{bs}(f) \le 2\deg(f)^2 \le 2\,\mathrm{s}(f)^4\) 2.130825579397823,4
\(\mathrm{bs}(f)\) \(\mathrm{bs}^0(f)\) No bound exists separations only →
\(\mathrm{bs}(f)\) \(\mathrm{bs}^1(f)\) No bound exists separations only →
\(\mathrm{bs}(f)\) \(\mathrm{fbs}(f)\) Settled \(\mathrm{bs}(f) \le \mathrm{fbs}(f)\) partial Settled
\(\mathrm{bs}(f)\) \(\lambda(f)\) Gap separations only → 2.130825579397823,4
\(\mathrm{bs}(f)\) \(\mathrm{C}(f)\) Settled \(\mathrm{bs}(f) \le \mathrm{C}(f)\) partial Settled 1,1
\(\mathrm{bs}(f)\) \(\mathrm{RC}(f)\) separations only → 1,1
\(\mathrm{bs}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{bs}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{bs}(f)\) \(\mathrm{Adv}(f)\) \(\mathrm{bs}(f) \le \mathrm{Adv}(f)^2\) partial Settled
\(\mathrm{bs}^0(f)\) \(\mathrm{bs}(f)\) Settled \(\mathrm{bs}^0(f) \le \mathrm{bs}(f)\) partial Settled
\(\mathrm{bs}^0(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{bs}^0(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{bs}^1(f)\) \(\mathrm{bs}(f)\) Settled \(\mathrm{bs}^1(f) \le \mathrm{bs}(f)\) partial Settled
\(\mathrm{bs}^1(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{bs}^1(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{fbs}(f)\) \(\mathrm{R}_{\varepsilon}(f)\) Settled \(\mathrm{fbs}(f) = O(\mathrm{R}(f))\) partial Settled
\(\mathrm{fbs}(f)\) \(\mathrm{s}(f)\) Gap \(\mathrm{fbs}(f) \le \mathrm{C}(f) \le 2\,\mathrm{s}(f)^5\)
\(\mathrm{fbs}(f)\) \(\mathrm{bs}(f)\) Gap \(\mathrm{fbs}(f) \le \mathrm{C}(f) \le \mathrm{s}(f)\,\mathrm{bs}(f) \le \mathrm{bs}(f)^2\)
\(\mathrm{fbs}(f)\) \(\mathrm{FC}(f)\) Settled \(\mathrm{fbs}(f) = \mathrm{FC}(f)\) partial Settled
\(\mathrm{fbs}(f)\) \(\lambda(f)\) Gap separations only →
\(\mathrm{fbs}(f)\) \(\mathrm{C}(f)\) Settled \(\mathrm{fbs}(f) \le \mathrm{C}(f)\) partial Settled
\(\mathrm{fbs}(f)\) \(\mathrm{RC}(f)\) Settled \(\mathrm{fbs}(f) = \Theta(\mathrm{RC}(f))\) partial Settled
\(\mathrm{fbs}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{fbs}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{fbs}(f)\) \(\mathrm{CA}(f)\) Settled \(\mathrm{fbs}(f) = \Theta\big(\mathrm{CA}(f)\big)\)
\(\mathrm{fbs}(f)\) \(\mathrm{Adv}(f)\) \(\mathrm{fbs}(f) \le \mathrm{Adv}(f)^2\) partial Settled
\(\mathrm{fbs}(f)\) \(\mathrm{noisyR}(f)\) \(\mathrm{fbs}(f) = O\big(\mathrm{noisyR}(f)\big)\) partial Settled
\(\mathrm{FC}(f)\) \(\mathrm{fbs}(f)\) Settled \(\mathrm{FC}(f) = \mathrm{fbs}(f)\) partial Settled
\(\mathrm{FC}(f)\) \(\mathrm{EC}(f)\) Gap \(\mathrm{FC}(f) \le \mathrm{EC}(f)\) partial Settled
\(\mathrm{FC}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{FC}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{cbs}(S)\) \(\mathrm{D}^{\oplus}(f)\) separations only → No bound exists
\(\mathrm{cbs}(S)\) \(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{cbs}(S) = O(\mathrm{R}(S))\) relation Settled
\(\mathrm{cbs}(S)\) \(\mathrm{bs}(f)\) Settled \(\mathrm{cbs}(f) = \mathrm{bs}(f) \text{ for Boolean } f\)
\(\mathrm{cbs}(S)\) \(\mathrm{CA}(f)\) \(\mathrm{cbs}(f) = O(\mathrm{CA}(f))\) relation Settled
\(\lambda(f)\) \(\mathrm{D}(f)\) separations only → 1,1
\(\lambda(f)\) \(\mathrm{R}_{\varepsilon}(f)\) separations only → 1,1
\(\lambda(f)\) \(\mathrm{R}_{0}(f)\) separations only → 1,1
\(\lambda(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) separations only → 1,1
\(\lambda(f)\) \(\mathrm{Q}_{\mathrm{E}}(f)\) separations only → 1,1
\(\lambda(f)\) \(\deg(f)\) separations only → 1,1
\(\lambda(f)\) \(\widetilde{\deg}_{\varepsilon}(f)\) separations only → 1,1
\(\lambda(f)\) \(\mathrm{rdeg}(f)\) Wide open separations only → 1.5,3
\(\lambda(f)\) \(\mathrm{s}(f)\) Settled \(\lambda(f) \le \mathrm{s}(f)\) partial Settled 1,1
\(\lambda(f)\) \(\mathrm{bs}(f)\) separations only → 1,1
\(\lambda(f)\) \(\mathrm{C}(f)\) separations only → 1,1
\(\lambda(f)\) \(\mathrm{RC}(f)\) separations only → 1,1
\(\lambda(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\lambda(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{C}(f)\) \(\mathrm{D}(f)\) Settled \(\mathrm{C}(f) \le \mathrm{D}(f)\) relation Settled 1,1
\(\mathrm{C}(f)\) \(\mathrm{R}_{\varepsilon}(f)\) Settled \(\mathrm{C}(f)=O(\mathrm{R}(f)^2)\) 2,2
\(\mathrm{C}(f)\) \(\mathrm{R}_{0}(f)\) Gap \(\mathrm{C}(f) \le \mathrm{R}_0(f)\) relation Settled 1,1
\(\mathrm{C}(f)\) \(\mathrm{R}^{1}(f)\) Settled \(\mathrm{C}(f)=O(\mathrm{R}^{1}(f)^2)\)
\(\mathrm{C}(f)\) \(\mathrm{R}_{\mathrm{RP}}(f)\) Settled \(\mathrm{C}(f)=O(\mathrm{R}_{\mathrm{RP}}(f)^2)\)
\(\mathrm{C}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) Settled \(\mathrm{C}(f)=O(\mathrm{Q}(f)^4)\) 4,4
\(\mathrm{C}(f)\) \(\mathrm{Q}_{\mathrm{E}}(f)\) Gap \(\mathrm{C}(f)=O(\mathrm{Q}_{\mathrm{E}}(f)^3)\) 2,3
\(\mathrm{C}(f)\) \(\mathrm{Q}_{0}(f)\) Gap \(\mathrm{C}(f)=O(\mathrm{Q}_0(f)^3)\)
\(\mathrm{C}(f)\) \(\deg(f)\) Gap separations only → 2,3
\(\mathrm{C}(f)\) \(\widetilde{\deg}_{\varepsilon}(f)\) Settled \(\mathrm{C}(f)=O(\widetilde{\deg}(f)^4)\) 4,4
\(\mathrm{C}(f)\) \(\mathrm{rdeg}(f)\) separations only → 2,4
\(\mathrm{C}(f)\) \(\overline{\deg}^{\mathrm{cert}}(f)\) Gap \(\mathrm{C}(f)=O((\overline{\deg}^{\mathrm{cert}}(f))^3)\)
\(\mathrm{C}(f)\) \(\mathrm{s}(f)\) Gap \(\mathrm{C}(f) \le \mathrm{s}(f)\cdot\mathrm{bs}(f) \le 2\,\mathrm{s}(f)\deg(f)^2 \le 2\,\mathrm{s}(f)^5\) 3,5
\(\mathrm{C}(f)\) \(\mathrm{bs}(f)\) Settled \(\mathrm{C}(f) \le \mathrm{s}(f)\cdot \mathrm{bs}(f) \le \mathrm{bs}(f)^2\) 2,2
\(\mathrm{C}(f)\) \(\mathrm{fbs}(f)\) Settled \(\mathrm{C}(f) = O\big(\mathrm{fbs}(f)^2\big)\) No bound exists
\(\mathrm{C}(f)\) \(\lambda(f)\) separations only → 4,6
\(\mathrm{C}(f)\) \(\mathrm{SP}(f)\) Settled \(\mathrm{C}(f) \le \mathrm{SP}(f)\) partial Settled
\(\mathrm{C}(f)\) \(\mathrm{RC}(f)\) Settled \(\mathrm{C}(f) = O(\mathrm{RC}(f)^2)\) 2,2
\(\mathrm{C}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{C}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{C}(f)\) \(\mathrm{prt}_{\varepsilon}(f)\) \(\mathrm{C}(f) \le \mathrm{prt}_{0}(f)\) partial Settled
\(\mathrm{C}(f)\) \(\overline{\mathrm{prt}}_{\varepsilon}(f)\) \(\mathrm{C}(f) \le \overline{\mathrm{prt}}_{0}(f)\) partial Settled
\(\mathrm{C}(f)\) \(\chi(f)\) Settled \(\mathrm{C}(f)\le\mathrm{bs}(f)^2\le4\chi(f)^2\)
\(\mathrm{C}^0(f)\) \(\mathrm{bs}^0(f)\) No bound exists \(\mathrm{C}^0(f) \le \mathrm{s}^1(f)\,\mathrm{bs}^0(f)\)
\(\mathrm{C}^0(f)\) \(\mathrm{C}(f)\) \(\mathrm{C}^0(f) \le \mathrm{C}(f)\) partial Settled
\(\mathrm{C}^0(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{C}^0(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{C}^1(f)\) \(\mathrm{R}^{1}(f)\) \(\mathrm{C}^{1}(f) \le \mathrm{R}^{1}(f)\) partial Settled
\(\mathrm{C}^1(f)\) \(\mathrm{psD}(S)\) separations only → Gap
\(\mathrm{C}^1(f)\) \(\mathrm{bs}^1(f)\) No bound exists \(\mathrm{C}^1(f) \le \mathrm{s}^0(f)\,\mathrm{bs}^1(f)\)
\(\mathrm{C}^1(f)\) \(\mathrm{cbs}(S)\) separations only → Gap
\(\mathrm{C}^1(f)\) \(\mathrm{C}(f)\) \(\mathrm{C}^1(f) \le \mathrm{C}(f)\) relation Settled
\(\mathrm{C}^1(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{C}^1(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{C}_{\min}(f)\) \(\mathrm{DTsize}(f)\) Settled \(\mathrm{C}_{\min}(f) \le \log_2 \mathrm{DTsize}(f)\) partial Settled
\(\mathrm{C}_{\min}(f)\) \(\mathrm{C}(f)\) \(\mathrm{C}_{\min}(f) \le \mathrm{C}(f)\) relation Settled
\(\mathrm{C}_{\min}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{C}_{\min}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{UC}(f)\) \(\mathrm{SP}(f)\) \(\mathrm{UC}(f) \le \mathrm{SP}(f)\) partial Settled
\(\mathrm{UC}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{UC}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{UC}_{\min}(f)\) \(\mathrm{DTsize}(f)\) Gap separations only →
\(\mathrm{UC}_{\min}(f)\) \(\mathrm{UC}(f)\) \(\mathrm{UC}_{\min}(f) \le \mathrm{UC}(f)\) partial Settled
\(\mathrm{UC}_{\min}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{UC}_{\min}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{SP}(f)\) \(\mathrm{D}(f)\) Settled \(\mathrm{SP}(f) \le \mathrm{D}(f)\) partial Settled
\(\mathrm{SP}(f)\) \(\mathrm{UC}(f)\) Settled \(\mathrm{SP}(f) \le \mathrm{UC}(f)\) partial Settled
\(\mathrm{SP}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{SP}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\lambda^{\mathrm{cert}}(f)\) \(\lambda(f)\) \(\lambda^{\mathrm{cert}}(f)\le\lambda(f)\) partial Gap
\(\mathrm{RC}(f)\) \(\mathrm{D}(f)\) separations only → 1,1
\(\mathrm{RC}(f)\) \(\mathrm{R}_{\varepsilon}(f)\) separations only → 1,1
\(\mathrm{RC}(f)\) \(\mathrm{R}_{0}(f)\) separations only → 1,1
\(\mathrm{RC}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) separations only → 2,2
\(\mathrm{RC}(f)\) \(\mathrm{Q}_{\mathrm{E}}(f)\) separations only → 1.15,2
\(\mathrm{RC}(f)\) \(\deg(f)\) separations only → 1.63,2
\(\mathrm{RC}(f)\) \(\widetilde{\deg}_{\varepsilon}(f)\) Settled \(\mathrm{RC}(f) = O\big(\widetilde{\deg}(f)^2\big)\) 2,2
\(\mathrm{RC}(f)\) \(\mathrm{rdeg}(f)\) separations only → 2,4
\(\mathrm{RC}(f)\) \(\mathrm{s}(f)\) Gap separations only → 2.130825579397823,4
\(\mathrm{RC}(f)\) \(\mathrm{bs}(f)\) separations only → 1.5,2
\(\mathrm{RC}(f)\) \(\mathrm{fbs}(f)\) \(\mathrm{RC}(f) = \Theta(\mathrm{fbs}(f))\) partial Settled
\(\mathrm{RC}(f)\) \(\lambda(f)\) Gap separations only → 2.130825579397823,4
\(\mathrm{RC}(f)\) \(\mathrm{C}(f)\) Settled \(\mathrm{RC}(f) = \Theta(\mathrm{fbs}(f)) \le \mathrm{C}(f)\) partial Settled 1,1
\(\mathrm{RC}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{RC}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{RC}(f)\) \(\mathrm{prt}_{\varepsilon}(f)\) \(\mathrm{RC}_{2\varepsilon/(1-2\varepsilon)}(f) \le \mathrm{prt}_{\varepsilon}(f) + \log(1/\varepsilon)\) partial Settled
\(\mathrm{RC}(f)\) \(\overline{\mathrm{prt}}_{\varepsilon}(f)\) \(\mathrm{RC}_{2\varepsilon/(1-2\varepsilon)}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) + \log(1/\varepsilon)\) partial Settled
\(\mathrm{EC}(f)\) \(\mathrm{C}(f)\) \(\mathrm{EC}(f) \le \mathrm{C}(f)\) partial Settled
\(\mathrm{EC}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{EC}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{I}(f)\) \(\mathrm{DTsize}(f)\) Settled \(\mathrm{I}(f) \le \log_2 \mathrm{DTsize}(f)\)
\(\mathrm{I}(f)\) \(\mathrm{N}_{p}(f)\) Settled \(\mathrm{I}(f)\log \mathrm{I}(f) = O\big(\mathrm{N}_p(f)\big),\quad\text{i.e.}\quad \mathrm{I}(f) = O\!\left(\frac{\mathrm{N}_p(f)}{\log \mathrm{N}_p(f)}\right)\)
\(\mathrm{I}(f)\) \(\deg(f)\) Settled \(\mathrm{I}(f) \le \deg(f)\)
\(\mathrm{I}(f)\) \(\widetilde{\deg}_{\varepsilon}(f)\) Settled \(\mathrm{I}(f) = O(\widetilde{\deg}(f))\)
\(\mathrm{I}(f)\) \(\mathrm{s}(f)\) Settled \(\mathrm{I}(f) \le \mathrm{s}(f)\)
\(\mathrm{I}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{I}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{I}^{1}(f)\) \(\mathrm{DTsize}(f)\) Settled \(\mathrm{I}^{1}(f) \le \log_2 \mathrm{DTsize}(f)\)
\(\mathrm{I}^{1}(f)\) \(\deg(f)\) Gap \(\mathrm{I}^{1}(p) = O(\deg(p)^2) \text{ for bounded } p:\{-1,1\}^n\to[-1,1]\)
\(\mathrm{I}^{1}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{I}^{1}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{MaxInf}(f)\) \(\widetilde{\deg}_{\varepsilon}(f)\) Settled \(\max_i\mathrm{Inf}_i(p)\ge c\,\mathrm{Var}(p)^{5/2}/d^6,\qquad d=\deg(p)\ge1\)
\(\mathrm{MaxInf}(f)\) \(\mathrm{NS}_{\delta}(f)\) Settled \(\mathrm{MaxInf}(f) \le \mathrm{NS}_\delta(f)/\delta \quad (0 \le \delta \le \tfrac12)\)
\(\mathrm{MaxInf}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{osss}(f)\) \(\mathrm{R}_{0}(f)\) Settled \(\mathrm{osss}(f) \;=\; \frac{\mathrm{Var}(f)}{\mathrm{MaxInf}(f)} \;\le\; \bar{\mathrm{R}}_0(f) \;=\; \mathrm{R}_0(f)\)
\(\mathrm{osss}(f)\) \(\mathrm{spar}(f)\) Gap \(\mathrm{osss}(f) \;\le\; \mathrm{spar}(f)\)
\(\mathrm{NS}_{\delta}(f)\) \(\mathrm{D}(f)\) Settled \(\mathrm{NS}_\delta(f) = O(\delta\,\mathrm{D}(f))\)
\(\mathrm{NS}_{\delta}(f)\) \(\mathrm{I}(f)\) Settled \(\mathrm{NS}_\delta(f) \le \delta\,\mathrm{I}(f)\)
\(\mathrm{NS}_{\delta}(f)\) \(\mathrm{MaxInf}(f)\) No bound exists separations only →
\(\mathrm{NS}_{\delta}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{Stab}_{\rho}(f)\) \(\mathrm{MaxInf}(f)\) No bound exists separations only →
\(\mathrm{Stab}_{\rho}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{nsr}(f)\) \(\mathrm{s}(f)\) Settled \(\mathrm{nsr}(f) \;\le\; 4\,\mathrm{s}(f)\)
\(\hat{L}_1(f)\) \(\mathrm{D}(f)\) Settled \(\hat L_1(f) \le 2^{\mathrm{D}(f)}\)
\(\hat{L}_1(f)\) \(\mathrm{DTsize}(f)\) Settled \(\hat L_1(f) \le \mathrm{DTsize}(f)\)
\(\hat{L}_1(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\hat{L}_1(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{spar}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{spar}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\dim_{\mathbb{F}_2}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\dim_{\mathbb{F}_2}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{CA}(f)\) \(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{CA}(S) = O\big(\mathrm{R}(S)\big)\) relation Settled
\(\mathrm{CA}(f)\) \(\mathrm{psD}(S)\) separations only → Gap
\(\mathrm{CA}(f)\) \(\widetilde{\deg}_{\varepsilon}(f)\) \(\widetilde{\deg}_{\varepsilon}(f) \ge \tfrac{1}{\pi}\sqrt{(1-2\varepsilon)\,\mathrm{CA}(f)}\) partial Settled
\(\mathrm{CA}(f)\) \(\mathrm{fbs}(f)\) Settled \(\mathrm{CA}(f) = \Theta\big(\mathrm{fbs}(f)\big)\)
\(\mathrm{CA}(f)\) \(\mathrm{cbs}(S)\) separations only → Gap
\(\mathrm{CA}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{CA}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{CA}(f)\) \(\mathrm{Adv}(f)\) \(\mathrm{Adv}(f) \le \mathrm{CA}(f) \le 2\,\mathrm{Adv}(f)^2\) partial Settled
\(\mathrm{CA}(f)\) \(\mathrm{CG}^{\mathrm{pub}}(f)\) \(\mathrm{CA}(f) = \Theta\big(\mathrm{CG}^{\mathrm{pub}}(f)\big)\) partial Settled
\(\mathrm{CA}(f)\) \(\mathrm{prt}_{\varepsilon}(f)\) \((1-4\varepsilon)\,\mathrm{CA}(f) \le \mathrm{prt}_{\varepsilon}(f) + \log(1/\varepsilon)\) partial Settled
\(\mathrm{Adv}(f)\) \(\mathrm{psD}(S)\) separations only → Gap
\(\mathrm{Adv}(f)\) \(\widetilde{\deg}_{\varepsilon}(f)\) \(\mathrm{Adv}(f) = O\big(\widetilde{\deg}(f)^2\big)\) partial Gap
\(\mathrm{Adv}(f)\) \(\mathrm{fbs}(f)\) Settled \(\mathrm{Adv}(f) \le \sqrt{\mathrm{FC}^{0}(f)\,\mathrm{FC}^{1}(f)} \le \mathrm{fbs}(f)\)
\(\mathrm{Adv}(f)\) \(\mathrm{cbs}(S)\) separations only → Gap
\(\mathrm{Adv}(f)\) \(\lambda(f)\) \(\lambda(f) \le \mathrm{Adv}(f)\) partial Settled
\(\mathrm{Adv}(f)\) \(\mathrm{C}(f)\) \(\mathrm{Adv}(f) \le \sqrt{\mathrm{C}^{0}(f)\,\mathrm{C}^{1}(f)} \le \mathrm{C}(f)\) partial Settled
\(\mathrm{Adv}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{Adv}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{CG}(f)\) \(\mathrm{D}(f)\) Settled \(\mathrm{CG}(f) \le \mathrm{C}^0(f)\,\mathrm{C}^1(f) \le \mathrm{D}(f)^2\)
\(\mathrm{CG}(f)\) \(\mathrm{R}_{0}(f)\) Settled \(\mathrm{CG}(f) \le \mathrm{C}^0(f)\,\mathrm{C}^1(f) \le \mathrm{R}_0(f)^2\)
\(\mathrm{CG}(f)\) \(\mathrm{C}(f)\) Settled \(\mathrm{CG}(f) \le \mathrm{C}^0(f)\,\mathrm{C}^1(f) \le \mathrm{C}(f)^2\)
\(\mathrm{CG}(f)\) \(\mathrm{EC}(f)\) Settled \(\mathrm{CG}(f) = O\big(\mathrm{EC}(f)^2\big)\)
\(\mathrm{CG}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{CG}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{CG}(f)\) \(\mathrm{Adv}(f)\) Wide open separations only →
\(\mathrm{CG}(f)\) \(\mathrm{CG}^{\mathrm{pub}}(f)\) separations only → No bound exists
\(\mathrm{CG}^{\mathrm{pub}}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{CG}^{\mathrm{pub}}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{CG}^{\mathrm{pub}}(f)\) \(\mathrm{CA}(f)\) \(\mathrm{CG}^{\mathrm{pub}}(f) = \Theta\big(\mathrm{CA}(f)\big)\) partial Settled
\(\mathrm{CG}^{\mathrm{pub}}(f)\) \(\mathrm{CG}(f)\) \(\mathrm{CG}^{\mathrm{pub}}(f) \le \mathrm{CG}(f)\) partial Gap
\(\mathrm{CG}^{\mathrm{pub}}(f)\) \(\mathrm{CG}^{*}(f)\) \(\mathrm{CG}^{*}(f) \le \mathrm{CG}^{\mathrm{pub}}(f)\) partial Settled
\(\mathrm{CG}^{\mathrm{pub}}(f)\) \(\mathrm{CG}^{\mathrm{ns}}(f)\) \(\mathrm{CG}^{\mathrm{ns}}(f) \le \mathrm{CG}^{*}(f) \le \mathrm{CG}^{\mathrm{pub}}(f)\) partial Settled
\(\mathrm{CG}^{*}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) Gap separations only →
\(\mathrm{CG}^{*}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{CG}^{*}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{CG}^{\mathrm{ns}}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{CG}^{\mathrm{ns}}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{Adv}^{\pm}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{Adv}^{\pm}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{Adv}^{\pm}(f)\) \(\mathrm{Adv}(f)\) Gap \(\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}(f)) \le \mathrm{D}(f) \le \mathrm{bs}(f)^3 \le \mathrm{Adv}(f)^6\) Settled Settled
\(\gamma_2^{\alpha}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) \(\gamma_2^{\alpha}(f) = O\big(\mathrm{Q}_{\varepsilon}(f)\big)\) partial Settled
\(\gamma_2^{\alpha}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\gamma_2^{\alpha}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\gamma_2^{\alpha}(f)\) \(\mathrm{Adv}^{\pm}(f)\) \(\gamma_2^{\alpha}(f) = O\big(\mathrm{Adv}^{\pm}(f)\big)\) partial Settled
\(\mathrm{MAdv}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) \(\mathrm{MAdv}(f) = O\big(\mathrm{Q}_{\varepsilon}(f)\big)\) partial Settled
\(\mathrm{MAdv}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{MAdv}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{MAdv}(f)\) \(\mathrm{Adv}^{\pm}(f)\) \(\mathrm{Adv}^{\pm}(f) = O\big(\mathrm{MAdv}(f)\big)\) partial Settled
\(\mathrm{prt}_{\varepsilon}(f)\) \(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{prt}_{\varepsilon}(f) \le 2\,\mathrm{R}_{\varepsilon}(f)\) relation Settled
\(\mathrm{prt}_{\varepsilon}(f)\) \(\mathrm{psD}(S)\) separations only → Gap
\(\mathrm{prt}_{\varepsilon}(f)\) \(\mathrm{cbs}(S)\) separations only → Gap
\(\mathrm{prt}_{\varepsilon}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{prt}_{\varepsilon}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) \(\mathrm{psD}(S)\) separations only → Gap
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) \(\mathrm{cbs}(S)\) separations only → Gap
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) \(\mathrm{prt}_{\varepsilon}(f)\) \(\overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{prt}_{\varepsilon}(f)\) relation Settled
\(\mathrm{RS}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{RS}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{RS}(f)\) \(\mathrm{prt}_{\varepsilon}(f)\) Settled separations only →
\(\mathrm{RS}(f)\) \(\chi(f)\) Gap separations only →
\(\mathrm{RS}(f)\) \(\bar{\chi}(f)\) \(\mathrm{RS}(g) = O\big(\bar\chi(g)\big)\) partial Settled
\(\chi(f)\) \(\mathrm{D}(f)\) \(\chi(g) \le \mathrm{D}(g)\) partial Settled
\(\chi(f)\) \(\mathrm{bs}(f)\) Gap \(\chi(g) = \Omega(\mathrm{bs}(g))\)
\(\chi(f)\) \(\mathrm{C}(f)\) Settled \(\chi(g) \le \mathrm{C}(g)^2\)
\(\chi(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\chi(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\chi(f)\) \(\mathrm{RS}(f)\) Gap separations only →
\(\chi(f)\) \(\chi(f)\) No bound exists separations only →
\(\chi(f)\) \(\bar{\chi}(f)\) \(\chi(g) \le \bar\chi(g)\) partial Settled
\(\bar{\chi}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\bar{\chi}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\bar{\chi}(f)\) \(\mathrm{RS}(f)\) Gap \(\bar\chi(g) = \Omega(\mathrm{RS}(g))\) partial No bound exists
\(\bar{\chi}(f)\) \(\chi(f)\) Gap separations only →
\(\bar{\chi}(f)\) \(\mathrm{LR}(f)\) \(\bar\chi(g) = O\big(\mathrm{LR}(g)\big)\) partial Settled
\(\mathrm{LR}(f)\) \(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{LR}(f) \le \mathrm{R}(f)\) partial Gap
\(\mathrm{LR}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{LR}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{LR}(f)\) \(\bar{\chi}(f)\) Gap \(\bar\chi(g) = O(\mathrm{LR}(g))\) partial Settled
\(\mathrm{LR}(f)\) \(\mathrm{R}^{*}(f)\) Settled \(\mathrm{LR}(f) = O\big(\mathrm{R}^{*}(f)\big)\)
\(\mathrm{noisyR}(f)\) \(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{noisyR}(f) \le \mathrm{R}(f)\) partial Settled Settled
\(\mathrm{noisyR}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{noisyR}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →
\(\mathrm{noisyR}(f)\) \(\mathrm{noisyR}^{\mathrm{na}}(f)\) \(\mathrm{noisyR}(f) \le \mathrm{noisyR}^{\mathrm{na}}(f)\) relation Gap
\(\mathrm{noisyR}^{\mathrm{na}}(f)\) \(\mathrm{R}^{\mathrm{na}}(f)\) \(\mathrm{noisyR}^{\mathrm{na}}(f) \le \mathrm{R}^{\mathrm{na}}(f)\) partial Settled Settled
\(\mathrm{noisyR}^{\mathrm{na}}(f)\) \(\mathrm{noisyR}(f)\) Gap separations only →
\(\mathrm{Corr}_{\varepsilon}(f)\) \(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{Corr}(f) \le \mathrm{R}(f)\) partial Settled
\(\mathrm{Corr}_{\varepsilon}(f)\) \(\mathrm{Sel}_{\varepsilon}(f)\) \(\mathrm{Corr}(f, D) = O\big(\mathrm{Sel}(f, D)\big) \text{ for every } (f,D)\) partial Settled
\(\mathrm{Sel}_{\varepsilon}(f)\) \(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{Sel}(f) \le \mathrm{R}(f)\) partial Settled
\(\mathrm{R}^{*}(f)\) \(\mathrm{R}_{\varepsilon}(f)\) Settled \(\mathrm{R}^{*}(f)=O(\mathrm{R}(f)\log(\mathrm{R}(f)+1))\) partial Settled
\(\mathrm{R}^{*}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) Wide open \(\mathrm{R}^{*}(f) = \Omega(\mathrm{Q}(f))\)
\(\mathrm{R}^{*}(f)\) \(\mathrm{NS}_{\delta}(f)\) No bound exists separations only →
\(\mathrm{R}^{*}(f)\) \(\mathrm{Stab}_{\rho}(f)\) No bound exists separations only →

Named relation records

Some records are about a phenomenon rather than a single ordered pair (composition theorems, parameter dependence). They carry a stable id you can link to.

idPairSettingHeadline
comp-D \(\mathrm{D}(f)\) \(\mathrm{D}(f)\) relation \(\mathrm{D}(f\circ g^n) = \mathrm{D}(f)\,\mathrm{D}(g)\)
comp-MAJ \(\mathrm{R}_{\varepsilon}(f)\) \(\bar{\mathrm{R}}_{\varepsilon}(f)\) total \(\mathrm{R}(\mathrm{MAJ}_n\circ g^n) = \Theta\big(n\cdot \bar{\mathrm{R}}_{1/n}(g)\big)\)
comp-Q \(\mathrm{Q}_{\varepsilon}(f)\) \(\mathrm{Adv}^{\pm}(f)\) partial \(\mathrm{Q}(f\circ g) = \Theta\big(\mathrm{Q}(f)\,\mathrm{Q}(g)\big)\)
comp-QE \(\mathrm{Q}_{\mathrm{E}}(f)\) \(\mathrm{Q}_{\mathrm{E}}(f)\) total \(\mathrm{Q}_{\mathrm{E}}(f\circ g)\not\asymp\mathrm{Q}_{\mathrm{E}}(f)\mathrm{Q}_{\mathrm{E}}(g)\)
comp-R \(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{R}_{\varepsilon}(f)\) partial \(\frac{\mathrm{R}(f)\mathrm{R}(g)}{\log(n+1)}\lesssim\mathrm{R}(f\circ g^n)\lesssim\mathrm{R}(f)\mathrm{R}(g)\log(\mathrm{R}(f)+1)\)
comp-adeg \(\widetilde{\deg}_{\varepsilon}(f)\) \(\widetilde{\deg}_{\varepsilon}(f)\) total \(\widetilde{\deg}(f\circ g)=\Theta(\widetilde{\deg}(f)\widetilde{\deg}(g))\)
comp-chi \(\chi(f)\) \(\chi(f)\) total \(\chi(f\circ g)\not\asymp\chi(f)\chi(g)\)
comp-deg \(\deg(f)\) \(\deg(f)\) total \(\deg(f\circ g) = \deg(f)\,\deg(g)\)
dirprod-Q \(\mathrm{Q}_{\varepsilon}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) total \(\mathrm{Q}(f^{\otimes k}) = \tilde\Theta\big(k\,\mathrm{Q}(f)\big) \text{ for Boolean } f\)
dirprod-R \(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{R}_{\varepsilon}(f)\) total \(\text{Solving } f^{\otimes k} \text{ with } \ll k\,\mathrm{R}(f) \text{ queries succeeds with probability } 2^{-\Omega(k)}\)
dirsum-D \(\mathrm{D}(f)\) \(\mathrm{D}(f)\) relation \(\mathrm{D}(f^{\otimes k}) = k\,\mathrm{D}(f)\)
dirsum-R \(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{R}_{\varepsilon}(f)\) relation \(\Omega\big(k\,\mathrm{R}(f)\big) \;\le\; \mathrm{R}(f^{\otimes k}) \;\le\; O\big(k\,\mathrm{R}(f)\log k\big),\ \text{both ends attained}\)
param-Np-p \(\mathrm{N}_{p}(f)\) \(\mathrm{N}_{p}(f)\) relation \(\mathrm{N}_{p}(f) \text{ as a function of the flip probability } p\)
param-Q-eps \(\mathrm{Q}_{\varepsilon}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) partial \(\mathrm{Q}_{\varepsilon}(f) \text{ as } \varepsilon\to 0\)
param-Q-zero-error \(\mathrm{Q}_{0}(f)\) \(\mathrm{Q}_{\mathrm{E}}(f)\) total
param-Q-zero-error-rel \(\mathrm{Q}_{0}(f)\) \(\mathrm{Q}_{\mathrm{E}}(f)\) relation
param-R-directsum \(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{R}_{\varepsilon}(f)\) partial \(\text{Strong direct sum: } \bar{\mathrm{R}}_\varepsilon(f^{k}) = \Theta\big(k\,\bar{\mathrm{R}}_{\varepsilon/k}(f)\big)\)
param-R-eps \(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{R}_{\varepsilon}(f)\) partial \(\mathrm{R}_{\varepsilon}(f) \text{ as } \varepsilon \to 0\)
param-R-vs-Rbar \(\mathrm{R}_{\varepsilon}(f)\) \(\bar{\mathrm{R}}_{\varepsilon}(f)\) relation
param-adeg-eps \(\widetilde{\deg}_{\varepsilon}(f)\) \(\widetilde{\deg}_{\varepsilon}(f)\) total \(\widetilde{\deg}_{\varepsilon}(f) \text{ as } \varepsilon \to 0 \text{ and } \varepsilon\to 1/2\)
param-adeg-eps-partial \(\widetilde{\deg}_{\varepsilon}(f)\) \(\widetilde{\deg}_{\varepsilon}(f)\) partial \(\widetilde{\deg}_{\varepsilon}(f) = O\big(\widetilde{\deg}_{1/3}(f)\log(1/\varepsilon)\big)\)
param-minimax \(\bar{\mathrm{R}}_{\varepsilon}(f)\) \(\mathrm{D}^{\mu}_{\varepsilon}(f)\) partial
param-minimax-rel \(\bar{\mathrm{R}}_{\varepsilon}(f)\) \(\mathrm{D}^{\mu}_{\varepsilon}(f)\) relation \(\text{Yao minimax: } \bar{\mathrm{R}}_\varepsilon(f) = \Theta\big(\max_\mu \mathrm{D}^{\mu}_{\varepsilon}(f)\big)\)
param-zero-error \(\mathrm{R}_{0}(f)\) \(\mathrm{D}(f)\) total
param-zero-error-rel \(\mathrm{R}_{0}(f)\) \(\mathrm{D}(f)\) relation
recent-C-vs-Q-total \(\mathrm{C}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) total
recent-C-vs-Q0-total \(\mathrm{C}(f)\) \(\mathrm{Q}_{0}(f)\) total
recent-C-vs-QE-total \(\mathrm{C}(f)\) \(\mathrm{Q}_{\mathrm{E}}(f)\) total
recent-C-vs-R-total \(\mathrm{C}(f)\) \(\mathrm{R}_{\varepsilon}(f)\) total
recent-C-vs-R1-total \(\mathrm{C}(f)\) \(\mathrm{R}^{1}(f)\) total
recent-C-vs-R1RP-total \(\mathrm{C}(f)\) \(\mathrm{R}_{\mathrm{RP}}(f)\) total
recent-C-vs-adeg-total \(\mathrm{C}(f)\) \(\widetilde{\deg}_{\varepsilon}(f)\) total
recent-C-vs-deg-total \(\mathrm{C}(f)\) \(\deg(f)\) total
recent-C-vs-degcert-total \(\mathrm{C}(f)\) \(\overline{\deg}^{\mathrm{cert}}(f)\) total
recent-Q-vs-QSstr-total \(\mathrm{Q}_{\varepsilon}(f)\) \(\mathrm{QS}_{\mathrm{str}}(f)\) total
recent-Q-vs-QSstrind-total \(\mathrm{Q}_{\varepsilon}(f)\) \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f)\) total
recent-Q-vs-QSweak-total \(\mathrm{Q}_{\varepsilon}(f)\) \(\mathrm{QS}_{\mathrm{weak}}(f)\) total
recent-Q-vs-QSweakind-total \(\mathrm{Q}_{\varepsilon}(f)\) \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f)\) total
recent-Q0cert-vs-Q-total \(\mathrm{Q}_{0}^{\mathrm{cert}}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) total
recent-Q0cert-vs-Q0-partial \(\mathrm{Q}_{0}^{\mathrm{cert}}(f)\) \(\mathrm{Q}_{0}(f)\) partial
recent-Q0cert-vs-QC-total \(\mathrm{Q}_{0}^{\mathrm{cert}}(f)\) \(\mathrm{QC}(f)\) total
recent-QC-vs-Q0cert-partial \(\mathrm{QC}(f)\) \(\mathrm{Q}_{0}^{\mathrm{cert}}(f)\) partial
recent-QC-vs-QSstr-partial \(\mathrm{QC}(f)\) \(\mathrm{QS}_{\mathrm{str}}(f)\) partial
recent-QC-vs-QSstrind-partial \(\mathrm{QC}(f)\) \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f)\) partial
recent-QC-vs-QSweak-partial \(\mathrm{QC}(f)\) \(\mathrm{QS}_{\mathrm{weak}}(f)\) partial
recent-QC-vs-QSweakind-partial \(\mathrm{QC}(f)\) \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f)\) partial
recent-QEcert-vs-C-partial \(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f)\) \(\mathrm{C}(f)\) partial
recent-QEcert-vs-Q-total \(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) total
recent-QEcert-vs-QC-total \(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f)\) \(\mathrm{QC}(f)\) total
recent-QEcert-vs-QE-partial \(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f)\) \(\mathrm{Q}_{\mathrm{E}}(f)\) partial
recent-QSstr-vs-Q-partial \(\mathrm{QS}_{\mathrm{str}}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) partial
recent-QSstr-vs-QSstrind-partial \(\mathrm{QS}_{\mathrm{str}}(f)\) \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f)\) partial
recent-QSstr-vs-QSweak-partial \(\mathrm{QS}_{\mathrm{str}}(f)\) \(\mathrm{QS}_{\mathrm{weak}}(f)\) partial
recent-QSstr-vs-RS-partial \(\mathrm{QS}_{\mathrm{str}}(f)\) \(\mathrm{RS}(f)\) partial
recent-QSstr-vs-fbs-total \(\mathrm{QS}_{\mathrm{str}}(f)\) \(\mathrm{fbs}(f)\) total
recent-QSstrind-vs-Q-partial \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) partial
recent-QSstrind-vs-QSweakind-partial \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f)\) \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f)\) partial
recent-QSstrind-vs-RS-partial \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f)\) \(\mathrm{RS}(f)\) partial
recent-QSstrind-vs-fbs-total \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f)\) \(\mathrm{fbs}(f)\) total
recent-QSweak-vs-Q-total \(\mathrm{QS}_{\mathrm{weak}}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) total
recent-QSweak-vs-QSweakind-partial \(\mathrm{QS}_{\mathrm{weak}}(f)\) \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f)\) partial
recent-QSweak-vs-RS-partial \(\mathrm{QS}_{\mathrm{weak}}(f)\) \(\mathrm{RS}(f)\) partial
recent-QSweak-vs-fbs-total \(\mathrm{QS}_{\mathrm{weak}}(f)\) \(\mathrm{fbs}(f)\) total
recent-QSweakind-vs-Q-total \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) total
recent-QSweakind-vs-RS-partial \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f)\) \(\mathrm{RS}(f)\) partial
recent-QSweakind-vs-fbs-total \(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f)\) \(\mathrm{fbs}(f)\) total
recent-R-vs-R1RP-partial \(\mathrm{R}_{\varepsilon}(f)\) \(\mathrm{R}_{\mathrm{RP}}(f)\) partial
recent-R0-vs-Q-total \(\mathrm{R}_{0}(f)\) \(\mathrm{Q}_{\varepsilon}(f)\) total
recent-R1RP-vs-R0-partial \(\mathrm{R}_{\mathrm{RP}}(f)\) \(\mathrm{R}_{0}(f)\) partial
recent-RC-vs-lambda-total \(\mathrm{RC}(f)\) \(\lambda(f)\) total
recent-RC-vs-s-total \(\mathrm{RC}(f)\) \(\mathrm{s}(f)\) total
recent-adeg-vs-osdeg-partial \(\widetilde{\deg}_{\varepsilon}(f)\) \(\overline{\mathrm{osdeg}}_{\varepsilon}(f)\) partial
recent-adeg-vs-osdeg0-partial \(\widetilde{\deg}_{\varepsilon}(f)\) \(\overline{\mathrm{osdeg}}^{\,0}_{\varepsilon}(f)\) partial
recent-adeg-vs-osdeg1-partial \(\widetilde{\deg}_{\varepsilon}(f)\) \(\overline{\mathrm{osdeg}}^{\,1}_{\varepsilon}(f)\) partial
recent-bdeg-vs-QE-partial \(\overline{\deg}(f)\) \(\mathrm{Q}_{\mathrm{E}}(f)\) partial
recent-bs-vs-degcert-partial \(\mathrm{bs}(f)\) \(\overline{\deg}^{\mathrm{cert}}(f)\) partial
recent-bs-vs-lambda-total \(\mathrm{bs}(f)\) \(\lambda(f)\) total
recent-deg-vs-bdeg-partial \(\deg(f)\) \(\overline{\deg}(f)\) partial
recent-deg-vs-degcert-total \(\deg(f)\) \(\overline{\deg}^{\mathrm{cert}}(f)\) total
recent-degcert-vs-C-partial \(\overline{\deg}^{\mathrm{cert}}(f)\) \(\mathrm{C}(f)\) partial
recent-degcert-vs-Q0cert-partial \(\overline{\deg}^{\mathrm{cert}}(f)\) \(\mathrm{Q}_{0}^{\mathrm{cert}}(f)\) partial
recent-degcert-vs-QEcert-partial \(\overline{\deg}^{\mathrm{cert}}(f)\) \(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f)\) partial
recent-degcert-vs-bdeg-partial \(\overline{\deg}^{\mathrm{cert}}(f)\) \(\overline{\deg}(f)\) partial
recent-degcert-vs-osdeg-partial \(\overline{\deg}^{\mathrm{cert}}(f)\) \(\overline{\mathrm{osdeg}}_{\varepsilon}(f)\) partial
recent-degcert-vs-rdeg-total \(\overline{\deg}^{\mathrm{cert}}(f)\) \(\mathrm{rdeg}(f)\) total
recent-fbs-vs-lambda-total \(\mathrm{fbs}(f)\) \(\lambda(f)\) total
recent-fbs-vs-s-total \(\mathrm{fbs}(f)\) \(\mathrm{s}(f)\) total
recent-lambdacert-vs-lambda-partial \(\lambda^{\mathrm{cert}}(f)\) \(\lambda(f)\) partial
recent-osdeg-vs-Q0-partial \(\overline{\mathrm{osdeg}}_{\varepsilon}(f)\) \(\mathrm{Q}_{0}(f)\) partial
recent-osdeg-vs-adeg-total \(\overline{\mathrm{osdeg}}_{\varepsilon}(f)\) \(\widetilde{\deg}_{\varepsilon}(f)\) total
recent-osdeg-vs-bdeg-partial \(\overline{\mathrm{osdeg}}_{\varepsilon}(f)\) \(\overline{\deg}(f)\) partial
recent-osdeg0-vs-osdeg-partial \(\overline{\mathrm{osdeg}}^{\,0}_{\varepsilon}(f)\) \(\overline{\mathrm{osdeg}}_{\varepsilon}(f)\) partial
recent-osdeg1-vs-osdeg-partial \(\overline{\mathrm{osdeg}}^{\,1}_{\varepsilon}(f)\) \(\overline{\mathrm{osdeg}}_{\varepsilon}(f)\) partial
recent-rdeg-vs-degcert-partial \(\mathrm{rdeg}(f)\) \(\overline{\deg}^{\mathrm{cert}}(f)\) partial
recent-rdeg-vs-osdeg-partial \(\mathrm{rdeg}(f)\) \(\overline{\mathrm{osdeg}}_{\varepsilon}(f)\) partial