License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2016.15
URN: urn:nbn:de:0030-drops-68504
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6850/
S., Karthik C. ;
Tavenas, Sébastien
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) <= 4 * s(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 2 * s(f). We extend this result and also construct examples of Boolean functions which provide the matching lower bounds.
BibTeX - Entry
@InProceedings{s_et_al:LIPIcs:2016:6850,
author = {Karthik C. S. and S{\'e}bastien Tavenas},
title = {{On the Sensitivity Conjecture for Disjunctive Normal Forms}},
booktitle = {36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
pages = {15:1--15:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-027-9},
ISSN = {1868-8969},
year = {2016},
volume = {65},
editor = {Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6850},
URN = {urn:nbn:de:0030-drops-68504},
doi = {10.4230/LIPIcs.FSTTCS.2016.15},
annote = {Keywords: Boolean function, Sensitivity, Block sensitivity, DNF}
}
|
Keywords: |
|
Boolean function, Sensitivity, Block sensitivity, DNF |
|
Collection: |
|
36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
10.12.2016 |
