Lower bounds for uniform read-once threshold formulae in the randomized decision tree model

2022/03/31 by Nikos Leonardos, Leonardos, Nikos
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Machine Learning and Algorithms #Privacy-Preserving Technologies in Data

paper · pdf · doi:10.48550/arxiv.2203.17168

openalex publication_date 2022/03/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We investigate the randomized decision tree complexity of a specific class of read-once threshold functions. A read-once threshold formula can be defined by a rooted tree, every internal node of which is labeled by a threshold function T_kⁿ (with output 1 only when at least k out of n input bits are 1) and each leaf by a distinct variable. Such a tree defines a Boolean function in a natural way. We focus on the randomized decision tree complexity of such functions, when the underlying tree is a uniform tree with all its internal nodes labeled by the same threshold function. We prove lower bounds of the form c(k,n)^d, where d is the depth of the tree. We also treat trees with alternating levels of AND and OR gates separately and show asymptotically optimal bounds, extending the known bounds for the binary case.

Related

• Every decision tree has an influential variable
• The relation between tree size complexity and probability for Boolean functions generated by uniform random trees
• When Is Amplification Necessary for Composition in Randomized Query\n Complexity?
• Improved bounds for the randomized decision tree complexity of recursive majority
• Tree tribes and lower bounds for switching lemmas