Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR16-084 | 23rd May 2016 18:51

Low-Sensitivity Functions from Unambiguous Certificates

RSS-Feed




TR16-084
Authors: Shalev Ben-David
Publication: 27th May 2016 09:30
Downloads: 1826
Keywords: 


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.1 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 ($UC_{\min}$). Finally, we show that $UC_{\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).



ISSN 1433-8092 | Imprint