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.