Low-Sensitivity Functions from Unambiguous Certificates

Shalev Ben-David, Pooya Hatami, Avishay Tal

We provide new query complexity separations against sensitivity for total Boolean functions: a power $3$ separation between deterministic (and even randomized or quantum) query com…