Scholarlink

We investigate the randomized decision tree complexity of a specific class of read-once threshold formulae. A read-once threshold formula can be defined by a rooted tree, every internal node of which is labeled by a threshold function \(T^{n}_{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 and all leaves at the same level. 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.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Lower Bounds for Uniform Read-Once Threshold Formulae in the Randomized Decision Tree Model

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Nikos Leonardos

摘要

We investigate the randomized decision tree complexity of a specific class of read-once threshold formulae. A read-once threshold formula can be defined by a rooted tree, every internal node of which is labeled by a threshold function \(T^{n}_{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 and all leaves at the same level. 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.