Q The Query Complexity Zoo

Open problems

Active questions with the best known bounds on each side. Recent resolutions are recorded below.

Is $\mathrm{D}(f) = \widetilde O(\mathrm{R}(f)^2)$? total #

Gap between exponents 2 and 3. Both neighbouring error models are settled at 2.

How much can randomness save a decision tree on a total function? Nisan's simulation gives $\mathrm{D}(f)\le 27\,\mathrm{R}(f)^3$; the pointer functions give a family with $\mathrm{D}=\widetilde\Omega(\mathrm{R}^2)$. Nobody has closed either end since.

Best known

  • \(\mathrm{D}(f) \le 27\,\mathrm{R}(f)^3\)
    Through the combinatorial core: $\mathrm{D}\le\mathrm{C}^1\mathrm{bs}\le\mathrm{bs}^3$ and $\mathrm{bs}\le 3\mathrm{R}$. Every factor of the cube is a step nobody knows how to skip.
  • \(\mathrm{D}(f_n) = \widetilde\Omega\big(\mathrm{R}(f_n)^2\big)\)
    The best separation, and it costs polylogs. Before the pointer functions the record was the $\mathrm{D}=\Theta(\mathrm{R}_0^{1.33})$ of \(\bar{\wedge}\text{-tree}\), which Saks and Wigderson conjectured to be optimal.
  • \(\mathrm{D}(f) = O(\mathrm{R}_0(f)^2) \text{ and } \mathrm{D}(f) = O(\mathrm{R}^1(f)^2)\)
    Both are tight up to polylogs, by the same pointer functions. So zero error and one-sided error are settled at exponent 2, and two-sided bounded error is the only one of the three left open -- which is why a quadratic answer is the popular guess.

Why it matters

This is the headline cell of the classical corner, and it is the bottleneck in several others: $\mathrm{D}$ vs $\mathrm{bs}$, $\mathrm{D}$ vs $\deg$ and $\mathrm{R}$ vs $\mathrm{Q}$ all run through the same cubic-vs-quadratic slack. It is also the cell that says what randomness is worth on a total function: quadratic would mean a coin never buys more than the square root of the work, which is exactly what the Las Vegas and one-sided cases already say.

Is $\mathrm{D}(f) = O(\mathrm{bs}(f)^2)$? total #

Gap between exponents 2 and 3.

Block sensitivity is one of the two workhorse lower bounds on $\mathrm{D}$. We know $\mathrm{D}(f)\le\mathrm{s}(f)\mathrm{bs}(f)^2\le\mathrm{bs}(f)^3$ [BdW02, Cor. 1] and that $\mathrm{D}(f)$ can be $\Omega(\mathrm{bs}(f)^2)$. Which is the truth?

Best known

  • \(\mathrm{D}(f) \le \mathrm{C}^1(f)\,\mathrm{bs}(f) \le \mathrm{s}(f)\mathrm{bs}(f)^2 \le \mathrm{bs}(f)^3\)
  • \(\mathrm{D}(f_n) = \Omega(\mathrm{bs}(f_n)^2)\)
    Open problem 2 of [BdW02]; still open.

Why it matters

$\mathrm{bs}$ sits between $\mathrm{s}$ and $\mathrm{C}$, so this is the cleanest remaining question in the classical combinatorial core.

What is the optimal exponent of $\mathrm{bs}$ versus $\mathrm{s}$? total #

Quadratic conjecture refuted; exponent gap [2.1308255793978239…, 4] (source checked October 22, 2026).

The proposed quadratic upper bound is false. [OpenAISensitivity26] first constructed total functions with a fixed exponent strictly larger than two. The accepted public theorem [Prove2MeSensitivity26] gives, for every $\varepsilon>0$ and arbitrarily large sensitivity, $$\mathrm{bs}(f)\ge\mathrm{s}(f)^{\alpha-\varepsilon},\qquad \alpha=\frac{\log(14055^8)}{\log(3738277295413674)}=2.1308255793978239\ldots.$$ The universal upper bound remains $\mathrm{bs}\le2\deg^2\le2\mathrm{s}^4$. What is the optimal exponent in this interval?

Best known

  • \(\mathrm{bs}(f) \le 2\deg(f)^2 \le 2\,\mathrm{s}(f)^4\)
  • \(\forall\varepsilon>0,\ S\ge2,\ \exists f:\ \mathrm{s}(f)\ge S,\ \mathrm{bs}(f)\ge\mathrm{s}(f)^{\alpha-\varepsilon}\)
    $\alpha=\log(14055^8)/\log(3738277295413674)$. The public theorem is marked Proved. No assertion of a loss-free endpoint or a matching upper bound.
  • \(\exists\alpha>2,\ (F_m):\ \mathrm{bs}(F_m,0)\ge\mathrm{s}(F_m)^\alpha,\quad \mathrm{bs}(F_m,0)\to\infty\)
    Corollary 4.3 amplifies a fixed nested-tournament seed.
  • \(\mathrm{bs}(f) \ge \tfrac23 \mathrm{s}(f)^2 - \tfrac13\mathrm{s}(f)\)
    Improving Rubinstein's $\mathrm{s}^2/2$.

Why it matters

Huang settled polynomial boundedness, and the 2026 constructions rule out its quadratic strengthening. Improving either endpoint remains open. Since $\mathrm{bs}\le\mathrm{fbs}=\Theta(\mathrm{RC})$ and $\lambda\le\mathrm{s}$, the same family improves the lower exponents for fractional block sensitivity and randomized certificates versus sensitivity, and block sensitivity versus spectral sensitivity. The larger existing cubic separations of $\mathrm{D}$ and $\mathrm{C}$ from sensitivity are not improved by this implication.

What is the exponent of $\mathrm{D}$ versus $\mathrm{s}$? total #

Gap between exponents 3 and 6 -- the widest gap left in the total-function matrix.

Huang's theorem is what makes this cell finite at all: $\deg\le\mathrm{s}^2$, and Midrijanis' $\mathrm{D}\le\mathrm{bs}\cdot\deg\le2\deg^3$ then gives $\mathrm{D}(f)\le 2\,\mathrm{s}(f)^6$. The widest separation anyone has built is cubic. Nothing is known to rule out either end.

Best known

  • \(\mathrm{D}(f) \le \mathrm{bs}(f)\deg(f) \le 2\deg(f)^3 \le 2\,\mathrm{s}(f)^6\)
    Two steps, and the second one is tight: $\deg\le\mathrm{s}^2$ is matched by \(\mathrm{AND}_n \circ \mathrm{OR}_n\), which has $\deg = n^2$ against $\mathrm{s}=n$. So this route cannot do better than the square of whatever the truth is for $\mathrm{D}$ versus $\deg$, and the cell is that open problem wearing a different hat.
  • \(\mathrm{D}(f_n) = \widetilde\Omega\big(\mathrm{s}(f_n)^3\big)\)
    Desensitize a function with cheap unambiguous certificates -- triple every bit and accept only $ppp$ for $p$ a $1$-certificate, which drives $\mathrm{s}_0$ down to $1$ without moving anything else -- then compose on the outside with a function whose certificates are almost all ones. Sensitivity stays $\widetilde O(n)$ while $\mathrm{Q}$, and so $\mathrm{D}$, multiplies up to $\widetilde\Omega(n^3)$.
  • \(\mathrm{D}(f) = O(\deg(f)^2)\ \Longrightarrow\ \mathrm{D}(f) = O(\mathrm{s}(f)^4)\)
    Which is why $4$, not $3$, is the natural guess for the answer -- though no function is known that reaches it.
  • \(\mathrm{D}(P) = O(\mathrm{s}(P)^2) \text{ for every graph property } P\)
    Turán''s $\mathrm{s}(P) = \Omega(n)$ for non-trivial graph properties, against the trivial $\mathrm{D}(P)\le\binom n2$. [CPS23] prove the matching $\mathrm{D}(P)=O(\deg(P)^2)$ and get quadratic bounds for two further classes: functions with a constant number of alternations, and "zebra" functions, where every monotone path from $0^n$ to $1^n$ alternates equally often (this contains the symmetric and the monotone functions).

Why it matters

This is the cell every other row inherits: a bound in terms of $\mathrm{s}$ is almost always routed through $\deg$ or $\mathrm{bs}$, so the sixth power reappears all over the $\mathrm{s}$ column. It is also the one place where Huang's theorem is load-bearing -- before 2019 no polynomial bound existed here at all.

A useful contrast is \(\lambda(f)\), the spectral sensitivity that Huang's proof actually bounds. It obeys the same sixth-power ceiling, but its separation is quartic, from the pointer functions: they have $\lambda=\widetilde O(n^{1/4})$ against $\mathrm{D}=\widetilde\Omega(n)$, while their sensitivity is $\widetilde O(\sqrt n)$ and so gives only a quadratic gap. Sensitivity is the harder measure to hold down, and \(f_{\mathrm{BHT}}\) is the only construction that does.

Is $\mathrm{D}(f) = O(\deg(f)^2)$? total #

Gap between exponents 2 and 3.

Exact polynomial degree lower-bounds everything. Nisan-Smolensky gave $\mathrm{D}\le 2\deg^4$, improved by Midrijanis to $\mathrm{D}=O(\deg^3)$. The best separation is quadratic.

Best known

  • \(\mathrm{D}(f) \le \mathrm{bs}(f)\deg(f) = O(\deg(f)^3)\)
    Midrijanis' inequality $\mathrm{D}\le\mathrm{bs}\cdot\deg$ combined with $\mathrm{bs}\le2\deg^2$.
  • \(\mathrm{D}(f) \le \deg(f)^2\,\mathrm{bs}(f) \le 2\deg(f)^4\)
    The earlier bound.
  • \(\mathrm{D}(f_n) = \tilde\Omega(\deg(f_n)^2)\)
    The $\mathrm{D}$-vs-$\deg$ cell of the matrix; see that cell for the construction.

Why it matters

A positive answer would say the polynomial method loses at most a square.

Is $\mathrm{D}(f) = O(\mathrm{Q}_E(f)^2)$? total #

Gap between exponents 2 and 3.

An exact quantum algorithm has to be right on every input, which is a strong enough demand that no total function is known to gain more than a square by it. Midrijanis' simulation gives $\mathrm{D}(f)=O(\mathrm{Q}_E(f)^3)$; the pointer functions give a family with $\mathrm{D}=\widetilde\Omega(\mathrm{Q}_E^2)$.

