Q The Query Complexity Zoo
\(\mathrm{Adv}^{\pm}(f)\)

General (negative-weights) adversary bound

The tight SDP characterisation of bounded-error quantum query complexity.

also written: negative adversary, ADV^pm, gamma_2 with error

Definition

Same SDP as $\mathrm{Adv}$ but the adversary matrix $\Gamma$ may have negative entries. Reichardt proved $\mathrm{Q}(f)=\Theta(\mathrm{Adv}^{\pm}(f))$, so this is not merely a lower bound but a characterisation.

Basic facts

  • Perfect composition: $\mathrm{Adv}^{\pm}(f\circ g)=\Theta(\mathrm{Adv}^{\pm}(f)\mathrm{Adv}^{\pm}(g))$, which is how one proves $\mathrm{Q}$ composes.
  • Being an SDP, $\mathrm{Adv}^{\pm}$ is computable in time exponential in $n$ but polynomial in the domain size.

Equivalent / near-equivalent measures

Relations to other measures

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

Other measure \(\mathrm{Adv}^{\pm}(f)\) in terms of it It in terms of \(\mathrm{Adv}^{\pm}(f)\)
\(\mathrm{Adv}(f)\) Positive-weights adversary bound total2,6 partial∞ relation∞ open pair → total1,1 partial1,1 relation1,1 derived open pair →
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity total1,1 partial1,1 relation1,1 derived open pair → total1,1 partial1,1 relation1,1 open pair →
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm total1,1 partial1,? derived open pair → total1,1 partial1,1 open pair →
\(\mathrm{MAdv}(f)\) Multiplicative adversary total1,1 partial1,1 derived open pair → total1,1 partial1,1 open pair →
\(\lambda(f)\) Spectral sensitivity total3,6 partial∞ derived open pair → total1,1 partial1,1 derived open pair →

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

Known values

