I'm sorry, I still don't understand practical applications of that paper. Does that mean we now can write "smart" function with input of booleans and sensitivity and get results much faster than if we just iterate over booleans?
It's all about different ways of measuring how good a function is at scrambling the input data. I'm guessing if you want to break (or make) a hash or cryptosystem you will use these measures over various aspects of it to look for weaknesses or some such.
This particular proof seems to be saying that the measure called sensitivity will give you similar answer to a bunch of other measures.
On the one hand, that's disappointing (a measure that gave totally different results might enlighten whole new ways of attacking/strengthening you crypto). On the other hand it is encouraging because if a whole bunch of very different measures agree, then that's a sign that they are on to something real.
> But no one could prove it. […] “People wrote long, complicated papers trying to make the tiniest progress,”[…] this power should yield new insights about complexity measures. “It adds to our toolkit for maybe trying to answer other questions in the analysis of Boolean functions,” […]
etc.
But essentially a large part of why this is a big deal is that it was a "long"-unproven conjecture that smart people had looked at over the years and not solved, and expected to take heavier machinery, and that all of a sudden got a really simple proof.
I hope so.