We relate various complexity measures like sensitivity, block sensitivity, certificate complexity for multi-output functions to the query complexities of such functions. Using these relations, we show that the deterministic query complexity of total search problems is at most the third power of its pseudo-deterministic query complexity. Previously, a fourth-power relation was shown by Goldreich, Goldwasser and Ron (ITCS'13). Furthermore, we improve the known separation between pseudo-deterministic and randomized decision tree size for total search problems in two ways: (1)~we exhibit an $\exp(\widetilde{\Omega}(n^{1/4}))$ separation for the $\SearchCNF$ relation for random $k$-CNFs. This seems to be the first exponential lower bound on the pseudo-deterministic size complexity of $\SearchCNF$ associated with random $k$-CNFs. (2)~we exhibit an $\exp(\Omega(n))$ separation for the $\ApproxHW$ relation. The previous best known separation for any relation was $\exp(\Omega(n^{1/2}))$. We also separate pseudo-determinism from randomness in $\AND$ and $\CONJ$ decision trees, and determinism from pseudo-determinism in $\Parity$ decision trees. For a hypercube colouring problem, that was introduced by Goldwasswer, Impagliazzo, Pitassi and Santhanam (CCC'21) to analyze the pseudo-deterministic complexity of a complete problem in $\TFNPdt$, we prove that either the \emph{monotone} block-sensitivity or the \emph{anti-monotone} block sensitivity is $\Omega(n^{1/3})$; Goldwasser et al. showed an $\Omega(n^{1/2})$ bound for \emph{general} block-sensitivity.

Polished previous version.
Improved the known separation between pseudo-deterministic and randomized decision tree size for total search problems in two ways: (1) we exhibit an $\exp(\widetilde{\Omega}(n^{1/4}))$ separation for the $\SearchCNF$ relation for random $k$-CNFs. This seems to be the first exponential lower bound on the pseudo-deterministic size complexity of $\SearchCNF$ associated with random $k$-CNFs. (2)~we exhibit an $\exp(\Omega(n))$ separation for the $\ApproxHW$ relation. The previous best known separation for any relation was $\exp(\Omega(n^{1/2}))$.

We relate various complexity measures like sensitivity, block sensitivity, certificate complexity for multi-output functions to the query complexities of such functions. Using these relations, we improve upon the known relationship between pseudo-deterministic query complexity and deterministic query complexity for total search problems: We show that pseudo-deterministic query complexity is at most the third power of its deterministic query complexity. (Previously a fourth-power relation was shown by Goldreich,Goldwasser,Ron (ITCS13).) We then obtain a significantly simpler and self-contained proof of a separation between pseudodeterminism and randomized query complexity recently proved by Goldwasser, Impagliazzo, Pitassi, Santhanam (CCC 2021). We also separate pseudodeterminism from randomness in AND decision trees, and determinism from pseudodeterminism in PARITY decision trees. For a hypercube colouring problem closely related to the pseudodeterministic complexity of a complete problem in $TFNP^{dt}$, we prove that either the monotone block-sensitivity or the anti-monotone block sensitivity is $\Omega(n^{1/3})$; previously an $\Omega(n^{1/2})$ bound was known but for general block-sensitivity.