The Sensitivity Conjecture has been solved. What is it about?

612 views
0

In the paper below, Hao Huang, apparently provides a solution to the sensitivity conjecture, a mathematical problem which has been open for quite a while. Could someone provide an explanation what the problem and solution are about and why this is significant?

(http://www.mathcs.emory.edu/~hhuan30/papers/sensitivity_1.pdf)

In: Mathematics

Think of it like a Buzzfeed quiz. You answer a bunch of multiple-choice input questions about seemingly random topics (‘What’s your favourite breakfast cereal?’, ‘What’s your favourite classic movie?’, ‘What did you want to be when you grew up?’, and so on), and you get a response back at the end: usually which Hogwarts house you belong in.

But shock, horror: after answering twenty questions honestly, Buzzfeed informs you that you are a Hufflepuff, when you *know* that you’re actually (obviously) a Ravenclaw. So you take the test again. You change one answer, and boom! Now Buzzfeed tells you that you’re the Ravenclaw you always knew you were meant to be.

But you start to wonder: just how many of the input questions could you change in order to change the output? Some of them won’t make a difference to the result; it doesn’t matter whether you prefer Coco Pops or Rice Krispies, because the Sorting Hat only uses that to determine between Gryffindors and Slytherins, and based on your other answers you are *obviously* neither. On the other hand, some of them will. No self-respecting Hufflepuff would ever answer that their favourite classic movie is *Inherit the Wind*, so flipping that answer will immediately flip the output and put you in a different house, without you changing the answer to any other question.

*That’s* the sensitivity of a system. If there are three individual answers you could switch that would each change the output, we say the system has a sensitivity of — you guessed it — three. (In computer science terms, this is usually considered as a sort of true-or-false, 1-or-0 example, but the basic idea is the same: how many true-or-false inputs can you flip to change the true-or-false output?) This is a way of measuring just how complex the system is. There are other measures of complexity, but over time they were mathematically proven to be polynomial in nature. (That contrasts with it being *exponential* in nature, which would have set it apart from other complexity measures. You don’t need to worry *too* much about what that means to get a surface understanding of what’s going on; just understand that people suspected it might be polynomial like all the others, but hadn’t yet proved it.)

The conjecture, and I’m really ELI5ing it here, is about whether or not the rules for sensitivity follow the same rules as other measures of complexity, or whether it’s a weird outlier. The short version is yes, it follows the same rules. (If you want to get particular about it, what was proved was that ‘every 2^n-1 + 1-vertex induced subgraph of the n-dimensional cube graph has maximum degree at least √n’, which is comfortably above my paygrade and well out of the remit of ELI5.)

The reason why it’s so significant is because this was one of those problems that anyone who’s anyone in the field had tried to make even incremental progress towards in the past thirty years, but had generally failed. Along comes Huang, and produces a proof that’s two pages long — that is to say, extremely elegant. It’s the computer science version of a team of cryptozoologists spending decades searching for Bigfoot, and then the new guy on the team says, ‘Wait, you mean Harry? Hairy guy, kind of blurry, lives in the woods? Yeah, he’s on my bowling team. He’s cool.’ (In actual fact, the solution goes above and beyond what would be needed for a proof, so it’s opened up several new interesting questions; it’s closer to the new guy saying, ‘Yeah, Harry’s on my bowling team. Last week he brought the Loch Ness Monster and the Chupacabra. We went out for tacos. Nice guys. Want me to give you their Snapchat?’)

That’s why people are talking about it. It’s not a *colossal* leap forward in terms of changing the field, but it’s impressive that it was solved and that the solution was so neat.

[removed]

Piggyback question, does Huang get anything out of this solution?

I guess ELI5 isn’t the same as a nutshell. Anyone, please?

Some explanation for someone who has never read or seen Harry Potter, please? There are dozens of us!

Does this have any practical applications? Engineering, science, etc?

As an add-on to /u/Portarossa’s excellent explanation, you should read this nice write-up on it.

https://www.quantamagazine.org/mathematician-solves-computer-science-conjecture-in-two-pages-20190725/