Skip to content

That was, that almost wasn’t?

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 Doktorgroßvater. Another paper co-authored by Lehrer was reviewed by Richard Hamming, of Hamming distance fame.

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

Lehrer’s joint paper is interesting because a problem couched in the language of distributions of real numbers becomes a simpler one about permutations ${\pi}$ of ${1,2,\dots,n}$. Namely, say an integer ${m}$ is a “${k}$-peak” of ${\pi}$ if it is the maximum of some run of ${k}$ consecutive entries of ${\pi}$. The number ${n}$ is always a ${k}$-peak, but ${n-1}$ might not be if it is toward one end of ${\pi}$ with ${n}$ nearby. There must be at least ${\lfloor n/k\rfloor}$ different ${k}$-peaks, but can be as many as ${n-k+1}$ in the case of the identity permutation. The paper gives recurrences and generating functions for the number ${f_k(n,i)}$ of permutations having ${i}$-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 of 2012?

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 Both Ways?

Looking ahead and behind, Janus-style, four papers that catch our eye from those accepted to next week’s “Innovations in Theoretical Computer Science” conference are:

1. “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.

2. “Evasiveness Through Circuit Lens,” by Raghav Kulkarni. This paper makes advances on the evasiveness conjecture, which we mentioned here.

3. “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.

4. “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.

Advertisements
10 Comments leave one →
1. Andy D permalink
December 31, 2012 8:00 pm

Nice… “There must be at least X different k-peaks” –> “at most”, right?

• December 31, 2012 10:27 pm

Disjoint runs have different peaks, so “at least” —?

• Andy D permalink
January 3, 2013 2:31 pm

Thanks, misunderstood the definition.

2. Javaid Aslam permalink
January 1, 2013 2:58 pm

[On the correctness of claimed proofs] Yes, of course, … “there’s always 2013” (and 2014, 2015, …).

I wonder how such an artificial labeling of the time has acquired such a great importance throughout the world. Of course, there needs to be a common clock to synchronize various transactions.
Anyway, happy (artificial) New Year to Dick, Ken and all the readers!

• January 1, 2013 6:47 pm

Any labeling of the time would be artificial. So, we select one that kind-a fits the number in a revolution around the Sun. Definitely an improvement from the Julian calendar, this one is (algorithmically) simpler, since it requires a single leap year to correct itself. Quite efficient for its time, I dare to say.

Now, as to why we celebrate this event? One part is human nature, specifically each one individually is celebrating that we are still alive, so our loved ones. You would celebrate (in one way or another) a milestone reached in a significant project or in your career. In life, one needs those ”artificial” milestones. You could say this part is a celebration of the present, people forget their problems for just a night and get together with family and friends to celebrate. Coming from a Greek Orthodox background, this is very evident. The equivalent of St NIck is st. Bill (see http://en.wikipedia.org/wiki/Basil_of_Caesarea). Although I no longer live in Greece, I was told by many friends and family that “at least we’ve got New Year’s Eve” and that “we’ll try to celebrate despite the problems”.

The other part relates more to the past. One sits down and contemplates over the events that transpired during the year. Sometimes the scale might tip one way or another, but still one can find comfort in the things that were good. This also relates to thinking about the future; perhaps one can change its habits (the famous New Year’s resolutions) or find a way to deal with problems that just happened.

So, although I agree with you that the labeling is artificial, this does not necessarily imply that there is no meaning in celebrating it.

• Javaid Aslam permalink
January 4, 2013 1:29 am

Thank you chazisop for providing these details on the importance of “New Year”. Hope it does make some of us see it with a new perspective.

• January 2, 2013 4:31 am

this comes from what in neurobiology is called “fire together wire together” principle.

3. January 2, 2013 1:28 am

It appears that Congress has just discovered the Fuzzy Fiscal Cliff.

4. Serge permalink
January 2, 2013 5:41 pm

> “An Energy Complexity Model for Algorithms,” by Swapnoneel Roy, Atri Rudra, and Akshat Verma.

This extended notion of algorithm takes into account the energy spent at running time. I think it could become the missing link between math and physics and help break some undecidability in complexity theory.

Happy new year to all!

5. iengiregibiegeinkw permalink
January 5, 2013 10:17 am

Title reminds me of (TW)^3 That Was The Week That Was, a 1960s television program: http://en.wikipedia.org/wiki/That_Was_The_Week_That_Was