Hacker News Reader

Comment by scythmic_waves | Hacker News Reader

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

View on HN

Kind 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.

A 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

> 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. :)

It was, in fact, _the_ Don Knuth. You can see the proof on his site.

I initially assumed that this was a random person using Don Knuth as a username, instead of, you know, the real deal.

Ah yes, and he seems to have typeset it all nicely in Word.

And it's actually only half a page. The first bit is an acknowledgement, and the second half is notes including another few acknowledgements.

Knuth reduced it to half a page in the comments

HA! I just remembered that that proof was posted to /r/math a while back:

https://www.reddit.com/r/math/comments/cl20l6/knuth_has_writ...

I 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".

> 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

Different Ben-David. You're talking about Shalev's dad Shai.

Ah indeed, I mixed up his name with the Shalev part of the name of the other author.

Nice! And it's a basically a pigeonhole principle argument.

Reply on news.ycombinator.com