Decades-Old Computer Science 'Boolean Sensitivity' Conjecture Solved in Two Pages (quantamagazine.org) 101
Long-time Slashdot reader Faizdog writes: The "sensitivity" conjecture stumped many top computer scientists, yet the new proof is so simple that one researcher summed it up in a single tweet.
"This conjecture has stood as one of the most frustrating and embarrassing open problems in all of combinatorics and theoretical computer science," wrote Scott Aaronson of the University of Texas, Austin, in a blog post. "The list of people who tried to solve it and failed is like a who's who of discrete math and theoretical computer science," he added in an email.
The conjecture concerns Boolean functions, rules for transforming a string of input bits (0s and 1s) into a single output bit. One such rule is to output a 1 provided any of the input bits is 1, and a 0 otherwise; another rule is to output a 0 if the string has an even number of 1s, and a 1 otherwise. Every computer circuit is some combination of Boolean functions, making them "the bricks and mortar of whatever you're doing in computer science," said Rocco Servedio of Columbia University.
"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 Erds' 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.
"This conjecture has stood as one of the most frustrating and embarrassing open problems in all of combinatorics and theoretical computer science," wrote Scott Aaronson of the University of Texas, Austin, in a blog post. "The list of people who tried to solve it and failed is like a who's who of discrete math and theoretical computer science," he added in an email.
The conjecture concerns Boolean functions, rules for transforming a string of input bits (0s and 1s) into a single output bit. One such rule is to output a 1 provided any of the input bits is 1, and a 0 otherwise; another rule is to output a 0 if the string has an even number of 1s, and a 1 otherwise. Every computer circuit is some combination of Boolean functions, making them "the bricks and mortar of whatever you're doing in computer science," said Rocco Servedio of Columbia University.
"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 Erds' 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.
Re: (Score:3)
So its solved. Now what?
Re: Short and to the point. (Score:4, Funny)
Step 3: profit
Where's your white cane? (Score:1)
You need to see doctors. For starters, a shrink and an eye doctor.
Re: (Score:2)
Step 3: Gigantic yawn.
On the one hand it's cool that it's been solved, but it's a theoretical computer science problem so esoteric that it takes a small... no, medium-sized essay just to explain what it is to a non-theoretician. For those who haven't read the original paper, it "show[s] that every $(2^{n-1}+1)$-vertex induced subgraph of the $n$-dimensional cube graph has maximum degree at least $\sqrt{n}$". TCS folks will find it fascinating, but I don't know what anyone else is supposed to do with it.
Re: (Score:2)
I'm not convinced it has anything to do with Computer Science other than who proposed the problem.
It seems to be purely a math game that doesn't involve a computer at all.
Even the graduate level combinatorics classes that they say it will be taught in "all of" this fall are in the math department.
When I wanted to check out a book on combinatorics in compilers, I didn't find it in the University's Science Library with the compiler books; it was in a back corner of the Math Library!
Re: (Score:2)
I'm not convinced it has anything to do with Computer Science other than who proposed the problem. It seems to be purely a math game that doesn't involve a computer at all.
Yeah, as I said, it's Theoretical Computer Science. You've described it perfectly.
Re: (Score:1)
I don't follow all the math, but it sounds like Huang's been down into Greg Egan's truth mines and come back up with a really nice gem. If you don't get the reference, immediately go out and buy all of Greg Egan's books. He makes a living as a software engineer. Last time I checked he was in Perth, Australia.
www.gregegan.net
Re: (Score:1)
I think it was either in Diaspora or Permutation city. Not sure, though.
The truth mines, that is.
(Not deliberately trying to plug all of Greg Egan's books.)
Re: (Score:2)
Have you seen the crap people can do with Unicode on other sites? They can build sideways stacked text a mile tall.
This site is the testbed for trolling. It is my understanding they disallowed editing posts because people were making crafted outrageous trolls, causing predictable responses, then going back and editing their posts to make trollee look idiotic.
Re: (Score:1)
Don't you mean Erdos?
(pronounced "Erdish"?)
--
If it's just for myself, I don't much care.
Re: (Score:2)
November 8, 1923
Jefferson City, Missouri, U.S.
Two slashdot editors walk into a bar... (Score:1)
both get immediately stabbed, choked, stomped, and left for dead.
Funnier when you were there.
Bad editing (Score:5, Insightful)
What about actually stating somewhere in the story what the sensitivity conjecture actually is? But no, that could have been helpful...
Re: (Score:2)
We are just humble god loving jews. we suck kids dicks. we run your banks in the best of honest intentions possible / 100.
We literally love Jews. When our messiah comes to third temple thanks to Donald Trumps help we will have all the non jews as our slaves.
Did I mention the holocaust and Donald Trump is a white supremacist? Saw it on CNN.
Modern Christian preachers support Israel not because it's right to support a democracy surrounded by dictatorships that want to push it into the sea, but because Israel needs to exist, according to the Bible, so it can get destroyed to usher in the end times.
Re:Bad editing (Score:5, Informative)
It's apparently hidden from view behind this paywall here. [acm.org] Yay Academia, you're so useful to us.
From wikipedia,
The sensitivity of a Boolean function f at a given point is the number of coordinates i such that if we flip the i'th coordinate, the value of the function changes.
So that's something. I found this attempt to define the conjecture at princeton.edu.
What are smooth Boolean functions, and how simple are they? One measure of smoothness is the sensitivity of the function to local changes. Let the graph G(f) of a Boolean function f on the n-dimensional cube be the (bipartite) subgraph of the cube graph containing only edges with different f-values.
The sensitivity of f, denoted s(f), is simply the maximum vertex degree of G(f). When s(f) is small compared to the number n of variables, it means that for every vertex x, flipping the bit in one coordinate will change the value of f only for very few coordinates. The basic high level question under study is what structure is implied by this smoothness?
One measure of simplicity of a Boolean function is its Fourier degree. More precisely, let deg(f) be the degree of the unique real multilinear polynomial which equals f on every vertex of the cube. This measure of simplicity is extremely robust, in that remarkably many other parameters of Boolean functions are polynomially related to deg(f). These include the computational complexity of f in the deterministic, probabilistic, quantum and non-deterministic decision tree models.
The sensitivity conjecture, formulated by Noam Nisan and Mario Szegedy in the 1990s, asserts that smooth functions are simple: deg(f) < (s(f))^c, for some fixed constant c independent of n and f.
Of course, "smooth function" isn't defined, so I guess the audience was just expected to already know.
Note on the above, the "cube" mentioned is the n-diminsional cube representing a Boolean function of n bits: every vertex of the cube is an input, and the value at each vertex is the corresponding result. The "coordinates" are thus the input bits.
Re: (Score:3)
Of course, "smooth function" isn't defined, so I guess the audience was just expected to already know.
Just as likely, the person who copied the text from whatever source he found it simply didn’t understand what he was copying and so had no idea that concept also needed explanation.
Re: (Score:2)
Holy crap with a definition like that it's no surprise it was hard to prove. Now excuse me while I get a math degree just so I can understand the problem.
There are some smart cookies in the world.
Re: Bad editing (Score:1)
My conjecture: smooth functions require smooth operators - even in Fortran. Still awaiting proof: m(j) is an example.
Re: Bad editing (Score:2)
I do not get the "frustration" about a conjecture that requires so much preamble...
Re: (Score:1)
What about actually stating somewhere in the story what the sensitivity conjecture actually is? But no, that could have been helpful...
If only there was a way to find out. If... only... there... was... a... way. https://www.quantamagazine.org... [quantamagazine.org]
Re: (Score:1)
Can you explain it in your own words? Just linking the article isn't helpful.
Re:Bad editing (Score:4, Funny)
Re: (Score:3)
Re: (Score:3)
When you have a formula made up of boolean logic, things like "complexity" (not going to explain) and most other relationships between the variables are polynomial. "Sensitivity" though they didn't have a proof for that. It seemed like it should be true, but they had trouble ruling out an exponential relationship in some cases.
What this means is that now you can do calculus with the sensitivity of a boolean function. Eg, in some cases you might be able to do a better job predicting the worst case time of an
Re: s/God/I/ (Score:2)
Yay, you just stumbled upon Advaita Vedanta:
The term Advaita refers to its idea that the true self, Atman, is the same as the highest metaphysical Reality (Brahman).
https://en.m.wikipedia.org/wik... [wikipedia.org]
Om.
What does it mean for dummies? (Score:5, Informative)
Sensitivity is one of the measures of boolean function complexity.
Sensitivity is the maximum number of bits which need to be flipped so that the result of a boolean function flips. The maximum is taken over all the possible inputs of the boolean function.
The sensitivity conjecture says that these alternative complexity measures are polynomially related to each other; that their result is just smaller than some constant power of the sensitivity measure.
Hao Huang found a lower limit of sensitivity (measure) in some interesting cases which led to the proof of the conjecture.
Not sure how useful it actually is except knowing that boolean function complexity measures are somewhat similar; i.e. none of them deviates too much from the others. Maybe somebody can point out something.
Re: (Score:1)
Even better:
"the maximum number (of single input bit flips) (resulting) into (single result) bit flip"
I am knew to this though, but that's how I interpret sensitivity and I think it's correct based on:
1. https://www.quantamagazine.org/mathematician-solves-computer-science-conjecture-in-two-pages-20190725/
and
2. https://www.quantamagazine.org/mathematician-solves-computer-science-conjecture-in-two-pages-20190725/
"
The total influence of a Boolean function is also the average sensitivity of the function. The se
Re: (Score:2, Informative)
The usefulness of a proof is inversely proportional to its length, and directly proportional to its novelty. Being shorter makes it more intuitive and easier to apply to other problems; while being novel is also useful.
The method of proof is both short and novel. That should pay dividends. The actual proposition itself is maybe not as useful.
what IS the conjecture? (Score:1)
Like, we're smart people here. We can take a bit of maths in the summary. Yes, I know what an or gate is, I know what even parity is. Tell us the CONJECTURE that has been solved?
Re: (Score:1)
I think the conjecture is that sensitivity can be part of the framework that is used measure the complexity of a given Boolean function. I don't know the details, or even that there was a framework in the first place.
Re: (Score:1)
There are a bunch of other metrics for boolean functions and they can all be converted between each other using a polynomial. Such a transformation hadn't been found for sensitivity til this paper, proving an old conjecture that such a thing exists. Everyone in the field expected such a proof to be an awful mess but instead the first proof found is a simple geometric argument about the corners of a cube.
Re: (Score:2)
but instead the first proof found is a simple geometric argument about the corners of a cube.
Its an interesting take on visualizing boolean functions, but I think just saying "cube" is misleading. "The corners of an N-dimensional cube" would be a far more revealing wording. You can imagine the output of a function of N boolean inputs to be the labeled corners of an N-dimensional unit volume.
Re: (Score:2)
There are a bunch of other metrics for boolean functions and they can all be converted between each other using a polynomial. Such a transformation hadn't been found for sensitivity til this paper, proving an old conjecture that such a thing exists. Everyone in the field expected such a proof to be an awful mess but instead the first proof found is a simple geometric argument about the corners of a cube.
Thank you, assuming your description is accurate. :)
Re: (Score:2)
Theoretical bullshit in other words. Now the footnotes in textbooks can be updated.
Peer review (Score:3)
Does twitter count as submission to peer review or self publishing?
Re: Peer review (Score:2)
My conjecture: (Score:2)
My conjecture: Twitter dumbs Computer Science down to the level of humanities.
So the first rule is trivial, it can be simplified to the output is equal to the input.
Re: (Score:2)
Not sure what programming language that is (Java, I suppose), but if it means what I think it means, no. The bit string 10 is a sequence of input bits, but the desired output is 1, and 10 =/= 1. Even less sure what the second rule does, because I'm not sure how the variable 'state' gets initialized. But whatever it does, it's going to have to return 1 for 0, 11, 101, 1001, 1010, 1100 etc., and return 0 for 1, 10, 1011, 1101 etc., and I doubt it does that.
At any rate, those two rules were chosen to be simple
stupid summary does not have actual text of conj (Score:2)
This frustrating paragraph about conjecture that starts as if it will actually provide the text of it.
Such a discovery is the dream of every scholar. (Score:1)
Making a discovery of this type is the dream of every scholar. Huang's proof will now almost certainly be mentioned in almost every master’s-level combinatorics course for the foreseeable future.
What matters in this case is not just the aspect that Huang managed to prove the conjecture, but that he was able to do so elegantly in only 2 pages. The simplicity and elegance of his proof ensure that it will be discussed in almost every master’s-level combinatorics course so long as civilization lasts