Tree tribes and lower bounds for switching lemmas

2017/02/28 by Mehta, Jenish C.
#Computational Complexity (cs.CC) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1703.00043

Abstract

We show tight upper and lower bounds for switching lemmas obtained by the action of random p-restrictions on boolean functions that can be expressed as decision trees in which every vertex is at a distance of at most t from some leaf, also called t-clipped decision trees. More specifically, we show the following: \bullet If a boolean function f can be expressed as a t-clipped decision tree, then under the action of a random p-restriction ρ, the probability that the smallest depth decision tree for f|_ρ has depth greater than d is upper bounded by (4p2^t)^d. \bullet For every t, there exists a function g_t that can be expressed as a t-clipped decision tree, such that under the action of a random p-restriction ρ, the probability that the smallest depth decision tree for g_t|_ρ has depth greater than d is lower bounded by (c₀p2^t)^d, for 0≤ p≤ c_p2^-t and 0≤ d≤ c_d\fraclog n2^tlog t, where c₀,c_p,c_d are universal constants.

Related

• Every decision tree has an influential variable
• Superpolynomial Lower Bounds for Decision Tree Learning and Testing
• Notes on switching lemmas
• On Learning and Testing Decision Tree
• Lower bounds for uniform read-once threshold formulae in the randomized decision tree model