Best known

  • \(\mathrm{D}(f) \le 2\deg(f)^3 \le 16\,\mathrm{Q}_E(f)^3\)
    Through the degree, using $\deg\le2\mathrm{Q}_E$: an exact algorithm making $T$ queries writes the acceptance probability as a polynomial of degree $2T$, and for an exact algorithm that polynomial is $f$. Midrijanis states the cubic bound in this form; it superseded the $\mathrm{D}=O(\mathrm{Q}_E^4)$ of [BBCMdW01].
  • \(\mathrm{D}(f_n) = \widetilde\Omega\big(\mathrm{Q}_E(f_n)^2\big)\)
    The same family that gives the quadratic $\mathrm{D}$-vs-$\mathrm{R}_0$ separation: $\mathrm{D}=\widetilde\Omega(n)$ against $\mathrm{Q}_E=\widetilde O(\sqrt n)$, so exactness costs the pointer-chasing algorithm nothing.
  • \(\mathrm{Q}_E(f) = O(\mathrm{D}(f)^{0.8675})\)
    Exponent $1.15$, and historically the hard part: the first proof that an exact quantum algorithm can beat a deterministic one by more than a constant at all.
  • \(\mathrm{D}(f) = O(\deg(f)^2)\ \Longrightarrow\ \mathrm{D}(f) = O(\mathrm{Q}_E(f)^2)\)
    And that would be tight, by the pointer functions. So this cell closes the moment $\mathrm{D}$ versus $\deg$ does.

Why it matters

$\mathrm{Q}_E$ sits between $\deg$ and $\mathrm{D}$, and this cell is pinned on both sides by open problems: $\deg\le2\mathrm{Q}_E\le2\mathrm{D}$, with Is …? asking whether the left inequality is tight and Is …? asking about the right. If $\mathrm{Q}_E=\Theta(\deg)$ then this is the $\mathrm{D}$-vs-$\deg$ cell, and the two would close together; both currently stand at $[2,3]$.

Where there is no room at all: for symmetric $f$, $\mathrm{Q}_E(f)=\Theta(n)$ [BdW02, Thm 21], so exactness costs the whole speedup.

Is $\mathrm{Q}_E(f) = O(\deg(f))$? total #

Open. Open problem 4 of [BdW02].

We know $\deg(f)\le 2\mathrm{Q}_E(f)$. Is the converse true up to constants? Equivalently: is the polynomial method tight for exact quantum algorithms?

Best known

  • \(\deg(f) \le 2\,\mathrm{Q}_E(f)\)
  • \(\mathrm{Q}_E(f) \le \mathrm{D}(f) = O(\deg(f)^3)\)
  • \(\mathrm{Q}_E(f) = O(\mathrm{D}(f)^{0.8675})\)
    The first superlinear exact-quantum advantage for a total function; shows $\mathrm{Q}_E$ is not simply $\Theta(\mathrm{D})$.

Why it matters

For symmetric $f$, $\mathrm{Q}_E(f)=\Theta(n)$ [BdW02, Thm 21], so no speedup at all -- the question is entirely about asymmetric functions. The companion question "is $\mathrm{Q}(f)=O(\widetilde{\deg}(f))$?" is false for partial functions [AmbainisBelovs23] and open for total ones.

How much do negative weights buy the adversary? total #

Gap between exponents 2 and 6 on total functions. On partial functions the ratio is already known to be unbounded.

The positive adversary is the general one with its weights restricted to be non-negative, so $\mathrm{Adv}\le\mathrm{Adv}^{\pm}$ for free, and $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$ [Reichardt11]. The question is how far below the quantum query complexity the positive version can fall on a total function -- how much is lost by insisting on an adversary matrix that is entrywise non-negative.

Best known

  • \(\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}(f)) \le \mathrm{D}(f) \le \mathrm{bs}(f)^3 \le \mathrm{Adv}(f)^6\)
    Nothing here is about adversaries except the two ends: the middle is the ordinary classical chain, entered through $\mathrm{bs}\le\mathrm{Adv}^2$ [Ambainis02]. Every improvement to $\mathrm{D}$ versus $\mathrm{bs}$ lands here doubled.
  • \(\mathrm{Adv}^{\pm}(f_n) = \widetilde\Omega\big(\mathrm{Adv}(f_n)^2\big)\)
    The certificate complexity barrier, $\mathrm{Adv}\le\sqrt{\mathrm{C}^0\mathrm{C}^1}$, applied to a function built to have cheap certificates and expensive quantum complexity: $\mathrm{Q}=\widetilde\Theta(n)$ against $\mathrm{C}=\widetilde O(\sqrt n)$, so $\mathrm{Adv}=\widetilde O(\sqrt n)$ whatever the truth about it is.
  • \(\mathrm{Adv}^{\pm}(g^{\circ d}) \ge \mathrm{Adv}(g^{\circ d})^{1.098}\)
    Smaller, but the only separation proved between the two bounds themselves rather than through $\mathrm{Q}$. Take the monotone $g$ on six bits whose minterms and maxterms are the Hamming-weight-three inputs of a function of Kushilevitz''s, so $\mathrm{C}^0(g)=\mathrm{C}^1(g)=3$; a numerically found negative-weight matrix gives $\mathrm{Adv}^{\pm}(g)\ge 2+3\sqrt5/5\approx3.341$, both bounds compose, and the barrier caps $\mathrm{Adv}(g^{\circ d})$ at $3^d$.
  • \(\sqrt{\mathrm{fbs}(f)} \le \mathrm{Adv}(f) \le \sqrt{\mathrm{FC}^0(f)\,\mathrm{FC}^1(f)} \le \mathrm{fbs}(f)\)
    The positive adversary is pinned within a square of fractional block sensitivity, so this cell is a proxy for $\mathrm{Q}$ versus $\mathrm{fbs}$: there $\mathrm{Q}=\widetilde\Omega(\mathrm{fbs}^2)$ is known (same witness) and $\mathrm{Q}=\widetilde O(\mathrm{fbs}^2)$ would follow from $\mathrm{D}=O(\mathrm{bs}^2)$ [CPS23], which would bring the ceiling here down from $6$ to $4$.

