  We give efficient deterministic algorithms for converting randomized query
algorithms into deterministic ones. We first give an algorithm that takes as
input a randomized $q$-query algorithm $R$ with description length $N$ and a
parameter $\varepsilon$, runs in time $\mathrm{poly}(N) \cdot
2^{O(q/\varepsilon)}$, and returns a deterministic $O(q/\varepsilon)$-query
algorithm $D$ that $\varepsilon$-approximates the acceptance probabilities of
$R$. These parameters are near-optimal: runtime $N + 2^{\Omega(q/\varepsilon)}$
and query complexity $\Omega(q/\varepsilon)$ are necessary.
  Next, we give algorithms for instance-optimal and online versions of the
problem:
  $\circ$ Instance optimal: Construct a deterministic $q^\star_R$-query
algorithm $D$, where $q^\star_R$ is minimum query complexity of any
deterministic algorithm that $\varepsilon$-approximates $R$.
  $\circ$ Online: Deterministically approximate the acceptance probability of
$R$ for a specific input $\underline{x}$ in time
$\mathrm{poly}(N,q,1/\varepsilon)$, without constructing $D$ in its entirety.
  Applying the techniques we develop for these extensions, we constructivize
classic results that relate the deterministic, randomized, and quantum query
complexities of boolean functions (Nisan, STOC 1989; Beals et al., FOCS 1998).
This has direct implications for the Turing machine model of computation:
sublinear-time algorithms for total decision problems can be efficiently
derandomized and dequantized with a subexponential-time preprocessing step.
