推荐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”
推荐黄皓对敏感度定理极其简洁的证明
极简证明敏感度猜想:布尔函数的敏感度与次数多项式相关
论文证明:n 维立方体图中任何含 2^(n-1)+1 个顶点的导出子图,其最大度至少为 √n,该结果是最优的,并改进了 Chung、Füredi、Graham 和 Seymour 在 1988 年得到的对数下界。由此直接推出布尔函数的敏感度与次数是多项式相关的,解决了理论计算机科学中 Nisan 与 Szegedy 提出的敏感度猜想这一基础性难题。
评论者把它当作令人惊叹的简单证明来推荐,用它说明该领域的近期进展,也有人欣赏它仅用一个 .tex 文件就能生成完整 PDF。
“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”
“nice use of a single.tex file to produce the full.pdf”