[Skydiver]

Mathematician Solves Computer Science Conjecture in Two Pages

Quote

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.

Quote

I expect that this fall it will be taught — in a single lecture — in every master’s-level combinatorics course.

Quote

“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.

[macosxnerd101]

The proof of the sensitivity conjecture comes down to the Eigenvalue Interlace Theorem from linear algebra. The application is to the adjacency matrix of the hypercube. I wouldn't be surprised to see Huang's proof as an exercise in Spectral Graph Theory courses, moving forward. The proof is actually that simple.

https://arxiv.org/pdf/1907.00847.pdf

[DarenR]

i stopped at Qn -- to many letters not enough names for me -- ha