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

#1 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 7025
  • View blog
  • Posts: 23,851
  • 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   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12641
  • View blog
  • Posts: 45,813
  • 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
Was This Post Helpful? 0
  • +
  • -

#3 DarenR   User is offline

  • D.I.C Lover

Reputation: 634
  • View blog
  • Posts: 4,201
  • 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
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1