按年被提到
20192019 · 3 次2026
数学、逻辑与理论›数学猜想与重大证明·arXiv:1907.00847 · math.CO

Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture

超立方体的导出子图与敏感度猜想的证明
Hao Huang · 2019

极简证明敏感度猜想:布尔函数的敏感度与次数多项式相关

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 5 人首次 2019-07-26 · 最近 2021-10-05发表于 Annals of Mathematics
5不同的人
4活跃月份
5讨论串
112被引(OpenAlex)

论文证明:n 维立方体图中任何含 2^(n-1)+1 个顶点的导出子图,其最大度至少为 √n,该结果是最优的,并改进了 Chung、Füredi、Graham 和 Seymour 在 1988 年得到的对数下界。由此直接推出布尔函数的敏感度与次数是多项式相关的,解决了理论计算机科学中 Nisan 与 Szegedy 提出的敏感度猜想这一基础性难题。

HN 为什么提它

评论者把它当作令人惊叹的简单证明来推荐,用它说明该领域的近期进展,也有人欣赏它仅用一个 .tex 文件就能生成完整 PDF。

奠基之作难度 4 / 5约 20 分钟经得起时间
读之前最好知道
1布尔函数的敏感度与次数
2超立方体图与图的谱
3线性代数(特征值、交错定理)
4组合学基础

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
推荐amirhirsch · 2021-10

“Some recent progress in the field includes the amazingly simple proof of the Sensitivity Theorem by Hao Huang: Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture”

推荐黄皓对敏感度定理极其简洁的证明
The NAND gate. One gate to rule them all原评论 ↗
引用plg · 2019-07

“nice use of a single.tex file to produce the full.pdf”

称赞它只用一个 .tex 文件就生成完整 PDF
Decades-Old Computer Science Conjecture Solved in Two Pages原评论 ↗
被提交为 story · 3 次