论文标题
布尔功能的输入数量与其他复杂性度量之间的关系
Relationships between the number of inputs and other complexity measures of Boolean functions
论文作者
论文摘要
我们在最近的Chiarelli，Hatami和Saks的论文中概括并扩展了思想，以证明有关布尔功能的相关变量数量的新界限，从各种复杂性测量方面。我们的方法统一并完善了此类类型的所有以前已知的界限。我们还通过一个恒定的因素来改善Nisan和Szegedy众所周知的块灵敏度与程度不平等，从而提高了Huang最近对敏感性猜想的证据。
We generalize and extend the ideas in a recent paper of Chiarelli, Hatami and Saks to prove new bounds on the number of relevant variables for boolean functions in terms of a variety of complexity measures. Our approach unifies and refines all previously known bounds of this type. We also improve Nisan and Szegedy's well-known block sensitivity vs. degree inequality by a constant factor, thereby improving Huang's recent proof of the sensitivity conjecture by the same constant.
