Randomized certificate complexity
Cost of a randomized verifier that must detect, with constant probability, that the input has been changed to flip f.
Definition
$\mathrm{RC}_x(f)$ is the minimum $T$ such that there is a randomized algorithm making $T$ queries which accepts $x$ with probability $\ge 1-\varepsilon$, and rejects with probability $\ge 1/2$ any $y$ with $f(y)\ne f(x)$. $\mathrm{RC}(f) = \max_x \mathrm{RC}_x(f)$. Aaronson showed $\mathrm{RC} = \Theta(\mathrm{fbs})$.
Basic facts
- $\mathrm{RC}(f) = \Theta(\mathrm{QC}(f)^2)$ where $\mathrm{QC}$ is quantum certificate complexity.
- $\mathrm{RC}(f) = O(\widetilde{\deg}(f)^2)$ [Kulkarni-Tal].
- $\mathrm{RC}(f) \le \mathrm{C}(f)$ and $\mathrm{RC}(f) \ge \mathrm{bs}(f)$.
Equivalent / near-equivalent measures
- \(\mathrm{fbs}(f)\) $\mathrm{RC}(f) = \Theta(\mathrm{fbs}(f))$ Aaronson08 KulkarniTal16
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{RC}(f)\). “\(\mathrm{RC}(f)\) in terms of it” is the pair with \(\mathrm{RC}(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.
The 5 above are this entry’s hand-picked neighbours; the other 88 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| OR total | \(\Theta(n)\) | |
| AND total | \(\Theta(n)\) | |
| PARITY total | \(\lceil n/2\rceil\) putative | A verifier must catch the flip of any single bit with probability $\ge 1/2$, so $\Pr[i \in S]\ge 1/2$ for every $i$ and $\mathbb{E}|S| \ge n/2$; a uniformly random half attains it. Note $\mathrm{RC} \ne \mathrm{fbs} = n$ here -- the constant in $\mathrm{RC}=\Theta(\mathrm{fbs})$ is real. |
| MAJORITY total | \(\Theta(n)\) | $\mathrm{RC}=\Theta(\mathrm{fbs})=\Theta(n)$. Aaronson08 |
| Threshold total | \(\Theta(\max\{k,\;n-k+1\})\) | Sandwiched: $\mathrm{FC}(f) \le \mathrm{RC}(f) \le \mathrm{fbs}(f)$, with both ends $\max\{k,\;n-k+1\}$ here. |
| Symmetric functions (general) total | \(\Theta(n)\) | $\mathrm{RC}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$, and $\mathrm{fbs}(f) = \Theta(n)$ here. Aaronson08 |
| EXACT-HALF total | \(\Theta(n)\) | Sandwiched: $\mathrm{fbs}(f) \le \mathrm{RC}(f) \le \mathrm{D}(f)$, with both ends $n$ here. |
| ODD-MAX-BIT total | \(\Theta(n)\) | $\mathrm{RC}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$, and $\mathrm{fbs}(f) = \lfloor n/2\rfloor+1$ here. Aaronson08 |
| ADDRESS / multiplexer total | \(\Theta(k+1)\) | Sandwiched: $\mathrm{fbs}(f) \le \mathrm{RC}(f) \le \mathrm{D}(f)$, with both ends $k+1$ here. |
| Binary tree navigation total | \(\Theta(k)\) | $\mathrm{RC}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$, and $\mathrm{fbs}(f) = k$ here. Aaronson08 |
| TRIBES total | \(\Theta(n/\log n)\) | $\mathrm{RC}=\Theta(\mathrm{fbs})$. Aaronson08 |
| AND-OR tree (depth 2) total | \(\Theta(n)\) | |
| NAND tree (balanced AND-OR formula) total | \(\Theta(\sqrt{N})\) | |
| Recursive MAJORITY-of-3 total | \(\Theta(2^d)\) | Sandwiched: $\mathrm{fbs}(f) \le \mathrm{RC}(f) \le \mathrm{C}(f)$, with both ends $2^d$ here. |
| Kushilevitz's function (iterated) total | \(\Theta(N)\) | |
| Rubinstein's function total | \(\Theta(N)\) | Sandwiched: $\mathrm{fbs}(f) \le \mathrm{RC}(f) \le \mathrm{C}(f)$, with both ends $\Theta(N)$ here. |
| Ambainis-Sun function total | \(\Theta(N)\) | Sandwiched: $\mathrm{fbs} \le \mathrm{RC} \le \mathrm{D}$, with both ends $\Theta(N)$. |
| AND composed with NOT-EXACT-HALF total | \(\Theta(n^2)\) | Sandwiched: $\mathrm{fbs}(f) \le \mathrm{RC}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n^2)$ here. |
| Meiburg's tournament-subcube function total | \(\Theta(14011^{\,d})\) putative | $\mathrm{RC} = \Theta(\mathrm{fbs})$ for every total $f$ (\(\mathrm{RC}(f)\) vs \(\mathrm{fbs}(f)\)), and \(\mathrm{fbs}(f)\) is pinned at $14011^{\,d}$. |
| Pointer functions total | \(\widetilde\Theta(\sqrt n)\) | Squeeze: $\mathrm{RC}=\Theta(\mathrm{fbs})$. |
| Cheat-sheet functions total | \(\widetilde\Theta(\sqrt n)\) | Squeeze: $\mathrm{RC}=\Theta(\mathrm{fbs})$, now pinned on both sides. |
| Low-sensitivity function from unambiguous certificates total | \(\widetilde\Omega(n)\) | Squeeze: $\mathrm{RC}=\Theta(\mathrm{fbs})$. |
| Unambiguous-DNF / Alon-Saks-Seymour function total | \(\widetilde\Omega(n^{4/3})\) | Squeeze: $\mathrm{RC}=\Theta(\mathrm{fbs})$. |
| Gilmer-Saks-Srinivasan functions total | \(\Theta(n)\) | Squeeze: $\mathrm{RC}=\Theta(\mathrm{fbs})$. |
| Random-indicator gadget total | \(\Theta(n)\) | Squeeze: $\mathrm{RC}=\Theta(\mathrm{fbs})$. |
| Goos-Pitassi-Watson partition-number function total | \(\widetilde\Omega(\sqrt n)\) | Squeeze: $\mathrm{RC}=\Theta(\mathrm{fbs})$. |
| Goos-Jayram-Pitassi-Watson function total | \(\widetilde\Omega(n^{1/3})\) | Squeeze: $\mathrm{RC}=\Theta(\mathrm{fbs})$. |
| Ambainis' exact-quantum function total | \(3^d\) | Squeeze: $\mathrm{fbs}\le\mathrm{RC}\le\mathrm{D}$. |
| FORRELATION partial | \(O(1)\) | $\mathrm{RC} = \Theta(\mathrm{fbs}) = O(1)$. |
| k-FORRELATION partial | \(O(k^2)\) | $\mathrm{RC} = \Theta(\mathrm{fbs}) = O(k^2)$. |
| Simon's problem partial | \(\Theta(1)\) putative | $\mathrm{RC} = \Theta(\mathrm{fbs}) = \Theta(1)$: to reject one fixed input of the other kind it is enough to query a random point of a block on which the two differ, which succeeds with constant probability. Rejecting them one at a time is free; $\mathrm{R} = \Theta(2^{n/2})$ is the price of rejecting all of them at once. |
| Deutsch-Jozsa partial | \(\Theta(1)\) | Sandwiched: $\mathrm{RC} \le \mathrm{R} = O(1)$, and every measure here is at least $1$. |
| Bernstein-Vazirani partial | \(\Theta(1)\) putative | One uniformly random query already distinguishes the codeword $x$ from any fixed other codeword with probability $1/2$, which is all $\mathrm{RC}$ asks; and $\mathrm{RC} = \Theta(\mathrm{fbs}) = \Theta(1)$. The contrast with $\mathrm{R} = \Theta(n)$ is the point: rejecting one alternative at a time is easy, rejecting all $2^n-1$ of them at once is not. |
| Unique search partial | \(\Theta(n)\) putative | At $0^n$ a certificate scheme must find the planted $1$ with constant probability against an adversary free to plant it anywhere, which costs $\Omega(n)$ weight; and $\mathrm{RC} \le \mathrm{C} = n$. |
| Two-or-none search partial | \(\Theta(n)\) putative | Squeezed between $\mathrm{fbs} = n/2$ and $\mathrm{C} = n-1$. |
| Marked bit partial | \(\Theta(1)\) | $\mathrm{RC} = \Theta(\mathrm{fbs}) = \Theta(1)$, and also $\mathrm{RC} \le \mathrm{C} = 1$. |
| Dense marked bit partial | \(\Theta(1)\) | $\mathrm{RC} = \Theta(\mathrm{fbs}) = \Theta(1)$, and also $\mathrm{RC} \le \mathrm{C} = 1$. |
| Gap-Majority partial | \(\Theta(\min(n, 1/\delta))\) | $\mathrm{RC} = \Theta(\mathrm{fbs})$. |
| Gap-Majority at constant gap partial | \(\Theta(1)\) | $\mathrm{RC} = \Theta(\mathrm{fbs})$. |
| Parity-labelled FIND-1 partial | \(1\) putative | The one-bit certificate is already a verifier that needs no coins: query the fixed position $i \in \mathrm{supp}(x)$, accept iff it returns $1$. Every $y$ of the opposite value has $y_i = 0$, so it is rejected with certainty. |
| Approximate index partial | \(\Theta(1)\) | $\mathrm{RC} = \Theta(\mathrm{fbs}) = \Theta(1)$; also $\mathrm{RC} \le \mathrm{C} = \Theta(1)$. |
| Collision problem partial | \(\Theta(1)\) putative | $\mathrm{RC} = \Theta(\mathrm{fbs}) = \Theta(1)$: rejecting one fixed input of the other type needs only a random query into a block where the two differ. Against $\mathrm{R} = \Theta(\sqrt n)$ and $\mathrm{Q} = \Theta(n^{1/3})$, this is why no certificate-style bound can prove anything about the collision problem. |
| Element distinctness total | \(\Theta(n)\) | $\mathrm{RC} = \Theta(\mathrm{fbs}) = \Theta(n)$; also squeezed between $\mathrm{fbs}$ and $\mathrm{R} = \Theta(n)$. |
| Ambainis-Belovs function partial | \(O(n)\) | $\mathrm{RC} = \Theta(\mathrm{fbs}) = O(n)$. Aaronson06 |
| Surjectivity total | \(\Theta(n)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{RC}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. The lower end of this sandwich is itself the zoo's own argument (see the note on $\mathrm{s}$), so this value inherits its status. |
| $k$-distinctness total | \(\Theta(n)\) | $\mathrm{RC} = \Theta(\mathrm{FC}) = \Theta(n)$. |
| Triangle finding total | \(\Theta(m^2) = \Theta(n)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{RC}(f) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(m^2) = \Theta(n)$ here. |
| Ordered search partial | \(2\) putative | Query positions $k$ and $k+1$ and reject unless the answers are $0$ and $1$: any promise input with a different boundary fails one of the two checks with certainty. $\mathrm{RC} \ge \mathrm{bs} = 2$, and Aaronson's $\mathrm{RC} = \Theta(\mathrm{fbs})$ agrees. |
| Inner product mod 2 total | \(\Theta(n)\) | Sandwiched: $\mathrm{fbs}(f) \le \mathrm{RC}(f) \le \mathrm{D}(f)$, with both ends $n$ here. |
| Minsky-Papert one-in-a-box total | \(\Theta(m^2) = \Theta(N^{2/3})\) | $\mathrm{RC} = \Theta(\mathrm{fbs})$. |
| Sink of a tournament total | \(\Theta(m) = \Theta(\sqrt N)\) | Sandwiched: $\mathrm{bs}(f) \le \mathrm{RC}(f) \le \mathrm{D}(f)$, with both ends $\Theta(m) = \Theta(\sqrt N)$ here. |
| Scorpion graphs total | \(\Theta(m)\) | Sandwiched: $\mathrm{fbs}(f) \le \mathrm{RC}(f) \le \mathrm{D}(f)$, with both ends $\Theta(m)$ here. |
| Graph connectivity total | \(\Theta(m^2) = \Theta(N)\) | $\mathrm{RC} = \Theta(\mathrm{fbs})$, and $\mathrm{fbs} = \Theta(m^2)$ here. |