Why it matters

$\mathrm{Adv}^{\pm}$ characterises quantum query complexity exactly, which makes it useless as an explanation: knowing $\mathrm{Q}=\Theta(\mathrm{Adv}^{\pm})$ tells you nothing you did not already have to prove. $\mathrm{Adv}$ is the version one can actually reason about, a weighting of input pairs with a combinatorial feel, and the price of that is a barrier: it never exceeds $\sqrt{\mathrm{C}^0\mathrm{C}^1}$, or even $\sqrt{\mathrm{FC}^0\mathrm{FC}^1}$ [KulkarniTal16]. This cell measures what the barrier costs.

The concrete thing that would move it: nobody has pinned $\mathrm{Adv}$ on the cheat-sheet function. It lies between $\widetilde\Omega(n^{1/4})$, from $\mathrm{fbs}\le\mathrm{Adv}^2$, and $\widetilde O(\sqrt n)$, from the barrier, against $\mathrm{Adv}^{\pm}=\widetilde\Theta(n)$ -- so the exponent that family witnesses is somewhere in $[2,4]$, and which end is right is a question about one explicit function rather than about all of them.

On partial functions the answer is as bad as it can be, and is the reason the negative-weight version was invented. For a promise problem whose $0$- and $1$-inputs are all at relative Hamming distance $\ge\epsilon$, the positive adversary cannot exceed $1/\epsilon$ -- the property-testing barrier -- so \(\mathrm{COL}_n\), where $\epsilon=1/2$, has $\mathrm{Adv}=O(1)$ against $\mathrm{Q}=\Theta(n^{1/3})$.

What is the exponent of $\deg$ versus $\mathrm{rdeg}$? total #

Gap between exponents 2 and 3. The polynomial relation itself was open from 1994 until [KKWY26] in 2026.

Fortnow's question -- is exact rational degree polynomially related to exact polynomial degree for total Boolean functions? -- was answered yes in 2026. What survives is the exponent: $\deg$ is somewhere between $\mathrm{rdeg}^2$ and $\widetilde{\mathrm{rdeg}}^3$, and $\mathrm{D}$ between $\mathrm{rdeg}^2$ and $\mathrm{rdeg}^4$.

Best known

  • \(\deg(f) = O\big(\mathrm{rdeg}(f)\deg_{\pm}(f)^2\log\mathrm{rdeg}(f)\big) = \widetilde O\big(\mathrm{rdeg}(f)^3\big)\)
    Corollary 4 of [KKWY26]: the answer to Fortnow's question, and the upper end of the surviving gap.
  • \(\mathrm{D}(f) \le 4\deg_{\pm}(f)^2\mathrm{rdeg}(f)^2 \le 16\,\mathrm{rdeg}(f)^4\)
    Theorem 4, which is what every other cell of the rdeg column now descends from. Its engine is minimum block sensitivity $\min_x\mathrm{bs}_x(f) \le 2\deg_{\pm}(f)^2$ -- a measure with no prior use in the literature, and one the zoo does not carry, since it is the min rather than the max over inputs.
  • \(\deg(f_n) = \Omega\big(\mathrm{rdeg}(f_n)^2\big)\)
    The lower end. On $\wedge_n\circ\overline{\mathrm{EH}}_n$, $\mathrm{rdeg}=\Theta(n)$ while $\deg=\Theta(n^2)$; the same function gives the best separation anyone has of any measure from $\mathrm{rdeg}$, namely $\widetilde{\deg} = \Omega(\mathrm{rdeg}^{3/2})$.
  • \(\mathrm{rdeg}(f) = \Omega(\deg(f)) \text{ for symmetric } f\)
    Exponent $1$ on symmetric functions; the pre-2026 partial results, which are still the sharpest available on their classes.
  • \(\mathrm{rdeg}(f) = \Omega(\sqrt{\deg(f)}) \text{ for unate } f \text{ and for read-once } \mathsf{AC}^0/\mathsf{TC}^0\)
  • \(\mathrm{rdeg}(f) \ge n/2 - O(\sqrt n) \text{ for almost every } f\)

Why it matters

