4 ms·
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 [
by scythmic_waves 6y ago
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.scottaaronson.com/blog/?p=4229#comment-1813084
- anchpop 6y agoKind of makes this seem funny in retrospect: > Aaronson and O’Donnell both called Huang’s paper the “book” proof of the sensitivity conjecture, referring to Paul Erdős’ notion of a celestial book in which God writes the perfect proof of every theorem. “I find it hard to imagine that even God knows how to prove the Sensitivity Conjecture in any simpler way than this,” Aaronson wrote.
- alberto_ol 6y agoA few comments below a guy called Don Knuth claims to have shortened the proof to one page https://www.scottaaronson.com/blog/?p=4229#comment-1815290 https://www.scottaaronson.com/blog/?p=4229#comment-1815290
- BugsJustFindMe 6y agoAnd it's actually only half a page. The first bit is an acknowledgement, and the second half is notes including another few acknowledgements.
- alasdair_ 6y ago> a guy called Don Knuth I found this unreasonably funny, given we’re posting on a tech-focused forum. It’s like posting about “a proof by some dude called Albert Einstein” on a physics forum. :)
- scythmic_waves 6y agoIt was, in fact, _the_ Don Knuth. You can see the proof on his site.
- SatvikBeri 6y agoI initially assumed that this was a random person using Don Knuth as a username, instead of, you know, the real deal.
- makeset 6y agoAh yes, and he seems to have typeset it all nicely in Word.
- hgoury 6y agoI really enjoyed Ben-David (and Shalev-Schwartz)'s book "Understanding machine learning". It's essentially about theory though, not "learn all about machine learning in torchsorflow in 10 days".
- scythmic_waves 6y ago> I really enjoyed Ben-David (and Shalev-Schwartz)'s book "Understanding machine learning". Good to hear! I only made it partway through (up through the kernel trick I think) but I keep meaning to come back to finish it. > torchsorflow Lol
- jcagalawan 6y agoDifferent Ben-David. You're talking about Shalev's dad Shai.
- hgoury 6y agoAh indeed, I mixed up his name with the Shalev part of the name of the other author.
- sdenton4 6y agoNice! And it's a basically a pigeonhole principle argument.
- knuthsat 6y agoKnuth reduced it to half a page in the comments
- scythmic_waves 6y agoHA! I just remembered that that proof was posted to /r/math a while back: https://www.reddit.com/r/math/comments/cl20l6/knuth_has_written_up_a_simplified_proof_of_the/ https://www.reddit.com/r/math/comments/cl20l6/knuth_has_writ...