Thomas Lehrer is a mathematician and co-author of the paper, ``The Distribution of the Number of Locally Maximal Elements in a Random Sample.'' It was published in 1957 in the journal Annals of Mathematical Statistics, and had the distinction of being reviewed in French. The paper after it in the journal was written by John Hammersley, Ken's Doktorgrossvater. Another paper co-authored by Lehrer was reviewed by Richard Hamming.

Today we do a brief review of results and ideas from 2012.

Lehrer's paper is interesting because a problem couched in the language of distributions of real numbers becomes a simpler one about permutations $latex {\pi}&fg=000000$ of $latex {1,2,\dots,n}&fg=000000$. Namely, say an integer $latex {m}&fg=000000$ is a ``$latex {k}&fg=000000$-peak'' of $latex {\pi}&fg=000000$ if it is the maximum of some run of $latex {k}&fg=000000$ consecutive entries of $latex {\pi}&fg=000000$. The number $latex {n}&fg=000000$ is always a $latex {k}&fg=000000$-peak, but $latex {n-1}&fg=000000$ might not be if it is toward one end of $latex {\pi}&fg=000000$ with $latex {n}&fg=000000$ nearby. There must be at least $latex {\lfloor n/k\rfloor}&fg=000000$ different $latex {k}&fg=000000$-peaks, but can be as many as $latex {n-k+1}&fg=000000$ in the case of the identity permutation. The paper gives recurrences and generating functions for the number $latex {f_k(n,i)}&fg=000000$ of permutations having $latex {i}&fg=000000$-many different peaks. Is this useful to you? That's our point---you never know in a given year exactly which work might be useful in later years.

Lehrer is perhaps better known as a writer and performer of comical satirical songs. His work for a TV show, ``That Was the Week That Was,'' became the 1965 album, ``That Was the Year That Was.'' He or we could riff on the Mayan Apocalypse as the ``year that almost wasn't,'' which expresses a little of our dithering on how to review 2012. Anyway, briefly, this was the year that was.

Best?

I (Dick) am not sure what I would select as the best result of the year, and neither is Ken.

The best claims of the year were as usual these two: (1) that P equals NP, and (2) that P is not equal to NP. We were not convinced any were correct in 2012, but there's always 2013.

The best math result must be the claimed proof that the ABC conjecture is true. But alas we have no idea---here `we' refers not only to us but even to the experts---no idea at all yet if it is correct. Perhaps in 2013 we will find out if it is correct. Perhaps not. We will see.

In their year-end review, Lance Fortnow and Bill Gasarch chose the paper on barriers to linear programs for the Traveling Salesman Problem which we covered recently here. They mention as runners-up some other papers, including one on the power of resolution, and covering them may become New Year's ``resolutions'' for us. Looking ahead, four papers that catch our eye from those accepted to next week's ``Innovations in Theoretical Computer Science'' conference are:

``On the Possibilities and Limitations of Pseudodeterministic Algorithms,'' a followup by Oded Goldreich, Shafi Goldwasser, and Dana Ron to Shafi's random-function model which we covered last May.
``Evasiveness Through Circuit Lens,'' by Raghav Kulkarni. This paper makes advances on the evasiveness conjecture, which we mentioned here.
``An Energy Complexity Model for Algorithms,'' by Swapnoneel Roy, Atri Rudra, and Akshat Verma. Roy is a student of Atri's in Ken's department.
``Making Evolution Rigorous - The Error Threshold'' by Nisheeth Vishnoi. OK, maybe we are biased since Nisheeth was a student of Dick's, but Ken chose the paper because he just wrote about evolution.

Open Problems

What was notable for you in 2012?

Happy New Year from Dick and Ken.