$\mathrm{rdeg}$ is the exact-error analogue of \(\mathrm{rdeg}_{\varepsilon}(f)\), and equals exact post-selected quantum query complexity [MahadevdeWolf15]. A positive answer adds a genuine new column to the classical lattice, and gives $\mathsf{P} = (\mathsf{C}_{=}\mathsf{P}\cap\mathsf{co}\text{-}\mathsf{C}_{=}\mathsf{P})$ relative to generic oracles -- which is what made Fortnow ask. The partial-function version fails in both directions, so this really is a total-function phenomenon; see \(\mathrm{GapMaj}^{\delta}_{n}\), where $\mathrm{rdeg} = \Theta(n)$ against $\mathrm{Q} = \Theta(1)$.

Two cells are filed here. $\deg$ vs $\mathrm{rdeg}$ is Fortnow's own, and sits in $[2,3]$. $\mathrm{D}$ vs $\mathrm{rdeg}$ sits in $[2,4]$ and is harder to move: the trick that removes the $\log n$ from Theorem 8 for $\deg$ and $\mathrm{s}$ is to restrict to a maximal monomial or a maximal sensitive block, which shrinks the arity without raising $\mathrm{rdeg}$. Doing the same for $\mathrm{D}$ would need decision-tree complexity to condense onto $\mathrm{poly}(\mathrm{D})$ variables, which is open. And $\mathrm{D} = O(\deg^3)$ is still the best bound by ordinary degree, so $\mathrm{D} = O(\mathrm{rdeg}^3)$ would be at least as strong as Is …? on that route.

The rest of the column -- $\mathrm{R}$, $\mathrm{C}$, $\mathrm{bs}$, $\mathrm{Q}$, $\mathrm{Q}_E$ and the others -- is no longer a separate mystery; each is an exponent gap inherited from these two.

Is $\mathrm{R}(f)$ polynomially bounded by $\mathrm{D}^{\mathrm{prod}}(f)$ for total $f$? total #

Open, and wide open: no bound $\mathrm{R} \le g(\mathrm{D}^{\mathrm{prod}})$ is known for any function $g$ whatsoever, not merely no polynomial one. The known separation is a single small polynomial.

Yao's minimax says $\mathrm{R}_\varepsilon(f)$ is the maximum of the distributional complexity $\mathrm{D}^{\mu}_\varepsilon(f)$ over all input distributions. Restrict the maximum to distributions in which the $n$ input bits are independent, and you get $\mathrm{D}^{\mathrm{prod}}$. How much does that restriction cost?

Best known

  • \(\mathrm{D}^{\mathrm{prod}}(f) \le \mathrm{R}(f)\)
    The trivial direction, and the only one that is known.
  • \(\mathrm{D}^{\mathrm{prod}}(g_d) = O(N^{0.69789\ldots}) \text{ while } \mathrm{R}(g_d) = \Theta(N^{0.75384\ldots})\)
    The balanced NAND tree on $N = 2^d$ leaves, a ratio of exponents of $1.08$. This is the only polynomial separation known.
  • \(\mathrm{RS}(g) = \tilde\Omega\big(\mathrm{D}^{\mathrm{prod}}(g)\big)\)
    The best general handle, but it bounds $\mathrm{D}^{\mathrm{prod}}$ from above, so it is the wrong way round to close the cell -- and the NAND tree shows it is not tight.

Why it matters

The motivation is composition. $\mathrm{R}(f \circ g^n) = \tilde\Omega(\mathrm{R}(f)\, \mathrm{D}^{\mathrm{prod}}(g))$ [Sanyal24], so a positive answer here would come close to the randomized composition conjecture from a direction independent of sabotage complexity (Is … for total …?). It is also the cleanest quantitative form of a question with a long history: how much of the hardness of a Boolean function lives in correlations between its input bits, rather than in the bits themselves?

What makes the NAND tree separate is worth internalising, because it is not the usual "product distributions are too weak" hand-wave. Saks and Wigderson's classic $\Theta(\alpha^d)$ bound, $\alpha = (1+\sqrt{33})/4$, is proved against a product distribution -- but at zero error. Under a product distribution the two subtrees at a gate are independent, so an algorithm that knows $\mu$ can always recurse first on the child likelier to evaluate to $0$ instead of on a random one, and that greedy choice compounds over the depth: the recursion closes at $\sqrt{\tfrac{2}{27}(17+7\sqrt7)} = 1.62207\ldots$ per level rather than $\alpha = 1.68614\ldots$. Against a correlated distribution the choice is not available. So the separation is powered by independence itself, which suggests that any counterexample to the polynomial relation will have to be deep rather than wide -- on the depth-$2$ \(\mathrm{MP}_m\) tree the same trick buys only a logarithmic factor.

Parity decision trees vs Fourier sparsity (query log-rank) total #

Best known: $\mathrm{D}^{\oplus}(f)=O(\sqrt{\mathrm{spar}(f)}\log\mathrm{spar}(f))$.

Is $\mathrm{D}^{\oplus}(f) = \mathrm{polylog}(\mathrm{spar}(f))$?

Best known

  • \(\mathrm{D}^{\oplus}(f) = O\big(\sqrt{\mathrm{spar}(f)}\log \mathrm{spar}(f)\big)\)
  • \(\mathrm{D}^{\oplus}(f)\ge \tfrac12\log_2 \mathrm{spar}(f)\)
  • \(\text{Known for small } \mathbb{F}_2\text{-degree and for sparse symmetric } f\)

Why it matters

A positive answer implies the log-rank conjecture for XOR functions in communication complexity, via lifting.

Is $\mathrm{fbs}(f) = O(\mathrm{bs}(f)^{3/2})$? total #

