News for hackers. Stuff that matters.
Re:‘Outsiders’ Crack 50-Year-Old Math Problem (2015) by ddinh on Tuesday December 05, 2017 @07:36PM (#15857552)
Quick note that the article is from 2015, and the MSS result dates back to 2013.

There's a blog post by Nikhil here that explains the proof of the discrepancy result that implies Kadison-Singer: https://windowsontheory.org/2013/07/11/discrepancy-graphs-an...

The main result is a theorem that replaces a Chernoff bound (saying here that a random partition has discrepancy logarithmic in the number of vectors with high probability) with a bound that says achieves a better bound on the discrepancy, independent of the number of vectors, at the cost of replacing the "with high probability" with "there exists".

The proof uses some really beautiful techniques from the geometry of polynomial roots to prove this and is a pretty fun read: https://arxiv.org/abs/1306.3969

There are no comments on this comment yet.