21–30 of 107 posts
Frankly speaking I don't know what the "Sensitivity Conjecture" is, and also wondering how many people on HN know about it? Or people are upvoting without knowing what it is :) So HN ...
Frankly speaking I don't know what the "Sensitivity Conjecture" is, and also wondering how many people on HN know about it? Or people are upvoting without knowing what it is :) So HN ...
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
> 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.
Earlier quoted context omitted.
I think that would be because God is nature (for those who believe in God) and math is how humans describe nature. That would be the same as saying that nature can't be expressed in its own language any simpler than this.
What aspect of nature does the sensitivity conjecture describe?
I was talking about nature as in "the universe we live in". Answering that question is just describing the problem itself.
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-4 hypercube graph is the graph which takes a cube, makes a copy, and then connects the corresponding vertices.
...
- The dimension-n hypercube graph is the graph which takes a dimension-(n-1) hypercube graph, makes a copy, and connects the corresponding vertices.
Ok, so let's play a game (for now, think about the 3-dimensional cube graph as a concrete example): if you could color the vertices of the cube red or green, what is the largest number of red (or green) vertices you can find such that no two of the same color are adjacent to each other? Note that the 3D hypercube has 2³=8 vertices, and, more generally, the nD hypercube has 2ⁿ vertices, so you have a lot of vertices to color :)
So, it turns out (and I will give it to you as an exercise!) that you can color 2ⁿ⁻¹ vertices of the cube with two colors without any vertices of a single color being adjacent to each other, but, if you try changing the color of any one vertex then at least one of the colors will have (at least) √n neighbors that are the same color! (It may be worth reading this once or twice :)
This is the sensitivity conjecture! The fact that changing any one color would immediately imply that now you have at least √n neighbors that are all of the same color. (This is a slightly funky restatement of it, the usual one is in terms of subgraphs or boolean functions, but one is easily mapped to the other.)
It turns out a lot of important problems (in things like voting systems, for example) can be reduced to proving this conjecture, which gives a rather neat set of results "for free" when proving it, and why it's been such an interesting object for the past uhh, quite a few years in computer science :)
“ 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?
Mathematics often deal in abstractions, and "God" may be used as a linguistic abstraction for ideal or perfect knowledge. It's a shorthand in writing casually about the most elegant mathematical insights. Its use is also a tradition via Erdos with "The Book", which Aaronson and many mathematicians pay homage to.
“ 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?
It's a shortcut, they're not literally invoking "God". It's an encoding of: We don't know what the optimum is, but we can imagine the complete set of possible things, and from those there will be one that's best. So that's the optimum, and we want to refer to it. We don't know what it is, but we assume it exists, so let's just call it 'God's solution'
Not necessarily, unless we make some more assumptions about the set of proofs and/or the proof goodness function ;)
The 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…
One thing that always makes me laugh though is the terminology in math. Things like "hypercube" just get a chuckle out of me.
I didn't know what the sensitivity conjecture is but your explanation using coloring a graph is very straightforward.