Earlier quoted context omitted.
Interesting... so what does a "5 dimensional" cube look like? I am having difficulty visualizing that
4 took me hours. Give up any visuals.
Decades-Old Computer Science Conjecture Solved in Two Pages
71–74 of 74 posts
Re: Decades-Old Computer Science Conjecture Solved in Two Pages
#72Earlier quoted context omitted.
I read that, but I believe that's describing the problem. Anyone care to explain the answer in a similar simple way? Actually one thing weird wiht that explanation is they call sensitive bits the ones that don't change the output? You'd think it would be the red ones
That is the solution! See? It's so simple it seems like a formulation of the problem itself! The solution is to think of the input ('001') in terms of an n-dimensional cube, where n is the length of the input. So for example, a binary logic with 5 bits ('01010') would require a 5-dimensional cube. From there, you check whether moving from one input ('00001') to an adjacent input ('00011') causes a flip in the output.…
The article is quite clear that this formulation of the problem has been around for a while and did not lead to a proof until Huang had his special insight.
> Huang knew, as did the broader research community, that the sensitivity conjecture could be settled if mathematicians could prove an easily stated conjecture about collections of points on cubes of different dimensions.
> In 1992, Craig Gotsman, now of the New Jersey Institute of Technology, and Nati Linial of Hebrew University figured out that proving the sensitivity conjecture can be reduced to answering a simple question about cubes of different dimensions: If you choose any collection of more than half the corners of a cube and color them red, is there always some red point that is connected to many other red points?
Re: Decades-Old Computer Science Conjecture Solved in Two Pages
#73>the new proof is so simple that one researcher summed it up in a single tweet. Didn't look that simple to me! Reminds me of Andrew Ng showing his students the simple one liner to solve the cocktail party problem in Octave. There's a lot represented in that one line of code!
Where is the tweet?
Re: Decades-Old Computer Science Conjecture Solved in Two Pages
#74Pretty good for an "Amateur Mathematician", I can't wait to see what he does once he goes pro.
Huang is a professional mathematician at Emory.