1 Search Results for "Mehta, Jenish C."

Tree Tribes and Lower Bounds for Switching Lemmas

Authors: Jenish C. Mehta

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

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.

Cite as

Jenish C. Mehta. Tree Tribes and Lower Bounds for Switching Lemmas. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 70:1-70:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

  author =	{Mehta, Jenish C.},
  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 =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.70},
  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}
  • Refine by Author
  • 1 Mehta, Jenish C.

  • Refine by Classification
  • 1 Theory of computation → Computational complexity and cryptography
  • 1 Theory of computation → Oracles and decision trees

  • Refine by Keyword
  • 1 Resilience
  • 1 Switching lemmas
  • 1 Tree Tribes
  • 1 decision tree
  • 1 lower bounds

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail