.png){kind=icon}
返回
Average-Case Deterministic Query Complexity of Boolean Functions with Fixed Weight
.png){kind=icon}
PRE
AI
DOI：10.1007/978-981-95-0215-8_15.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
我们研究了布尔函数在均匀输入分布下的平均情况确定性查询复杂度，记为D-ave(f)，即计算布尔函数f所需的最小零误差决策树平均深度。这一度量已在多个领域得到应用，但其理解仍有限。我们研究了固定权重的布尔函数，其中权重定义为输出为1的输入数量。我们证明了对于每个n变量的布尔函数f，有D-ave(f) ≤ max{log wt(f)/log n + O(log log wt(f)/log n), O(1)}，其中wt(f)表示权重。对于任意4 log n = m(n) ≤ 2(n-1)，我们证明了对于几乎所有固定权重wt(f) = m(n)的n变量布尔函数，上界在加性对数项内是紧的。Hastad的切换引理或Rossman的切换引理[Comput. Complexity Conf. 137, 2019]分别意味着对于宽度为w的CNF/DNF公式，有D-ave(f) ≤ n(1 - 1/O(w))或D-ave(f) ≤ n(1 - 1/O(log s))。我们证明了对于任何w ≥ 2 log n，存在一个宽度为w且大小为[2(w)/w]的DNF公式，使得D-ave(f) = n(1 - log n/circle plus(w))。
Keyword:
average-case query complexity
decision tree
weight
switching lemma
criticality
期刊
C
IF:
0
论文数:
24
被引数:
0
机构
引用论文
.png){kind=icon}
分享收藏
查看更多内容