Q The Query Complexity Zoo
Champion

Ben-David–Kothari championship function

Simultaneously $\mathrm{C}=\Omega(n^2)$, $\mathrm{R}=O(n\log n)$ and $\mathrm{Q}=\widetilde O(\sqrt n)$.

total separating-total arity: $\Theta(n^3\log n)$ bits

Description

There are $2n$ countries with $n$ athletes each. Each country-pair has a race-results list of length $n$, with spectators encoded as $\bot$. An athlete supplies a proposal card containing cumulative counts of spectators ahead in its races. The function accepts iff an athlete has a correctly formatted card, beats every other athlete in all its races, and loses to fewer than $n$ spectators in total. Only that athlete’s card and relevant race prefixes must be well formed. Section 2 of [BenDavidKothari26] specifies the bit encoding; malformed irrelevant data does not create a promise.

Formal definition

An input contains race lists $X^{\{c,d\}}$ of length $n$, and cards $Y^{(c,b)}$ of length $2n-1$, in the binary encoding of [BenDavidKothari26, Section 2]. Write the races involving $c$ in their fixed order as $r_1,\ldots,r_{2n-1}$, and the card entries as $y_1,\ldots,y_{2n-1}$; put $y_0=0$ and $q_t=y_t-y_{t-1}$. Athlete $(c,b)$ is valid precisely when $0\le y_1\le\cdots\le y_{2n-1}<n$ and, for every $t$, $X^{r_t}_{q_t+1}=(c,b)$ and $X^{r_t}_j=\bot$ for $1\le j\le q_t$. $$f(X,Y)=1\quad\Longleftrightarrow\quad\exists(c,b)\in[2n]\times[n] \text{ satisfying these checks}. $$ Only these checked fields need valid encodings; no promise is imposed on other fields.

Measure values

MeasureValueNotes
\(\mathrm{C}(f)\) Certificate complexity \(\Omega(n^2)\) Theorem 1 and Lemma 4. BenDavidKothari26
\(\mathrm{C}^0(f)\) 0-certificate complexity \(\Omega(n^2)\) All race lists are spectators and proposal cards are zero. BenDavidKothari26
\(\mathrm{C}^1(f)\) 1-certificate complexity \(O(n\log n)\) Lemma 2. BenDavidKothari26
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(O(n\log n)\) Lemma 3; the logarithm pays for binary labels. BenDavidKothari26
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\tilde O(\sqrt n)\) Lemma 5; the final verification costs O(√n log² n), with polylogs also in the sink-finding subroutine. BenDavidKothari26
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(\Theta(n\log n)\) v3 concurrent-work discussion extends the championship algorithm to exact queries and gives a matching restriction. AIK26
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\Theta(n\log n)\) Same discussion; zero-error lower bound from a description-bit restriction. AIK26

Separations its values prove — computed, not recorded

Read straight off the table above by comparing two values: no relation record states these, and where one does and says more, the record wins and the pair is not listed here. 4 in total.

Cited as a witness by