Q The Query Complexity Zoo

Cheat sheets: turning partial separations into total ones

The Aaronson-Ben-David-Kothari trick that converts a partial-function separation into a total-function separation with the same exponents.

Most extremal examples in query complexity are naturally partial (\(\mathrm{forr}\), \(\mathrm{forr}_k\)). The cheat sheet construction [ABK16] turns a partial function $f$ into a total function $f_{\mathrm{CS}}$ while roughly preserving the measures of interest.

Sketch: $f_{\mathrm{CS}}$ takes $\ell$ independent inputs $x^1,\dots,x^\ell$ to $f$ together with $2^\ell$ "cells", each holding a claimed certificate. The string $f(x^1)\cdots f(x^\ell)$ addresses one cell; the function outputs $1$ iff that cell contains valid certificates for all $\ell$ answers. Off-promise inputs are handled because the certificate check is a total condition.

Effects:

  • $\mathrm{Q}(f_{\mathrm{CS}}) = \tilde\Theta(\mathrm{Q}(f))$ and similarly for the other "algorithmic" measures.
  • $\mathrm{R}(f_{\mathrm{CS}}) = \tilde\Theta(\mathrm{R}(f))$.
  • Certificate-based measures ($\mathrm{C}$, $\mathrm{bs}$, $\mathrm{s}$) become small, which is exactly what one wants for separations from those measures.

This is how the cubic $\mathrm{R}$-vs-$\mathrm{Q}$ separation and the quadratic $\mathrm{Q}$-vs-$\deg$ separation are obtained for total functions from Forrelation-type partial functions.