Low-Sensitivity Functions from Unambiguous Certificates

Abstract

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 ($U{C}_{min}$). We also show that $U{C}_{min}$ is lower-bounded by fractional block sensitivity, which means we cannot use these techniques to get a super-quadratic separation between $bs(f)$ and $s(f)$. We also provide a quadratic separation between the tree-sensitivity and decision tree complexity of Boolean functions, disproving a conjecture of Gopalan, Servedio, Tal, and Wigderson (CCC 2016). 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 Göös (FOCS 2015). As a consequence, we obtain an improved $\Omega ({\log }^{1.22}n)$ lower-bound on the co-nondeterministic communication complexity of the Clique vs. Independent Set problem.

25 pages. This version expands the results and adds Pooya Hatami and Avishay Tal as authors

References in corpus (6)

• Nearly optimal separations between communication (or query) complexity and partitions
• A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity
• Lattice Variant of the Sensitivity Conjecture
• An $O(n^{0.4732})$ upper bound on the complexity of the GKS communication game
• Separating decision tree complexity from subcube partition complexity
• Sensitivity versus Certificate Complexity of Boolean Functions