What Is Best Result Of The Year?
What do you think?
Charles Lindbergh is famous for his solo non-stop flight that left Roosevelt Field in Long Island on May 20, 1927 and arrived the next day at Le Bourget Field in Paris. He covered a distance of almost miles, which is a long flight even for today’s jumbo jets. He did it in his single-seat, single-engine, Ryan monoplane called the “Spirit of St. Louis.”
Today Ken and I want to talk about not about making solo flights, or air travel, or jumbo jets; but about selecting the
“Person Of The Year.”
Lindbergh helped indirectly create the “Man of the Year” concept at Time Magazine. Toward the end of the year 1927 the editors at Time wanted to remedy an error they made earlier by not having Lindbergh’s historic flight pictured on their magazine’s cover. So Lindbergh became the first “Man of the Year” of Time magazine. This clever solution started their tradition of selecting what is now correctly called the Person of the Year, where Time features:
A person, group, idea or object that “for better or for worse \dots has done the most to influence the events of the year.”
The usual winners are leaders of countries, although in 1960 science was selected and represented by a group of scientists:
George Beadle, Charles Draper, John Enders, Donald Glaser, Joshua Lederberg, Willard Libby, Linus Pauling, Edward Purcell, Isidor Rabi, Emilio Segrè, William Shockley, Edward Teller, Charles Townes, James Van Allen, and Robert Woodward.
Over two decades later, in 1982, “The Computer” was the winner.
We would like to have your input on who or what should be the “Person Of The Year” winner from the view of theory, and more widely, mathematics. We have some ideas that we will share, but would love to get some additional input. The winner(s) will be determined by a complex system of voting—forget Arrow’s Impossibility Theorem—and later this month we will announce them. The first prize is a free subscription to Gödel’s Lost Letter, and the second prize is a fifty percent discount on a subscription.
Some Candidates From Experts
We have directly asked a few experts already. Both Paul Beame and Avi Widgerson independently selected the following results on constant depth circuits. We quote Paul:
I think that the biggest complexity results of the year were not contained in a single paper. It is the chain of papers on algebraic complexity which show that arbitrary algebraic circuits can be reduced to homogeneous depth 3 formulas of restricted size and fan-in, and that this simulation is tight up to constants in the exponents. This includes several papers including the following 2 papers. These are deserving together but there may be another to include.
Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi, Approaching the chasm at depth four, in Conference on Computational Complexity, IEEE, 2013.
Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi, Arithmetic Circuits: A chasm at depth three, in Foundations of Computer Science (FOCS), IEEE, 2013.
Ravi Kannan suggests the co-winners of the STOC 2013 Best-Paper Award: Ken Clarkson and David Woodruff for their paper Low Rank Approximation and Regression in Input Sparsity Time.
Here are some of our candidates.
Vladimir Voevodsky: For the new approach to mathematics in his paper, Univalent foundations and set theory. We have discussed this lightheartedly, but still intend serious treatment as time allows.
Yitang Zhang: For his unexpected and wonderful result on prime gaps that shows an almost twin prime conjecture is true. See this for recent results and improvements on the original paper.
Shinichi Mochizuki: For his claimed proof that the ABC conjecture is true. This is a continuation from last year, when we discussed it, but the efforts by the mathematical community to grapple with the heft of this new work have continued all this year.
Atri Rudra and Mary Wootters: For their result, Every list-decodable code for high noise has abundant near-optimal rate puncturings.
What sets this result apart from the large literature on list-decoding is that it is combinatorial. Perhaps the reason not much progress was made for years was because people were trying to prove a “purely algorithmic” version of this result. Atri tells me that
I don’t think the statement of the result is surprising: many folks, have believed that such codes should be list-decodable beyond the Johnson bound.
The fact still seems quite neat, in my opinion.
A Non-standard Candidate
How about our friends at Wikipedia? They might be a good choice for “Person” of the year. We use them all the time here at GLL. And they are trying right now to raise some money—maybe we could all help?
Who or what would be your choice?