FunctionValueNotes
OR total \(\Theta(\sqrt{n})\) Sandwiched: $\lambda(f) \le \mathrm{Adv}^{\pm}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with $\lambda(f) = \sqrt{n}$ and $\mathrm{Q}_{\varepsilon}(f) = \Theta(\sqrt{n})$ here.
AND total \(\Theta(\sqrt{n})\) Sandwiched: $\lambda(f) \le \mathrm{Adv}^{\pm}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with $\lambda(f) = \sqrt{n}$ and $\mathrm{Q}_{\varepsilon}(f) = \Theta(\sqrt{n})$ here.
PARITY total \(\Theta(\lceil n/2 \rceil)\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \lceil n/2 \rceil$ here.
MAJORITY total \(\Theta(n)\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(n)$ here.
Threshold total \(\Theta\!\big(\sqrt{k(n-k+1)}\big)\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta\!\big(\sqrt{k(n-k+1)}\big)$ here.
Symmetric functions (general) total \(\Theta\!\big(\sqrt{n(n-\Gamma(f))}\big)\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta\!\big(\sqrt{n(n-\Gamma(f))}\big)$ here.
EXACT-HALF total \(\Theta(n)\) Sandwiched: $\lambda(f) \le \mathrm{Adv}^{\pm}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with both ends $\Theta(n)$ here.
ODD-MAX-BIT total \(\Theta(\sqrt n)\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(\sqrt n)$ here.
ADDRESS / multiplexer total \(\Theta(k)\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q} = \Theta(k)$ here.
Binary tree navigation total \(\Theta(k)\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(k)$ here.
TRIBES total \(\Theta(\sqrt n)\) Sandwiched: $\lambda(f) \le \mathrm{Adv}^{\pm}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with both ends $\Theta(\sqrt n)$ here.
AND-OR tree (depth 2) total \(\Theta(n) = \Theta(\sqrt N)\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(n) = \Theta(\sqrt N)$ here.
NAND tree (balanced AND-OR formula) total \(\Theta(\sqrt{N})\) Sandwiched: $\lambda(f) \le \mathrm{Adv}^{\pm}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with $\lambda(f) = \sqrt{N}$ and $\mathrm{Q}_{\varepsilon}(f) = \Theta(\sqrt{N})$ here.
Recursive MAJORITY-of-3 total \(\Theta(2^d)\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(2^d)$ here.
Kushilevitz's function (iterated) total \(\Omega(\sqrt N),\ O(N)\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), so this inherits the \(\mathrm{Q}_{\varepsilon}(f)\) window verbatim; pinning it is the open question about the base function's adversary bound.
Rubinstein's function total \(\Theta(\sqrt N) = \Theta(n)\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q} = \Theta(\sqrt N)$ here.
Ambainis-Sun function total \(\Omega(\sqrt N),\ O(N^{3/4})\) putative $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), so this inherits the \(\mathrm{Q}_{\varepsilon}(f)\) window verbatim.
AND composed with NOT-EXACT-HALF total \(\Theta(n^{3/2}) = \Theta(N^{3/4})\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q} = \Theta(n^{3/2})$ here.
Meiburg's tournament-subcube function total \(\Omega(118.3^{\,d})\) putative $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}_{\varepsilon})$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q} \ge 118.3^{\,d}$ here.
Pointer functions total \(\widetilde O(n^{1/4})\) Variant $f_{2m,m}$: $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$, so the adversary bound is as small as the algorithm. Reichardt11
Cheat-sheet functions total \(\widetilde\Theta(n)\) Squeeze: $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$. The adversary bound therefore does see the hardness that $\widetilde{\deg}$ misses -- this is the standard reading of the $\mathrm{Q}$-vs-$\widetilde{\deg}$ separation. Reichardt11
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n^3)\) The general adversary bound characterises bounded-error quantum query complexity, $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$, so it inherits the recorded $\mathrm{Q}$. Reichardt11
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Omega(n^{2/3})\) Squeeze: $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$. Reichardt11
Gilmer-Saks-Srinivasan functions total \(\Omega(\sqrt n)\) Squeeze: $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$. Reichardt11
Goos-Pitassi-Watson partition-number function total \(\widetilde\Omega(n^{1/4})\) Squeeze: $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$. Reichardt11
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Omega(n^{1/6})\) Squeeze: $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$. Reichardt11
Ambainis' exact-quantum function total \(\Theta(2.1213^d)\) Squeeze: $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$. Ambainis' lower bound for this family is in fact an adversary bound, so this line is where the recorded $\mathrm{Q}$ comes from. Reichardt11
FORRELATION partial \(\Theta(1)\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = 1$ here.
k-FORRELATION partial \(\Theta(\lceil k/2\rceil)\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \lceil k/2\rceil$ here.
Simon's problem partial \(\Theta(n)\) $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}) = \Theta(n)$. Against $\mathrm{Adv} = O(1)$ this is the largest known gap between the positive and the general adversary.
Deutsch-Jozsa partial \(1\) Sandwiched: $\mathrm{Q} \le \mathrm{Adv}^{\pm} \le \mathrm{Q}_E$, with both ends $1$.
Bernstein-Vazirani partial \(1\) Sandwiched: $\mathrm{Q} \le \mathrm{Adv}^{\pm} \le \mathrm{Q}_E$, with both ends $1$.
Two-or-none search partial \(\Theta(\sqrt n)\) $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$.
Marked bit partial \(\Theta(\sqrt n)\) $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$. The gap to $\mathrm{Adv} = \Theta(1)$ is as wide as the function is hard.
Dense marked bit partial \(\Theta(1)\) $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}) = \Theta(1)$.
Unstructured search (relation) relation \(\Theta(\sqrt n)\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(\sqrt n)$ here.
FIND-1 under a density promise relation \(\Theta(1)\) Sandwiched between $\mathrm{Q} = \Theta(1)$ and $\mathrm{R} = O(1)$.
Approximate Hamming weight relation \(\Theta(1)\) Sandwiched between $\mathrm{Q} = \Theta(1)$ and $\mathrm{R} = \Theta(1)$.
SearchCNF relation \(\Theta(1)\) $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}) = \Theta(1)$.
Gap-Majority partial \(\Theta(\min(n, 1/\delta))\) $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$.
Gap-Majority at constant gap partial \(\Theta(1)\) $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$.
Parity-labelled FIND-1 partial \(\Theta(1)\) $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}) = \Theta(1)$.
Approximate index partial \(O(\sqrt{k\log k})\) $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$, hence at most $O(\sqrt{k\log k})$.
Collision problem partial \(\Theta(n^{1/3})\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(n^{1/3})$ here.
Element distinctness total \(\Theta(n^{2/3})\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(n^{2/3})$ here.
Ambainis-Belovs function partial \(\Omega(n^{1/3})\) $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$, and here the negative-weight adversary is literally how the lower bound is obtained -- an explicit adversary matrix built from the shifted matchings. AmbainisBelovs23
Ben-David-Kundu total search problems relation \(\widetilde\Omega(\sqrt n)\) $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$, so the negative-weight adversary is $\widetilde\Omega(\sqrt n)$ here while $\widetilde{\deg} = O(\log^7 n)$: for search problems the adversary bound is exponentially stronger than the polynomial method.
Yamakawa-Zhandry problem relation \(\mathrm{poly}(n)\) $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}) = \mathrm{poly}(n)$; the interest is entirely that this is exponentially below $\mathrm{R}$.
Surjectivity total \(\tilde\Theta(n)\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \tilde\Theta(n)$ here.
$k$-distinctness total \(\Theta\!\big(n^{3/4 - 1/(4(2^k-1))}\big)\)· $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta\!\big(n^{3/4 - 1/(4(2^k-1))}\big)$ here.
Triangle finding total \(\Omega(m),\ O(m^{5/4})\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), so the general adversary inherits the open window verbatim: computing $\mathrm{Adv}^{\pm}(\mathrm{TRI}_m)$ is the triangle problem.
Recursive Fourier sampling partial \(\Theta(2^{\ell})\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(2^{\ell})$ here for the base function $g = g_{\mathrm{mod}3}$.
Welded trees relation \(\Theta(n)\)· $\mathrm{Adv}^{\pm}$ characterises $\mathrm{Q}$ up to constants (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q} = \Theta(n)$ here. Medium confidence on two counts: the characterisation is proved for state conversion rather than for search relations in general, and the $\Omega(n)$ side of $\mathrm{Q}$ is itself folklore.
Local search on the hypercube relation \(\Theta(2^{n/3}n^{1/6})\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(2^{n/3}n^{1/6})$ here.
Local search on the grid relation \(\Theta(k^{d/3})\ (d \ge 6)\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)). In the open dimension $d = 4$ the general adversary inherits the window $[\Omega(k^{6/5}), O(k^{4/3})]$ verbatim.
Fourier fishing relation \(\Theta(1)\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = 1$ here.
Ordered search partial \(\tfrac1\pi\ln n + O(1)\) The same ceiling holds for negative weights, so improving $0.221\log_2 n$ needs a genuinely different technique. Unlike the positive-weight $\mathrm{Adv}$ above, this survives the passage to the Boolean decision version, since $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$ and $\mathrm{Q}$ is $\widetilde\Theta(\log n)$ either way. ChildsLee08
Tseitin search on an expander relation \(O(\sqrt n)\) $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$ is settled in the relation setting (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}=O(\sqrt n)$ by Grover search over the $\Theta(n)$ vertices, one of which is always violated. No lower bound is recorded because none is recorded for $\mathrm{Q}$.
Inner product mod 2 total \(\Theta(n)\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(n)$ here.
Minsky-Papert one-in-a-box total \(\Theta(m^{3/2}) = \Theta(\sqrt N)\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(m^{3/2}) = \Theta(\sqrt N)$ here.
Sink of a tournament total \(\Omega(\sqrt m),\ O(m)\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}$ is open between $\Omega(\sqrt m)$ and $O(m)$ here. Pinning this SDP down would settle $\mathrm{Q}(\mathrm{SINK})$.
Scorpion graphs total \(\Omega(\sqrt m),\ O(m)\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}$ is only known to lie between $\Omega(\sqrt m)$ (from $\widetilde{\deg}$) and $O(m)$ here.
Graph connectivity total \(\Theta(m^{3/2}) = \Theta(N^{3/4})\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(m^{3/2}) = \Theta(N^{3/4})$ here.