Gap between exponents 3/2 and 2.

Fractional block sensitivity is the LP relaxation of block sensitivity, so $\mathrm{bs}\le\mathrm{fbs}$ always, and $\mathrm{fbs}\le\mathrm{C}\le\mathrm{s}\cdot\mathrm{bs}\le\mathrm{bs}^2$. The largest known integrality gap is $\mathrm{fbs}=\widetilde\Omega(\mathrm{bs}^{3/2})$ [GSS16]. Which end of $[3/2,\,2]$ is the truth?

Best known

  • \(\mathrm{fbs}(f) \le \mathrm{C}(f) \le \mathrm{s}(f)\,\mathrm{bs}(f) \le \mathrm{bs}(f)^2\)
  • \(\mathrm{fbs}(f_n) = \widetilde\Omega\big(\mathrm{bs}(f_n)^{3/2}\big)\)
    [APV18] simplify the construction and improve the constant, but not the exponent.

Why it matters

$\mathrm{fbs}=\Theta(\mathrm{RC})=\Theta(\mathrm{CA})$ and $\mathrm{QC}=\Theta(\sqrt{\mathrm{fbs}})$, so this is simultaneously a question about randomized certificates, the classical adversary method, and quantum certificate complexity -- all of which would collapse onto $\mathrm{bs}$ if the answer were $3/2$... or rather, would stay distinct from it.

Is $\mathrm{R}_0(f) = O(\mathrm{FC}(f)^2)$? total #

Gap between exponents 2 and 3.

Aaronson's question, in the fractional-certificate notation $\mathrm{FC}=\mathrm{fbs}$: we know $\mathrm{R}_0(f)\le\mathrm{D}(f)\le\mathrm{C}^{(1)}(f)\,\mathrm{bs}(f)=O(\mathrm{fbs}(f)^3)$, and Tribes gives a quadratic separation. Is the cubic bound tight?

Best known

  • \(\mathrm{D}(f) = O\big(\mathrm{fbs}(f)^3\big)\)
  • \(\mathrm{D}(\mathrm{TRIBES}_n) = \Theta(n) = \Theta\big(\mathrm{fbs}(\mathrm{TRIBES}_n)^2\big)\)

Why it matters

The analogous question for integral certificate complexity is settled at 2 ($\mathrm{C}=O(\mathrm{fbs}^2)$ is tight [GSS16]), so a positive answer would say the LP relaxation loses nothing beyond what rounding already costs.

How hard is it to solve $k$ copies? relation #

Direct sum settled up to constants for $\mathrm{D}$ (exactly) and $\mathrm{R}$; the sharp constants, the large-budget direct product, and the quantum case are open.

Three related questions about $f^{\otimes k}$, all raised in the papers that settled the easy parts.

  1. Worst-case direct sum, sharply. [JainKlauckSantha10] prove $\mathrm{R}_\varepsilon(f^{\otimes k}) \ge \delta^2 k\,\mathrm{R}_{\varepsilon/(1-\delta)+\delta}(f)$ for every relation $f$. The $\delta^2$ loss and the additive $\delta$ in the error are known to be necessary in the distributional setting ([Shaltiel04]) -- is either necessary in the worst case?
  2. Direct product above the threshold. [Drucker12] gives a DPT with query budget $\gamma^3\mathrm{R}(f)k/11$. What worst-case success probability is achievable with $\alpha\,\mathrm{R}(f)k$ queries for $\alpha \gg 1$? Quantumly this was settled by [BNRdW07]; classically it is open, and the interesting regime is exactly the one where the $O(\mathrm{R}(f)k\log k)$ upper bound lives.
  3. A tight quantum direct sum. Is $\mathrm{Q}(f^{\otimes k}) = \Theta(k\,\mathrm{Q}(f))$? The known bound loses a log factor and holds only for Boolean functions, because it goes through the adversary bound; [JainKlauckSantha10] ask for a direct proof, even for relations.

Best known

  • \(\mathrm{D}(f^{\otimes k}) = k\,\mathrm{D}(f) \text{ exactly, for every relation}\)
  • \(\mathrm{R}_\varepsilon(f^{\otimes k}) \ge \delta^2 k\,\mathrm{R}_{\varepsilon'}(f)\)
  • \(\bar{\mathrm{R}}_\varepsilon(f^{k}) = \Theta\big(k\,\bar{\mathrm{R}}_{\varepsilon/k}(f)\big)\)
    The sharp form, in expected cost; it implies a total $f$ with $\mathrm{R}(f^{\otimes k}) = \Theta(k\log k\,\mathrm{R}(f))$.
  • \(\text{DPT at budget } \gamma^3\mathrm{R}(f)k/11 \text{, success } < (1/2+\gamma)^k\)
  • \(\text{Quantum DPT at budget } \Omega(\mathrm{Q}(f)k)\)

Why it matters

Direct sum is composition with a trivial outer function, so it is the floor of the composition programme: anything we cannot prove here we certainly cannot prove for comp-R. It is also the source of the $\log$ factors that make $\varepsilon$-dependence and expected cost unavoidable topics -- see Direct sum and direct product.

Do the quantum sabotage variants coincide, and how do they compare with Q? total #

Open. Strong decision costs O(Q); strong index costs O(Q^{3/2}); the total weak-model bound is O(Q⁴).

Can the strong index upper bound $\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}=O(\mathrm{Q}^{3/2})$ be made linear? Are weak and strong oracle access equivalent, and are decision and index output equivalent? [CMP24] prove these equivalences classically, but leave them open quantumly. The certification collapses in [KLLPV26] apply only after the certification transform.

Best known

  • \(\mathrm{QS}_{\mathrm{str}}(f)=O(\mathrm{Q}(f)),\quad \mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f)=O(\mathrm{Q}(f)^{3/2})\)
    Lemma 1.1 and Theorem 1.2 also hold for partial functions.
  • \(\mathrm{Q}(f)=\widetilde O(\mathrm{QS}(f)^6)\)
    For every variant on total functions; equations (1)–(4).

