$k$-distinctness
$\mathrm{Q} = \Theta(n^{3/4 - 1/(4(2^k-1))})$, settled in 2026 after fourteen years; the approximate degree is still open.
total quantum arity: $n$ symbols over an alphabet $[q]$ (element queries); $k$ is a constant
Description
Decide whether some symbol occurs at least $k$ times in the list. $k = 2$ is the complement of \(\mathrm{ED}_n\). On the indicator matrix of the list it is $\mathrm{OR}_q \circ \mathrm{THR}^k_n$ restricted to Hamming weight $\le n$.
Formal definition
$$\mathrm{DIST}^k(x) \;=\; \bigvee_{i_1 < \cdots < i_k}\ [\,x_{i_1} = \cdots = x_{i_k}\,].$$
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity | \(\Theta\!\big(n^{3/4 - 1/(4(2^k-1))}\big)\)· | For constant $k$ and alphabet size $q = \Omega(n^2)$. Upper: [Belovs12kdist], a learning graph of cost $O(n^{1 - 2^{k-2}/(2^k-1)})$ -- the same exponent, $2/3$ at $k=2$ and $5/7$ at $k=3$. Lower: [Belovs26kdist, Thm. 1.1], by a compressed-oracle framework that subsumes the polynomial method; the same paper recovers $\Omega(n^{2/3})$ for element distinctness (its Thm. 6.10). Marked medium confidence only because the lower bound is a 2026 preprint; the exponent matches the 2012 algorithm exactly. Earlier: $O(n^{k/(k+1)})$ by quantum walk [Ambainis07]. Belovs12kdist Belovs26kdist |
| \(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree | \(\tilde\Omega\!\big(n^{3/4-1/(4k)}\big),\ O\!\big(n^{3/4-1/(4(2^k-1))}\big)\)· | Open, so recorded as a range. Lower: [MTZ20, Thm. 17 / Cor. 18] for $2 \le k \le \log^4 q$ -- the first proof that $4$-distinctness is strictly harder than element distinctness. Upper: [Sherstov21, Thm. 1.1], degree $O(\sqrt n \cdot \min\{n,q\}^{1/2 - 1/(4(1-2^{-k}))})$, and $\tilde O(n^{3/4})$ for all $k \le \mathrm{polylog}(n)$ [MTZ20, Thm. 2]. The 2026 quantum lower bound does not transfer: [BT22] ask exactly how fast $\widetilde{\deg}$ approaches $n^{3/4}$ and it is still open. MTZ20 Sherstov21 BT22 |
| \(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity | \(\Theta(n)\) | Read everything; the lower bound is the usual hybrid argument in the element-query model. |
| \(\mathrm{D}(f)\) Deterministic query complexity | \(n\) | Element-query model. |
| \(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity | \(\Theta(n)\)· | Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \bar{\mathrm{R}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here. |
| \(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity | \(\Theta(n)\)· | Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}_{0}(f) \le \mathrm{D}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here. |
| \(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity | \(\Theta(n)\)· | Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here. |
| \(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound | \(\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. |
| \(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm | \(\Theta\!\big(n^{3/4 - 1/(4(2^k-1))}\big)\)· | $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta\!\big(n^{3/4 - 1/(4(2^k-1))}\big)$ here. |
| \(\mathrm{MAdv}(f)\) Multiplicative adversary | \(\Theta\!\big(n^{3/4 - 1/(4(2^k-1))}\big)\)· | $\mathrm{MAdv}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{MAdv}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta\!\big(n^{3/4 - 1/(4(2^k-1))}\big)$ here. |
| \(\mathrm{C}^1(f)\) 1-certificate complexity | \(k\) putative | Exhibit the $k$ positions carrying a repeated symbol. Counting a query as one symbol read, as throughout this entry and \(\mathrm{ED}_n\). |
| \(\mathrm{C}^0(f)\) 0-certificate complexity | \(n\) putative | Take a $0$-input in which one symbol occurs exactly $k-1$ times and everything else is distinct. Leave any other position unread and it could be overwritten with that symbol, completing a $k$-fold repeat; so the certificate must read all $n$ symbols. |
| \(\mathrm{C}(f)\) Certificate complexity | \(n\) | $\mathrm{C} = \max(\mathrm{C}^0,\mathrm{C}^1) = \max(n,k) = n$. |
| \(\mathrm{C}_{\min}(f)\) Minimum certificate complexity | \(k\) putative | The cheapest certificate anywhere is a $k$-fold repeat; every $0$-input costs $n$. |
| \(\mathrm{s}^1(f)\) 1-sensitivity | \(k\) putative | At a $1$-input every sensitive position must destroy every $k$-fold repeat, so it lies in all of them; a $1$-input with a single $k$-group therefore has sensitivity exactly $k$, and no $1$-input has more. The same argument caps $\mathrm{bs}^1$. |
| \(\mathrm{bs}^1(f)\) 1-block sensitivity | \(k\) putative | Disjoint sensitive blocks at a $1$-input must each meet every $k$-group, and a $k$-group has only $k$ positions, so $\mathrm{bs}^1 \le k$; the single-$k$-group input attains it. |
| \(\mathrm{s}^0(f)\) 0-sensitivity | \(\Theta(n)\) putative | On the $0$-input of the $\mathrm{C}^0$ note, overwriting any of the $n-k+1$ positions outside the $(k-1)$-group with that group's symbol flips the answer. So the sensitivity is wildly asymmetric: $\Theta(n)$ on $0$-inputs against $k$ on $1$-inputs. |
| \(\mathrm{s}(f)\) Sensitivity | \(\Theta(n)\) | $\mathrm{s} = \max(\mathrm{s}^0,\mathrm{s}^1) = \Theta(n)$. |
| \(\mathrm{bs}^0(f)\) 0-block sensitivity | \(\Theta(n)\) | The $n-k+1$ singleton blocks of the $\mathrm{s}^0$ note are disjoint, and $\mathrm{bs}^0 \le n$. |
| \(\mathrm{bs}(f)\) Block sensitivity | \(\Theta(n)\) | $\mathrm{s} \le \mathrm{bs} \le n$. |
| \(\mathrm{fbs}(f)\) Fractional block sensitivity | \(\Theta(n)\) | Between $\mathrm{bs} = \Theta(n)$ and $n$. |
| \(\mathrm{FC}(f)\) Fractional certificate complexity | \(\Theta(n)\) | Equal to $\mathrm{fbs}$ by LP duality. |
| \(\mathrm{RC}(f)\) Randomized certificate complexity | \(\Theta(n)\) | $\mathrm{RC} = \Theta(\mathrm{FC}) = \Theta(n)$. |
| \(\mathrm{EC}(f)\) Expectational certificate complexity | \(\Theta(n)\) | Squeezed between $\mathrm{fbs} = \Theta(n)$ and $\mathrm{C} = n$. |
| \(\mathrm{UC}(f)\) Unambiguous certificate complexity | \(n\) | Squeezed between $\mathrm{C} = n$ and $\mathrm{D} = n$. |
| \(\mathrm{SP}(f)\) Subcube partition complexity | \(n\) | Squeezed between $\mathrm{C} = n$ and $\mathrm{D} = n$. |
| \(\mathrm{CA}(f)\) Classical adversary bound | \(\Theta(n)\) | $\mathrm{CA} = \Theta(\mathrm{fbs}) = \Theta(n)$; also capped by $\mathrm{R} = \Theta(n)$. The classical adversary is tight here even though the positive quantum adversary is not. |
| \(\mathrm{Adv}(f)\) Positive-weights adversary bound | \(O(\sqrt n)\) putative | The certificate barrier $\mathrm{Adv}(f) \le \sqrt{\mathrm{C}^0 \mathrm{C}^1} = \sqrt{nk} = O(\sqrt n)$ for constant $k$ -- so the positive-weights adversary cannot even reach the $\Omega(n^{2/3})$ of \(\mathrm{ED}_n\), let alone the true exponent. This is why every lower bound in the row above goes through the polynomial method or a compressed oracle. |
| \(\mathrm{QC}(f)\) Quantum certificate complexity | \(\Theta(\sqrt n)\) | $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{FC}(f)})$, and $\mathrm{FC} = \Theta(n)$ here. Note this is below $\mathrm{Q}$, as it must be -- quantum certificate complexity is not a lower bound on $\mathrm{Q}$ in any useful sense here. |
| \(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity | \(n\) | Every symbol is relevant, so a non-adaptive algorithm reads all of them; $\mathrm{D} = n$ anyway. |
| \(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity | \(\Theta(n)\) | Sandwiched between $\mathrm{R} = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}} = n$. |
| \(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity | \(\Theta(n)\) | By Yao, $\max_\mu \mathrm{D}^\mu_\varepsilon = \mathrm{R}_\varepsilon = \Theta(n)$. |
| \(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) | \(\Theta(n)\) | Squeezed between $\mathrm{fbs} = \Theta(n)$ and $\mathrm{C} = n$; equivalently $\Theta(\mathrm{CA})$, which is also $\Theta(n)$ here. CGLMSG23 |
| \(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity | \(\Theta(n)\) | All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23 |
| \(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity | \(\Theta(n)\) | All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23 |
| \(\mathrm{CG}(f)\) Certificate game complexity (private coin) | \(\Theta(n)\) | For constant $k$ the correct sandwich $\mathrm{R}_0 \le \mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$ [CGLMSG23] closes: $\mathrm{R}_0 = \Theta(n)$ and $\mathrm{C}^0\mathrm{C}^1 = n \cdot k = \Theta(n)$. The value happens to agree with the one previously recorded, but the old justification -- $\mathrm{CG} \le \mathrm{D}$ -- is false in general: $\mathrm{CG}$ can exceed the arity, as it does for $\oplus_n$. For growing $k$ the ceiling degrades to $O(nk)$. CGLMSG23 |
| \(\chi(f)\) Conflict complexity | \(\Theta(n)\) | Sandwiched: $\mathrm{s}(f) \le \chi(g) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(n)$ here. |
| \(\bar{\chi}(f)\) Max-conflict complexity | \(\Theta(n)\) | Sandwiched: $\mathrm{s}(f) \le \bar{\chi}(g) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(n)$ here. |
| \(\mathrm{LR}(f)\) Linearised randomized complexity | \(\Theta(n)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{LR}(f) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(n)$ here. |
| \(\mathrm{R}^{*}(f)\) Asymptotic composition rate | \(\Theta(n)\) | Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}^{*}(f) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(n)$ here. |
| \(\mathrm{prt}_{\varepsilon}(f)\) Partition bound | \(\Theta(n)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(n)$ here. |
| \(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound | \(\Theta(n)\)· | Sandwiched: $\mathrm{s}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. As on \(\mathrm{SURJ}_{N,R}\), the lower end rests on the observation that the [JainKlauck10] arguments survive the relaxation of the completeness constraint; the upper end is unconditional. JainKlauck10 |
| \(\mathrm{N}_{p}(f)\) Noisy decision tree complexity | \(\tilde\Theta(n)\) | Between $\mathrm{R} = \Theta(n)$ and $O(\mathrm{R}\log \mathrm{R}) = O(n\log n)$ (\(\mathrm{N}_{p}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)). |
| \(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity | \(\tilde\Theta\!\big(n^{3/4 - 1/(4(2^k-1))}\big)\) | Between $\mathrm{Q}$ and $O(\mathrm{Q}\log \mathrm{Q})$ (\(\mathrm{Q}^{\mathrm{rob}}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q} = \Theta(n^{3/4-1/(4(2^k-1))})$ by the row above. Even the fourteen-year-old exponent is noise-robust up to a log. |
| \(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity | \(\Omega\!\big(n^{3/4 - 1/(4(2^k-1))}\big),\ O(n)\) | Only the generic $\mathrm{Q}_{\varepsilon} \le \mathrm{Q}_0 \le \mathrm{D}$. Zero error is not obviously free here, unlike on the search problems in this file: a $k$-collision found is a $k$-element certificate, but certifying that no symbol repeats $k$ times costs $\mathrm{C}^0 = n$, so a zero-error algorithm must be right on $0$-inputs with certainty. |
| \(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity | \(\Omega\!\big(n^{3/4 - 1/(4(2^k-1))}\big),\ O(n)\) | Same window as $\mathrm{Q}_0$, which it contains: $\mathrm{Q}_0 \le \mathrm{Q}_{\mathrm{E}} \le \mathrm{D} = n$. The usual $\mathrm{Q}_{\mathrm{E}} \ge \deg/2$ route is unavailable because $\deg(\mathrm{DIST}^k)$ is itself not recorded. |
| \(\mathrm{RS}(f)\) Sabotage complexity | \(\Theta(n)\) putative | Upper: $\mathrm{RS}\le\mathrm{R}=\Theta(n)$ [BenDavidKothari18]. Lower: take the input consisting of $n/(k-1)$ values each repeated exactly $k-1$ times -- a $0$-input with no room to spare. Starring any single symbol sabotages it: left alone its group stays at $k-1$ copies, changed to another group it makes that group $k$. So all $n$ symbols are sabotage positions over one base input, and finding the $\ast$ is finding a marked symbol among $n$. BenDavidKothari18 |
| \(\mathrm{noisyR}(f)\) Noisy randomized query complexity | \(\Theta(n)\) | $\mathrm{noisyR}\le\mathrm{R}$ [BenDavidBlais20composition], and $\mathrm{R}=\Theta(n)=\Theta(\text{arity})$ forces equality [CKMPSS23]. CKMPSS23 BenDavidBlais20composition |
| \(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity | \(\Theta(n)\)· putative | Upper: $\mathrm{D}^{\mathrm{prod}}\le\mathrm{R}=\Theta(n)$. Lower: fix (point masses are product measures) $n/2$ symbols as $m=n/(2(k-1))$ groups of $k-1$ copies of distinct values $a_1,\dots,a_m$; let free symbol $j$ independently be $a_{j\bmod m}$ with probability $1/M$ and otherwise a private value $b_j$ used nowhere else, where $M=n/2$. No accidental collision is possible, so the instance is a $1$-input exactly when some free symbol picks its $a$, an $\mathrm{OR}$ of $M$ independent events of probability $1/M$. Any tree that leaves a constant fraction of the free symbols unread errs with constant probability, so $\mathrm{D}^\mu=\Omega(n)$. Alphabet size $m+M=O(n)$ suffices. |
| \(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree | \(\tilde\Omega\!\big(n^{3/4-1/(4k)}\big),\ O(n)\) | $\widetilde{\deg}_\varepsilon\le\mathrm{cjdeg}_\varepsilon\le\mathrm{R}_\varepsilon$ (\(\mathrm{cjdeg}_{\varepsilon}(f)\) vs \(\widetilde{\deg}_{\varepsilon}(f)\), \(\mathrm{cjdeg}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)), taking the lower end from the recorded approximate degree and the upper end from $\mathrm{R}=\Theta(n)$. |
| \(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree | \(O\!\big(n^{3/4 - 1/(4(2^k-1))}\big)\) | $\mathrm{rdeg}_\varepsilon\le\widetilde{\deg}_\varepsilon$ (\(\mathrm{rdeg}_{\varepsilon}(f)\) vs \(\widetilde{\deg}_{\varepsilon}(f)\)), and the recorded approximate degree upper bound is the tight quantum one. No lower bound is recorded: the sign degree of $k$-distinctness is not known here, so the $\mathrm{sdeg}\le\mathrm{rdeg}_{1/3}$ route gives nothing. |
| \(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity | \(O\!\big(n^{3/4 - 1/(4(2^k-1))}\big)\) | $\mathrm{PostQ}_\varepsilon=\Theta(\mathrm{rdeg}_\varepsilon)$ [MahadevdeWolf15]; see \(\mathrm{rdeg}_{\varepsilon}(f)\). Equivalently, post-selection is at least as strong as the plain quantum algorithm, whose cost is $\Theta(n^{3/4-1/(4(2^k-1))})$. MahadevdeWolf15 |
| \(\mathrm{DTsize}(f)\) Decision tree size | \(2^{\Theta(n\log n)}\)· putative | For $q\ge n$ (so that the all-distinct inputs exist) every $0$-input needs all $n$ symbols read, since $\mathrm{C}^0=n$, so distinct $0$-inputs end at distinct leaves; the $n!$ orderings of $n$ fixed distinct values already give $\mathrm{DTsize}\ge n!=2^{\Theta(n\log n)}$. The ceiling is $q^n$, which matches for $q=\mathrm{poly}(n)$. |
Separations it witnesses
-
A family of total functions with $\mathrm{R} = \Theta(\mathrm{Q}^{1/(3/4 - 1/(4(2^k-1)))})$, approaching $\mathrm{R} = \mathrm{Q}^{4/3}$ as $k \to \infty$ -- over a large alphabet, so not a Boolean-input separation.
Notes
Open, per [Belovs26kdist, ยง7]: the approximate degree; alphabets smaller than $n^2$; non-constant $k$; and removing the "$\Omega(n)$ singletons" assumption on the input distribution. The framework is explicitly incomparable to the Liu-Zhandry compressed-oracle results, which fix a uniformly random input.