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.MFCS.2016.16
URN: urn:nbn:de:0030-drops-64317
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6431/
Bafna, Mitali ;
Lokam, Satyanarayana V. ;
Tavenas, Sébastien ;
Velingker, Ameya
On the Sensitivity Conjecture for Read-k Formulas
Abstract
Various combinatorial/algebraic parameters are used to quantify the complexity of a Boolean function. Among them, sensitivity is one of the simplest and block sensitivity is one of the most useful. Nisan (1989) and Nisan and Szegedy (1991) showed that block sensitivity and several other parameters, such as certificate complexity, decision tree depth, and degree over R, are all polynomially related to one another. The sensitivity conjecture states that there is also a polynomial relationship between sensitivity and block sensitivity, thus supplying the "missing link".
Since its introduction in 1991, the sensitivity conjecture has remained a challenging open question in the study of Boolean functions. One natural approach is to prove it for special classes of functions. For instance, the conjecture is known to be true for monotone functions, symmetric functions, and
functions describing graph properties.
In this paper, we consider the conjecture for Boolean functions computable by read-k formulas. A read-k formula is a tree in which each variable appears at most k times among the leaves and has Boolean gates at its internal nodes. We show that the sensitivity conjecture holds for read-once formulas with gates computing symmetric functions. We next consider regular formulas with OR and AND gates. A formula is regular if it is a leveled tree with all gates at a given level having the same fan-in and computing the same function. We prove the sensitivity conjecture for constant depth regular read-k formulas for constant k.
BibTeX - Entry
@InProceedings{bafna_et_al:LIPIcs:2016:6431,
author = {Mitali Bafna and Satyanarayana V. Lokam and S{\'e}bastien Tavenas and Ameya Velingker},
title = {{On the Sensitivity Conjecture for Read-k Formulas}},
booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
pages = {16:1--16:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-016-3},
ISSN = {1868-8969},
year = {2016},
volume = {58},
editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6431},
URN = {urn:nbn:de:0030-drops-64317},
doi = {10.4230/LIPIcs.MFCS.2016.16},
annote = {Keywords: sensitivity conjecture, read-k formulas, analysis of Boolean functions}
}
|
Keywords: |
|
sensitivity conjecture, read-k formulas, analysis of Boolean functions |
|
Collection: |
|
41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
19.08.2016 |