Resolved questions

Is the maximum quantum speedup for total functions cubic or quartic? total #

Solved in October 2026: the optimal exponent is 4.

OpenAI’s construction rules out every universal upper bound $\mathrm{R}=O((1+\mathrm{Q})^\alpha)$ with $\alpha<4$. Combined with $\mathrm{R}\le\mathrm{D}=O(\mathrm{Q}^4)$, the optimal power is quartic [OpenAI26QuarticRQ, ABKRT21].

Best known

  • \(\mathrm{R}(f) = O(\mathrm{Q}(f)^4)\)
  • \(\forall\alpha<4\ \exists k:\ \mathrm{R}(F_{k,m})/(1+\mathrm{Q}(F_{k,m}))^\alpha\to\infty\)
    Theorem 1.1; fixed-k exponent 4−2/k with polylogarithmic factors.
  • \(\mathrm{R}(f_n) = \tilde\Omega(\mathrm{Q}(f_n)^3)\)
    Via $k$-Forrelation plus a cheat sheet.

Why it matters

This settles the maximal polynomial quantum speedup for total Boolean functions at the exponent level and refutes the cubic conjecture.

Is $\mathrm{RS}(f) = \Theta(\mathrm{R}(f))$ for total $f$? total #

Refuted in 2026: a logarithmic separation on total functions.

Constant-factor equality is false even on total functions. The parity-pointer family $P_q$ has $\mathrm{R}(P_q)=\Theta(m_q\log q)$ and $\mathrm{RS}(P_q)=O(m_q)$, where $m_q=q^3\log q$ and input length $N_q=\Theta(q^4\log q)$ [Meiburg26composition, Theorem 7.5].

Best known

Why it matters

This refutes one proposed route to constant-factor randomized composition. The optimal separation between sabotage and randomized complexity remains a quantitative question.

Is $\chi(f)=\Omega(\mathrm{C}(f))$ for total functions? total #

Resolved in 2026; both the Ω(C) and O(C) comparisons are refuted.

Both proposed comparisons are false on total functions. The AIK26 DNF has $\mathrm{C}(f_n)=\Theta(n^2)$ and $\mathrm{R}(f_n)=\Theta(n)$ [AIK26, Theorem 2.2]. Since $\chi=O(\mathrm{R})$, it has $\chi(f_n)=O(\sqrt{\mathrm{C}(f_n)})=o(\mathrm{C}(f_n))$, refuting the proposed universal lower bound $\chi=\Omega(\mathrm{C})$. Moreover, $\mathrm{C}\le\mathrm{bs}^2$ [Nisan91] and $\chi\ge(\mathrm{bs}+1)/2$ [Li18] give $\mathrm{C}=O(\chi^2)$, so this family has $\mathrm{C}(f_n)=\Theta(\chi(f_n)^2)$. This is a consequence of AIK26 and the standard inequalities, rather than a conflict-complexity theorem stated in that paper.

The opposite proposed bound $\chi=O(\mathrm{C})$ is also false: on $F_m=\mathrm{AND}_m\circ\mathrm{OR}_m$, $\chi(F_m)=\Omega(\mathrm{C}(F_m)^2/\log^2\mathrm{C}(F_m))$ [Meiburg26composition, Corollary 9.11].

Best known

  • \(\mathrm{C}(f_n)=\Theta(\chi(f_n)^2)\)
    Derived: C=Θ(n²), R=Θ(n), χ=O(R), and C≤bs²≤4χ².
  • \(\chi(f) \ge \tfrac12\big(\mathrm{bs}(f)+1\big)\)
    Theorem 1, replacing the $\Omega(\sqrt{\mathrm{R}(f)})$ floor that came with the measure [Sanyal18].
  • \(\chi(f) \le \mathrm{D}(f)\)
    Immediate from the definition -- the random walk stops if it reaches a last query node -- and hence $\chi \le \mathrm{C}^2$ and $\chi \le \mathrm{bs}^3$.
  • \(\chi(g) = \Omega\big(\sqrt{\mathrm{R}(g)}\big) \text{ for partial } g\)
  • \(\chi(F_m)=\Omega(\mathrm{C}(F_m)^2/\log^2\mathrm{C}(F_m))\)
    C(F_m)=m.

Why it matters

Conflict and certificate complexity are incomparable within constant factors. The C-versus-χ exponent is exactly 2, while the χ-versus-C exponent is 2 up to logarithmic factors.

Does approximate degree compose? total #

Solved in 2026: constant-factor composition for total Boolean functions.

