@inproceedings{a1a7661229dd4edcb10d97af4c23b8ee,
title = "On the sensitivity conjecture for disjunctive normal forms",
abstract = "The sensitivity conjecture of Nisan and Szegedy [CC'94] asks whether for any Boolean function f, the maximum sensitivity s(f), is polynomially related to its block sensitivity bs(f), and hence to other major complexity measures. Despite major advances in the analysis of Boolean functions over the last decade, the problem remains widely open. In this paper, we consider a restriction on the class of Boolean functions through a model of computation (DNF), and refer to the functions adhering to this restriction as admitting the Normalized Block property. We prove that for any function f admitting the Normalized Block property, bs(f) ≤ 4s(f)2. We note that (almost) all the functions mentioned in literature that achieve a quadratic separation between sensitivity and block sensitivity admit the Normalized Block property. Recently, Gopalan et al. [ITCS'16] showed that every Boolean function f is uniquely specified by its values on a Hamming ball of radius at most 2s(f). We extend this result and also construct examples of Boolean functions which provide the matching lower bounds.",
keywords = "Block sensitivity, Boolean function, DNF, Sensitivity",
author = "Karthik, {C. S.} and S{\'e}bastien Tavenas",
note = "Funding Information: This work was partially supported by Irit Dinur's ERC-StG grant number 239985. Some parts of this work were done while interning at Microsoft Research, India. This work was supported by ANR project CompA (project number: ANR-13-BS02-0001-01). We would like to thank Satya Lokam for discussions and encouraging us to work on the sensitivity conjecture. In particular, Karthik would like to thank him for the internship at Microsoft Research. We would like to thank Avishay Tal for pointing out Corollary 21. We would like to thank Roei Tell for motivation and discussions. We would like to thank Andris Ambainis and Kri{\v s}jānis Prūsis for pointing out an error in a first version of Theorem 16 and for highlighting the relation between this theorem and the result in [2]. Finally, we would like to thank the anonymous reviewers for helping us improve the presentation of the paper. Publisher Copyright: {\textcopyright} Karthik C. S. and S{\'e}bastien Tavenas.; 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016 ; Conference date: 13-12-2016 Through 15-12-2016",
year = "2016",
month = dec,
day = "1",
doi = "https://doi.org/10.4230/LIPIcs.FSTTCS.2016.15",
language = "American English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
pages = "15.1--15.15",
editor = "Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen",
booktitle = "36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016",
address = "Germany",
}