Should add (2019) to the title.
It's there now. Thanks!
Mathematician Solves Sensitivity Conjecture in Two Pages (2019)
81–90 of 107 posts
Re: Mathematician Solves Sensitivity Conjecture in Two Pages (2019)
#82Earlier quoted context omitted.
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".
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.
Re: Mathematician Solves Sensitivity Conjecture in Two Pages (2019)
#83The sensitivity conjecture is actually pretty simple to understand, intuitively. (Its reduction to applications, and its proof, of course, are both a little bit more of the "magical" parts so-to-speak.) The 'canonical' way of thinking about it is in terms of the hypercube graph , which is defined in the following way: - The dimension-0 hypercube graph is... just a single vertex. . - The dimension-1 hypercube graph is…
A vertex on an nD hypercube has n neighbours, so how do you manage to colour it to have √n neighbours? Shouldn't it be n? If it's √n, then do you round it up or down?
Re: Mathematician Solves Sensitivity Conjecture in Two Pages (2019)
#84Earlier quoted context omitted.
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
I initially assumed that this was a random person using Don Knuth as a username, instead of, you know, the real deal.
Re: Mathematician Solves Sensitivity Conjecture in Two Pages (2019)
#85The sensitivity conjecture is actually pretty simple to understand, intuitively. (Its reduction to applications, and its proof, of course, are both a little bit more of the "magical" parts so-to-speak.) The 'canonical' way of thinking about it is in terms of the hypercube graph , which is defined in the following way: - The dimension-0 hypercube graph is... just a single vertex. . - The dimension-1 hypercube graph is…
A vertex on an nD hypercube has n neighbours, so how do you manage to colour it to have √n neighbours? Shouldn't it be n? If it's √n, then do you round it up or down?
Sorry, if it wasn't clear it should have √n neighbours of the same color! (The number of actual neighbors of each vertex is fixed, as you said, to n :)
In the latter case, you round up!
Re: Mathematician Solves Sensitivity Conjecture in Two Pages (2019)
#86Earlier quoted context omitted.
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.
Re: Mathematician Solves Sensitivity Conjecture in Two Pages (2019)
#87Earlier quoted context omitted.
The name of the mathematician is Hao Huang
Huang Hao. Chinese family name姓 first
It is notable that in English, Chinese names are generally written given-family, but in French the original family-given order is preserved. I'm curious how other languages handle this -- any takers?
Re: Mathematician Solves Sensitivity Conjecture in Two Pages (2019)
#88“ I find it hard to imagine that even God knows how to prove the Sensitivity Conjecture in any simpler way than this.” Why is there a tendency to invoke God in math?
In most religions, God is an omnipotent, omniscient, and generally perfect being. Mathematicians simply borrowed that definition. For example, Rubik's cube "God's number" is 20. Because, of course, God, as an omniscient, omnipotent perfect being will solve the puzzle in the minimum possible amount of moves. And that number is 20 in the most complex case. Computer science have a similar, more formal concept with oracl…
The overwhelming majority of religions are not monotheistic and believe no such thing about any given deity. /nitpick
Re: Mathematician Solves Sensitivity Conjecture in Two Pages (2019)
#89The sensitivity conjecture is actually pretty simple to understand, intuitively. (Its reduction to applications, and its proof, of course, are both a little bit more of the "magical" parts so-to-speak.) The 'canonical' way of thinking about it is in terms of the hypercube graph , which is defined in the following way: - The dimension-0 hypercube graph is... just a single vertex. . - The dimension-1 hypercube graph is…
FWIW, I found your explanation helpful, but introducing two colours confused it needlessly for me.
I'd say: You have a hypercube of dimension n with 2^n vertices, and you start colouring one after another of them, without having any two adjacent vertices coloured.
You'll find that you can mark half of them (that is, 2^(n-1)) without any having a coloured neighbour (basically, you always go diagonal) - but as soon as you mark even one more, there'll be at least one vertex with at least sqrt(n) marked neighbours.
Re: Mathematician Solves Sensitivity Conjecture in Two Pages (2019)
#90Just to emphasize how conceptually easy the proof is when boiled down to its bare essentials, here is the proof in tweet form
https://twitter.com/BooleanAnalysis/status/11458375764876124...