For all total Boolean $f,g$, $\widetilde{\deg}(f\circ g)=\Theta(\widetilde{\deg}(f)\widetilde{\deg}(g))$. Pednekar and Podder prove the matching multiplicative lower bound; Sherstov supplies the upper bound. There is no logarithmic loss.

Best known

Why it matters

Approximate degree composition is the main tool for proving $\mathsf{AC}^0$ approximate-degree lower bounds and quantum query lower bounds by the dual polynomial method.

The Aaronson-Ambainis conjecture total #

Proved in November 2026 by David Turturean at Physical Superintelligence (PSI).

Every bounded degree-$d$ polynomial $p:\{-1,1\}^n\to[-1,1]$ has a variable of influence at least $c\,\mathrm{Var}(p)^{5/2}/d^6$, for an absolute $c>0$. PSI/Turturean proves the Aaronson–Ambainis conjecture [PSI26AaronsonAmbainis, Turturean26]. Cleaner expositions are available in [BDST26AA] and [HMP26AA].

Best known

Why it matters

Quantum query algorithms can be simulated with polynomially many classical queries on most uniformly random inputs. For a partial Boolean function whose domain has density $\delta$, [HMP26AA] obtains a deterministic $O(\mathrm{Q}(f)^6/(\varepsilon\delta)^2)$-query algorithm correct on at least a $1-\varepsilon$ fraction of its domain. This is an average-case guarantee.

Does randomized query complexity compose for total functions? total #

Solved up to polylogarithmic factors in n (outer input size), not R(f); some slack is necessary.

Randomized composition holds with a $\log(n+1)$ loss, even for partial Boolean functions [PednekarPodder26STOC]. The polylogarithmic loss is in the outer input size $n$, not in $\mathrm{R}(f)$; the theorem does not guarantee a $\log(\mathrm{R}(f)+1)$ loss.

Meiburg's work shows that some polylogarithmic slack is necessary, even for total functions [Meiburg26composition]. His families save a factor $\Theta(\log\mathrm{R}(g))=\Theta(\log\log L)$, where $L$ is the composed input length, ruling out constant-factor multiplicative composition.

Best known

  • \(\mathrm{R}(f\circ g^n)=\Omega\!\left(\frac{\mathrm{R}(f)\mathrm{R}(g)}{\log(n+1)}\right)\)
    The logarithm is of the outer input length n, not R(f). Both f and g may be partial Boolean functions.
  • \(\mathrm{R}(f\circ g)=\Theta(\mathrm{R}(f)\mathrm{R}(g)/\log\mathrm{R}(g))\)
    Total separating families; the saving is Θ(log log L) in their composed input length L.

Why it matters

Composition remains available for building query lower bounds with a logarithmic loss in outer input size. Meiburg's total-function counterexample shows that some polylogarithmic slack is necessary.

Does randomized composition survive a $\log n$ loss? partial #

Proved in the STOC 2027 submission: logarithmic loss in outer input size.

Conjecture 2 of [BenDavidBlais20composition] is proved for all possibly partial Boolean $f,g$ [PednekarPodder26STOC]. The lower bound loses $\log(n+1)$, where $n$ is the outer input length. The known counterexamples to constant-factor composition are consistent with this theorem.

Best known

  • \(\mathrm{R}(f\circ g^n)=\Omega\!\left(\frac{\mathrm{R}(f)\mathrm{R}(g)}{\log(n+1)}\right)\)
    Here n is the outer input length, not R(f). Both f and g may be partial Boolean functions.

Why it matters

The theorem restores randomized composition as a lower-bound tool up to an input-size logarithm. The loss is not guaranteed to be polylogarithmic in R(f).

Is $\mathrm{noisyR}(f) = \Omega(\mathrm{R}(f)/\log n)$? partial #

Proved in the STOC 2027 submission for partial Boolean functions.

Conjecture 7 of [BenDavidBlais20composition] is proved: every nonconstant partial Boolean $f$ on $n$ bits satisfies $\mathrm{R}(f)\le C\log(n+1)\mathrm{noisyR}(f)$ [PednekarPodder26STOC, Theorem 31]. It implies Does randomized composition survive a … loss? via the optimal outer composition theorem. Constant-factor equality still fails on total functions [Meiburg26composition].

Best known

  • \(\mathrm{R}(f)\le C\log(n+1)\mathrm{noisyR}(f)\)
    Input-size logarithm; no general replacement by log R(f).
  • \(\frac{\mathrm{R}(W_q)}{\mathrm{noisyR}(W_q)}=\Omega\!\left(\frac{(\log N_q)^{1/4}}{\log\log\log N_q}\right)\)
    Theorem 4.1; W_q is total.

Why it matters

The theorem uses Boolean output. It remains false for relations: \(\mathrm{AGREE}_n\) has constant noisy complexity and randomized complexity Θ(√n).

Is $\mathrm{R}^{*}(f) = \Theta(\mathrm{R}(f))$? total #

Refuted in 2026: the maximal logarithmic gap is attained.

Constant-factor equality is false on total functions. [Meiburg26composition, Theorem 10.7] gives a total family $H_q$ with $\mathrm{R}^{*}(H_q)/\mathrm{R}(H_q)=\Theta(\log\mathrm{R}(H_q))$, attaining the general upper bound. The composition rate is larger than the one-level randomized complexity on this family.

Best known