敏感性与块敏感性之间的超二次分离
A superquadratic separation between sensitivity and block sensitivity
OpenAI 数学仓库收录的研究手稿。展开查看英文摘要，或标记后让我进一步解释。
具体内容
该稿件研究布尔函数的敏感性与块敏感性之间的关系。作者声称否定了敏感性猜想的二次强化，构造了非恒定全布尔函数，其块敏感性增长快于敏感性的任何常数倍平方。具体地，对于某个固定α>2，例子具有无界块敏感性且满足bs(f)≥s(f)^α。研究意义在于表明敏感性与块敏感性之间可以存在超二次的分离。
- 作者声称否定了敏感性猜想的二次强化。
- 构造了非恒定全布尔函数，其块敏感性增长快于敏感性的任何常数倍平方。
- 对某个固定α>2，例子满足bs(f)≥s(f)^α且块敏感性无界。
AI 产生的研究手稿；收录不表示已完成独立审查或同行评议。
英文原始摘要
We disprove the quadratic strengthening of the Sensitivity Conjecture by constructing nonconstant total Boolean functions whose block sensitivity grows faster than any constant multiple of sensitivity squared. In fact, for some fixed α > 2, our examples have unbounded block sensitivity and satisfy $`\mathop{\mathrm{bs}}\nolimits (f)\ge s(f)^\alpha`$.
用户标记：未标记
固定编号：654d6f1a214b4eb5
原文来源