算法与计算机科学quantamagazine.org
几十年悬而未决的计算机科学猜想，两页纸就被解决
Decades-Old Computer Science Conjecture Solved in Two Pages
2019 — 2021，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这篇 Quanta 文章报道数学家黄皓用仅两页的证明解决了计算机科学领域悬置近三十年的“敏感度猜想”。该猜想涉及布尔函数中输入位变化对输出的影响，其证明基于 n 维超立方体图中点与邻接关系的组合性质。
为什么经久不衰：一个困扰学界近三十年的核心猜想被两页纸的优雅证明攻克，且证明思路简洁到后来还被进一步简化，是理论计算机科学中罕见的经典时刻。
HN 评论精选
汇总了论文、图解和延伸阅读等核心资料，并点出证明的关键引理
附上布尔敏感度的图解链接、论文原文（arXiv:1907.00847）、Scott Aaronson 的博客解读以及更早的 HN 讨论帖。关键结论是：黄皓证明了在 n 维立方体中超过一半的点里，必有一点与至少 √n 个其他点相连，敏感度猜想随之得证。
floatingatoll查看英文原文
On boolean sensitivies: https://d2r55xnwy6nx47.cloudfront.net/uploads/2019/07/Boolean_Sensitivity_FINAL560-1068x1720.jpg The closing quote: > [Huang] was able to prove that in any collection of more than half the points in an n-dimensional cube, there will be some point that is connected to at least √n of the other points — and the sensitivity conjecture instantly followed from this result The actual paper: https://arxiv.org/abs/1907.00847 Another blog post: https://www.scottaaronson.com/blog/?p=4229 An older HN post: https://news.ycombinator.com/item?id=20338281
提醒读者“两页证明”背后是多年积累，标题有误导性
当然，抛开标题党不谈，实际上他们是先思考钻研了七年，站在数十年的具体研究基础上，学习了七年（对他而言）新的数学，才最终写出这两页简洁的证明。
TheRealPomax查看英文原文
When of course, in reality rather than clickbaity titles, they only wrote up the final, concise proof using two pages _after_ thinking about, and working on, the problem for seven years, building on decades of specific research combined with seven years of learning new mathematics (new to Huang, not necessarily new to the world) that might offer ways into cracking this problem.
证明后来又被进一步简化，连专家都感到惊讶
引用 Scott Aaronson 博客：他的前学生 Shalev Ben-David 在评论中给出了黄皓论证的简化版本，不再需要使用柯西交错定理。我原以为这个证明不可能更简单了，结果我错了！
scythmic_waves查看英文原文
From Scott Aaronson's blog (linked in the article): > Another Update: In the comments section, my former student Shalev Ben-David points out a simplification [1] of Huang’s argument, which no longer uses Cauchy’s interlacing theorem. I thought there was no way this proof could possibly be made any simpler, and I was wrong! [1] https://www.scottaaronson.com/blog/?p=4229#comment-1813084
提供作者本人讲解证明的视频讲座
感兴趣的读者可以看论文作者本人的在线讲座：https://www.youtube.com/watch?v=EJoe4qH6kLs
tevlon查看英文原文
For the interested. Here is an online lecture from the author of the paper: https://www.youtube.com/watch?v=EJoe4qH6kLs
历次讨论
同类还值得读
位运算技巧集
Bit Twiddling Hacks
斯坦福页面上的经典位运算技巧合集，收录了 popcount、前导/尾随零、位反转、交换、舍入等大量技巧，并附有解释和性能讨论。
算法与计算机科学上首页 8 次 · 2011–2024graphics.stanford.edu编辑精选如何不按平均评分排序
How Not To Sort By Average Rating
经典文章解释了为什么按平均评分排序不可靠：只有少量评价的条目（比如仅一条五星）会轻易排到最前，而评价数量的差异被忽略。
算法与计算机科学上首页 7 次 · 2009–2024evanmiller.org编辑精选数据结构可视化
Data Structure Visualizations
旧金山大学 David Galles 教授制作的数据结构与算法交互式可视化网站，涵盖 B 树、红黑树、排序、图算法等，可逐步操作观察其运行过程。
算法与计算机科学上首页 6 次 · 2011–2021cs.usfca.edu编辑精选1996 年以来的计算机科学最佳论文奖
Best Paper Awards in Computer Science since 1996
Jeff Huang 维护的一个汇总页面，收录了自 1996 年以来计算机科学各主要会议的“最佳论文奖”获奖名单，并按年份和会议整理，方便读者一站式浏览历届获奖论文。
算法与计算机科学上首页 6 次 · 2010–2018jeffhuang.com编辑精选算法（Jeff Erickson）
Algorithms, by Jeff Erickson
伊利诺伊大学 Jeff Erickson 教授的算法课教材，免费在线开放。
算法与计算机科学上首页 5 次 · 2018–2022jeffe.cs.illinois.edu编辑精选