# Mathematician Solves 30-Year Old Comp Sci Conjecture in Two Pages

Page 1 of 1

## 2 Replies - 1164 Views - Last Post: 26 July 2019 - 12:42 PM

### #1 Skydiver

• Code herder

Reputation: 7132
• Posts: 24,225
• Joined: 05-May 12

# Mathematician Solves 30-Year Old Comp Sci Conjecture in Two Pages

Posted 25 July 2019 - 09:30 PM

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.

Is This A Good Question/Topic? 2

## Replies To: Mathematician Solves 30-Year Old Comp Sci Conjecture in Two Pages

### #2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12657
• Posts: 45,831
• Joined: 27-December 08

## Re: Mathematician Solves 30-Year Old Comp Sci Conjecture in Two Pages

Posted 25 July 2019 - 10:00 PM

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

### #3 DarenR

• D.I.C Lover

Reputation: 634
• Posts: 4,215
• Joined: 12-January 10

## Re: Mathematician Solves 30-Year Old Comp Sci Conjecture in Two Pages

Posted 26 July 2019 - 12:42 PM

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