SoylentNews is people
SoylentNews
Decades-Old Computer Science Conjecture Solved in Two Pages
Over the years, computer scientists have developed many ways to measure the complexity of a given Boolean function. Each measure captures a different aspect of how the information in the input string determines the output bit. For instance, the "sensitivity" of a Boolean function tracks, roughly speaking, the likelihood that flipping a single input bit will alter the output bit. And "query complexity" calculates how many input bits you have to ask about before you can be sure of the output.
Each measure provides a unique window into the structure of the Boolean function. Yet computer scientists have found that nearly all these measures fit into a unified framework, so that the value of any one of them is a rough gauge for the value of the others. Only one complexity measure didn't seem to fit in: sensitivity.
In 1992, Noam Nisan of the Hebrew University of Jerusalem and Mario Szegedy, now of Rutgers University, conjectured that sensitivity does indeed fit into this framework. But no one could prove it. "This, I would say, probably was the outstanding open question in the study of Boolean functions," Servedio said. "People wrote long, complicated papers trying to make the tiniest progress," said Ryan O'Donnell of Carnegie Mellon University.
Now Hao Huang, a mathematician at Emory University, has proved the sensitivity conjecture with an ingenious but elementary two-page argument about the combinatorics of points on cubes. "It is just beautiful, like a precious pearl," wrote Claire Mathieu, of the French National Center for Scientific Research, during a Skype interview. 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.
(Score: 0) by Anonymous Coward on Monday July 29 2019, @12:41AM (5 children)
I knew the "conjecture" was true way before.
(Score: 2) by martyb on Monday July 29 2019, @01:45AM (4 children)
Wit is intellect, dancing.
(Score: 0) by Anonymous Coward on Monday July 29 2019, @02:34AM (3 children)
Assume the predicate false. Then I wouldn't have known it to be true, but I knew it to be true, and way back when. Therefore it is true.
Q.E.D.
(Score: 1) by khallow on Monday July 29 2019, @05:24AM
(Score: 2) by martyb on Monday July 29 2019, @10:41AM (1 child)
And just how is it that you "knew it to be true"? Claim without facts in evidence.
Let's try your "proof" using this conjecture: "The Earth is flat."
Wit is intellect, dancing.
(Score: -1, Troll) by Anonymous Coward on Monday July 29 2019, @06:46PM
You clearly failed to notice "Q.E.D." The proof concludes, conclusively, with a "Q.E.D." at the end. Do you know what "Q.E.D." means? In math, it means "shut the fuck up, case closed."
(Score: 0) by Anonymous Coward on Monday July 29 2019, @01:28AM (2 children)
Paul Erdős thanked is creativity and productivity to his use of amphetamine.
(Score: 2) by ikanreed on Monday July 29 2019, @01:36AM
You say that like overdose wasn't the most common cause of death among historic mathematicians.
(Score: 0) by Anonymous Coward on Monday July 29 2019, @03:47PM
For what it’s worth, there’s a passage in “The Man Who Loved Only Numbers” that says that Erdos didn’t want the stuff about amphetamines in the book because he didn’t want young mathematicians to think that they needed to take them in order to do math.
(Score: 3, Insightful) by black6host on Monday July 29 2019, @01:50AM (2 children)
This is a cool thing. At least for me, because I like mathematics. Logic classes were a favorite of mine way back when and I will admit that I had no idea, at the time, that Boolean functions could be studied so.
Hey kids, this is math. When you're studying for whatever degree in a computer related field don't tsk tsk your math classes. EVERYTHING regarding how computers work involves math. Even quantum computers...
When the day comes that wetware computing is prevalent, if ever, math will still be involved. For reference: https://en.wikipedia.org/wiki/Wetware_computer [wikipedia.org]
(Score: 1, Interesting) by Anonymous Coward on Monday July 29 2019, @05:12AM
Reminds me of this: https://xkcd.com/435/ [xkcd.com] because everything is just a higher-level abstraction or application of the math underneath.
(Score: -1, Flamebait) by Anonymous Coward on Monday July 29 2019, @03:51PM
You "like" math. That's nice - some reflected glory for you, Sir.
What were you doing last night at 4am? If you "liked" math like Erdos, you would be snorting Meth just so you could solve ONE MOAR EQUATION. I don't think you really like math.