|
\(\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 →
|
|
|
|