Alladi Ramakrishnan Hall

Pseudo-Deterministic Query Algorithms: Complexity Separations and Improved Bounds

Yogesh Dahiya

IMSc

We study pseudo-deterministic query algorithms. A probabilistic algorithm is considered pseudo-deterministic if, for any input, there exists a canonical value that is output with a high probability. 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 Approximate Hamming Weight relation. The previous best known separation for any relation was $\exp(\Omega(n^{1/2}))$. Additionally, we also separate pseudo-determinism from randomness in AND and AND OR decision trees, and determinism from pseudo-determinism in Parity decision trees. Finally, 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 TFNP-dt, we prove that either the monotone block-sensitivity or the anti-monotone block sensitivity is $\Omega(n^{1/3})$; Goldwasser et al. showed an $\Omega(n^{1/2})$ bound for general block-sensitivity.

Joint work with Arkadev Chattopadhyay and Meena Mahajan.
To appear in MFCS 2023.