2026-08-03T22:42:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18568 2024-03-06T11:02:08Z ddc:004 open_access

Query Complexity of Search Problems Chattopadhyay, Arkadev Dahiya, Yogesh Mahajan, Meena Decision trees Search problems Pseudo-determinism Randomness 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 provide the following improvements upon the known relationship between pseudo-deterministic and deterministic query complexity for total search problems: - We show that deterministic query complexity 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). - 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(Ω̃(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(Ω(n)) separation for the ApproxHamWt relation. The previous best known separation for any relation was exp(Ω(n^{1/2})). We also separate pseudo-determinism from randomness in And and (And,Or) 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 TFNP^{dt}, we prove that either the monotone block-sensitivity or the anti-monotone block sensitivity is Ω(n^{1/3}); Goldwasser et al. showed an Ω(n^{1/2}) bound for general block-sensitivity. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arkadev Chattopadhyay and Yogesh Dahiya and Meena Mahajan 2023 Is Part Of LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2023.34 urn:nbn:de:0030-drops-185689 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.34 eng https://creativecommons.org/licenses/by/4.0/legalcode