2026-07-21T14:14:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8186 2024-03-06T10:39:19Z ddc:004 open_access

Low-Sensitivity Functions from Unambiguous Certificates Ben-David, Shalev Hatami, Pooya Tal, Avishay Boolean functions decision tree complexity query complexity sensitivity conjecture We provide new query complexity separations against sensitivity for total Boolean functions: a power 3 separation between deterministic (and even randomized or quantum) query complexity and sensitivity, and a power 2.22 separation between certificate complexity and sensitivity. We get these separations by using a new connection between sensitivity and a seemingly unrelated measure called one-sided unambiguous certificate complexity. We also show that one-sided unambiguous certificate complexity is lower-bounded by fractional block sensitivity, which means we cannot use these techniques to get a super-quadratic separation between block sensitivity and sensitivity. Along the way, we give a power 1.22 separation between certificate complexity and one-sided unambiguous certificate complexity, improving the power 1.128 separation due to Goos [FOCS 2015]. As a consequence, we obtain an improved lower-bound on the co-nondeterministic communication complexity of the Clique vs. Independent Set problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shalev Ben-David and Pooya Hatami and Avishay Tal 2017 Is Part Of LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2017.28 urn:nbn:de:0030-drops-81869 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.28 eng https://creativecommons.org/licenses/by/3.0/legalcode