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.2018.70
URN: urn:nbn:de:0030-drops-96524
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9652/
Mehta, Jenish C.
Tree Tribes and Lower Bounds for Switching Lemmas
Abstract
Let f be a Boolean function on n variables, rho a random p-restriction that independently keeps each variable unset (or free) with probability p and otherwise uniformly sets it to 0 or 1, and DT_{depth}(f) denote the depth of the smallest depth decision tree for f. Let R_d(f|rho) be the resilience of f to rho for depth d, defined as R_d(f|rho)=Pr_{rho < - rho}[DT_{depth}(f|rho)>= d]. If d >> pn, all functions have resilience close to 0 since less than d variables would remain unset with high probability. For d << pn, most functions f on n variables have resilience close to 1, and some functions, like AND and OR, have resilience close to 0. Håstad's Switching Lemma states that for t-DNFs, the resilience R_d(f|rho) is upper bounded by (5pt)^d, and from known upper bounds on the size of constant depth circuits computing the parity function, it follows that there exist t-DNFs whose resilience is close to the bound obtained by Håstad. However, the exact bounds for such maximally resilient DNFs or their structure is unclear, and moreover, the argument is non-constructive.
In this work, we give an explicit construction of functions called Tree Tribes parameterized by an integer t and denoted Xi_t (on n variables), such that R_d(Xi_t|rho)<=(4p2^t)^d, and more importantly, the resilience is also lower bounded by the same quantity up to constants, R_d(Xi_t|rho)>=(c_0 p2^t)^d, for 0 <= p <= c_p 2^-t and 0 <= d <= c_d * (log n)/(2^t * t log t) (where c_0,c_p,c_d are universal constants). As a result, for sufficiently large n and small d, this gives a hierarchy of functions with strictly increasing resilience, and covers the entire region between the two extremes where functions have resilience (close to) 0 or 1.
BibTeX - Entry
@InProceedings{mehta:LIPIcs:2018:9652,
author = {Jenish C. Mehta},
title = {{Tree Tribes and Lower Bounds for Switching Lemmas}},
booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
pages = {70:1--70:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-086-6},
ISSN = {1868-8969},
year = {2018},
volume = {117},
editor = {Igor Potapov and Paul Spirakis and James Worrell},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9652},
URN = {urn:nbn:de:0030-drops-96524},
doi = {10.4230/LIPIcs.MFCS.2018.70},
annote = {Keywords: Tree Tribes, Resilience, Switching lemmas, lower bounds, decision tree}
}
|
Keywords: |
|
Tree Tribes, Resilience, Switching lemmas, lower bounds, decision tree |
|
Collection: |
|
43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
27.08.2018 |
