Shtetl-Optimized » Blog Archive » Sensitivity Conjecture resolved
The Sensitivity Conjecture, which I blogged about here, says that, for every Boolean function f:{0,1}n→{0,1}, the sensitivity of f—that is, the maximum, over all 2n input strings x∈{0,1}n, of the number of input bits such that flipping them changes the value of f—is at most polynomially smal...
Hasnain says:
Been a while since I’ve been able to nerd out on something. This was surprisingly interesting and accessible take on a new mathematical discovery defining a surprisingly simple problem.
“Paul Erdös famously spoke of a book, maintained by God, in which was written the simplest, most beautiful proof of each theorem. The highest compliment Erdös could give a proof was that it “came straight from the book.” In this case, I find it hard to imagine that even God knows how to prove the Sensitivity Conjecture in any simpler way than this.”
Additional accessible article in the comments.
Posted on 2019-07-26T04:11:14+0000