‘Outsiders’ Crack 50-Year-Old Math Problem (2015)
quantamagazine.org
quantamagazine.org
That class, and the way he taught it, convinced me that advanced math, whilst hard for me, is not beyond my grasp or really that of anyone. It’s just a matter of breaking problems down into manageable chunks and recognizable sub-problems, a skill at which Spielman is especially adept.
I knew he was smart then (he had just received a $500k McArthur “genius” grant), but reading this article really put into perspective how effective he is and how lucky I was to have him as a professor. His same skill for breaking down problems that helped me succeed in his class seems to be the same skill that enabled him to solve this problem.
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
Perhaps the key to their success was typically programming work estimations ;)
More seriously, I think that if you think something is easy for you, or that you are almost there, you may be more willing to put in the necessary time, than if you knew it would take 5 years from the outset.
"Spielman realized that he himself might be in the perfect position to solve it. “It seemed so natural, so central to the kinds of things I think about,” he said. “I thought, ‘I’ve got to be able to prove that.’”"
Funny story is he “invented” this technique in his school days and only found out that it wasn’t standard during he Manhattan project when a colleague complained a problem was t tractable and Feynman went to the black board to illustrate the “obvious” solution.
Sometimes optimal solutions aren’t found because nobody bothered to look, assuming if they think about it at all that any remaining work must be more complex than the already known suboptimal solution.
This can be a wonderful habit, or it can create cranks. As you mention, Feynman used it to great success, but he was Feynman. I had a few classmates in graduate school—I nearly was one, until my advisor set me straight—who couldn't make any progress because they couldn't take any results for granted; they wouldn't do anything until they could prove everything. This is intellectually admirable, but a sure recipe for stagnation (at least for me and these classmates).
Doing this even after becoming a world famous physicist led to the Feynman Lectures in Physics - written as much for his own benefit as for his students. However, I am not sure he used this strategy when learning entirely new concepts the very first time.
It makes sense to do this as practice. To build new theoretical structures, building new constructions of the stuff we already know is a great way to sharpen a toolbox of problem-solving techniques and reveal potential shaky theoretical foundations.
Happy ground between 'must build stack myself' and 'too orthodox to ever question the masters'.
This is a fantastic summary. I like it a lot, and may steal it for future use.
>> Perhaps the key to their success was typically programming work estimations ;)
No, you should always normalize programmer estimates by increasing both the unit and the measure by one. So "a few weeks", say 4 weeks, will actually take: 5 months! So he still took 12 times longer than the properly normalized estimate! :-)
Just a thought.
A Masters, based on this view, is designed to instill expertise in a field's main body of theory and techniques.
Contrast this with say pure math, where (I believe) most students even at the strongest schools do not publish or even produce publishable research in their first few years.
I think it depends what you call "novel research". Most of the time, novel research means making a small contribution to an existing paper (and for a graduate student, the paper to extend and the contribution are usually suggested by their supervisor).
Another help: Start with a problem significant in practice. If get a solution with new, correct results, then can say that the results are significant because the practical problem was.
https://en.wikipedia.org/wiki/Credentialism_and_educational_...
There's a lot of low hanging fruit out there, but you still have to actually know how to find it.
it will always be hard to get to the frontier. but that path should be easy. we can get years and years of explorers by building good roads.
Cannot even rely on citation indeed as it is a common practice to cite papers from your surroundings without quality control. Or barely on topic.
Other sciences are much more "soft" and have error bars and such. Someone with a "lesser pedigree" just couldn't cope with the special sciences. Nor could they afford the lab.