# A mathematician has resolved the Sensitivity Conjecture, a nearly thirty-year-old problem in computer science

1. 
Nmg
This is pretty cool. I think it is also notable because an n bit input Boolean function has 2^n possible inputs and (correct me if I am wrong), ( n 2^n /2 ) unique connections between neighboring...

This is pretty cool. I think it is also notable because an n bit input Boolean function has 2^n possible inputs and (correct me if I am wrong), ( n 2^n /2 ) unique connections between neighboring inputs ("edges of the cube.")

To transverse n × 2^n /2 edges is a lot...think about even 32 bit addition. That's 64 input bits or a gazillion transversals that could never be completed in the life of the universe. Then of course you have a 32 bit output, so multiply a gazillion by 32.

It's good to have a proof to tell you what "limits" you might have for problems like this.

Edit: I did the math, and to transverse all edges of a 32 bit adder function would take you more than a trillion years...

1. GnomeChompski
Thank you for your math. Reminds me of the story of the math that Emil Konopinski did.

Thank you for your math. Reminds me of the story of the math that Emil Konopinski did.

1 vote
2. gpl
Here is the preprint of the proof. The preprint is 6 pages, of which about 2 are actually the proof. If you are familiar with linear algebra and graph theory you might want to take a look here, as...

Here is the preprint of the proof. The preprint is 6 pages, of which about 2 are actually the proof. If you are familiar with linear algebra and graph theory you might want to take a look here, as the proof is relatively accessible.

Also check out Scott Aaronson's blog post about it. His blog in general is usually worth a read when there's a buzz in the CS / QC world.