An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean function
An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean function
复制标题
有界度布尔函数中相关变量数量的渐近紧界
DOI：
10.1007/s00493-019-4136-7
复制
发表时间：
2020
期刊：
影响因子：
1.1
通讯作者：
Saks, Michael
中科院分区：
文献类型：
--
作者：
Chiarelli, John;Hatami, Pooya;Saks, Michael
我们证明了存在一个常数tc≤6.614，使得每一个最多d次的布尔函数（作为一个多项式）都是aC·2d-军政府，即它最多依赖于c·2d变量。这改进了Nisan和Szegedy的2d-1上界[计算复杂性4(1994)]。c·2的边界紧绷于常量c，因为深度的一次读取决策树依赖于所有的2d- 1变量。我们通过构造一个带有3·2d-1- 2相关变量的次函数来稍微改进这个下界。Shinkar和Tal独立地观察到了类似的结构。
We prove that there is a constantC≤ 6.614 such that every Boolean function of degree at mostd(as a polynomial over ℝ) is aC·2d-junta, i.e., it depends on at mostC·2dvariables. This improves thed·2d-1upper bound of Nisan and Szegedy [Computational Complexity 4 (1994)].The bound ofC·2dis tight up to the constantC, since a read-once decision tree of depthddepends on all 2d- 1 variables. We slightly improve this lower bound by constructing, for each positive integerd, a function of degreedwith 3·2d-1- 2 relevant variables. A similar construction was independently observed by Shinkar and Tal.
影响因子：
1
作者：
Pooya Hatami;R. Kulkarni;D. Pankratov
通讯作者：
D. Pankratov
DOI：
10.1145/2422436.2422485
发表时间：
2013
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Avishay Tal
通讯作者：
Avishay Tal
切片上的布尔常度函数是 juntas
影响因子：
0.8
作者：
Yuval Filmus;F. Ihringer
通讯作者：
F. Ihringer