论文标题
随机决策树模型中均匀读取阈值公式的均匀读取阈值公式
Lower bounds for uniform read-once threshold formulae in the randomized decision tree model
论文作者
论文摘要
我们研究了特定类别的读取阈值函数的随机决策树复杂性。可以通过扎根树来定义一个读取阈值公式，其每个内部节点均由阈值函数$ t_k^n $标记（仅当$ n $输入位的至少$ k $均为1）和每个叶子的独特变量。这样的树自然而然地定义了布尔功能。当基础树是一棵均匀的树时，我们的所有内部节点都以相同的阈值函数标记，我们将重点关注此类功能的随机决策树复杂性。我们证明了表格$ c（k，n）^d $的下限，其中$ d $是树的深度。我们还分别用交替的水平和 /或门处理树木，并显示渐近的最佳界限，从而扩大了二进制案例的已知边界。
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^n$ (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.
