Algorithms for Farey Sequences

I recently uploaded the final version of my paper with Jakub Pawlewicz, due to appear in Algorithmica. The paper has a sparkling story (from my own perspective, at least) that should be told.

Starting research. In my glorious freshman year at MIT, when I was working on P vs NP and convincing random professors to pay me, I was trying to understand what research meant. This was not an easy task, since the closest thing I had to a mentor was Alex, who had just started research the previous summer. (Erik didn't quite qualify, since my second meeting with him was 3 or 4 months after he had started paying me.)

In any case, the lesson that I managed to absorb from the environment was that you're supposed to ignore all the cool stuff that's in books, and come up with new algorithms that were not known before Earth was graced with your existence. Then, you write papers describing these new algorithms, and you join the cool club of people who are in the business.

Judging that I might not have a paper on P vs NP soon, I decided to start looking for other problems, and I remembered a book on algorithms that I had read in middle school. This was the kind of book that Romanian associate professors write (because you need to have a number of books before becoming full professor): it contained all sorts of unrelated random topics that the author had come across since writing his previous book. Next to planar closest pair in O(n lg n) was a discussion of Farey sequences and an optimal algorithm for generating them. (See my older post for a definition of Farey sequences and a cool application.)

As soon as I remembered this algorithm, I saw potential for a "result": if we ask for just the kth element of the sequence, can we obtain a sublinear algorithm that doesn't generate the whole sequence? Here "sublinear" means better than O(n²), because the Farey sequence of order n has O(n²) elements. Of course, there is no real motivation to this problem, but this didn't bother me at the time.

A result. Soon enough, I had an algorithm running in O(n lg n) time, and summer was coming up. I was a member of the Scientific Committee of the Balkan Olympiad in Informatics happening that summer, so I assigned the problem in the competition. (Don't worry, I'm not a big fan of assigning "unrealistic" problems, so my time bounds allowed for an easier and less efficient algorithm that I had discovered at first. Even so, it turned out to be the perfect "hard problem," that required some unusual ideas and was solved only by a couple of people.)

Returning to "research mode," I used Google to check if my result was known (seemed not), and discovered the Algorithmic Number Theory Symposium (ANTS). I then wrote a paper with my ex and sent it to the conference. Looking at it in retrospect, it looks like a very childish paper. Nonetheless, Math conferences are not competitive, and it got accepted. The referee report contained the best polite equivalent of "the authors don't know what the heck they're talking about" that I have yet seen. It read: "The authors unintentionally hide the fact that the quantities A(.) that they define in the course of the solution are actually the Mertens function."

At the conference, people were entertained by the paper. They asked if we could get an O(poly(lg n)) algorithm on a quantum computer (I maintain my original response: What??), and asked whether we could count primitive lattice points inside polygons efficiently. A primitive lattice point is a point (x,y) where x and y are coprime; the Farey problem can be reduced to counting primitive lattice points in a special class of triangles.

I kept thinking at odd times about getting a faster algorithm, and about counting primitive lattice points in larger classes of polygons. I had a complicated algorithm running in O~(n^3/4) time, and some results for primitive lattice points. However, by then I was engaged in doing research on more high profile problems, and I could never get myself to write another paper on this topic.

Shock and awe. As it turns out, not publishing a follow-up was a brilliant decision. Last year, Krzysztof flew to California for my birthday party. Before the discussion got elevated by consumption of alcoholic beverages, he managed to tell me that Jakub Pawlewicz, a student at his alma mater in Poland, had written a follow-up paper about algorithms for Farey sequences. As it turned out, Jakub had a very nice algorithm achieving O(n^3/4) time.

At first, I was amused and surprised by the fact that someone had actually picked up the problem! Then, I found out that the paper was accepted to ESA'07, and I was even more surprised (I had never considered mainstream CS conferences for such a problem). But only when I found out that it got the Best Student Paper Award at ESA, was I totally blown away!

Now, had I published my follow-up paper, then almost certainly history would have been different. I would have never found out that the best student paper at ESA can be won for a follow-up paper to something I did in freshman year! As you can imagine, this made for some entertaining pub discussions, like:

Admired top-notch researchers get research awards. Also, there are some godly figures, so established, so influential, that research awards are being handed out for works in the fields that they created. But who else can claim that research awards are being given for work in a field that they introduced in freshman year? :)

The aftermath. Despite the entertainment value, getting scooped was not entirely a nice feeling, since I am, like any researcher, a bit attached to my results. My consolation was that Jakub is also a former medal winner at Informatics Olympiads (IOI and CEOI), so at least I had been scooped by a very worthy person.

Fortunately, I lucked out for the second time. I asked Jakub for the paper, and his solution was so clear and elegant, that I found it easy to plug my old ideas into it. Within the hour, I saw how to improve his algorithm to O(n^2/3) and was writing him an email about it. Yes, I imagine he hates me for this episode :)...

In the end, we merged the two results into the paper I mentioned in the beginning, which appears in the Algorithmica special issue for ESA'07. This was the ideal outcome for me: I got my ideas published with minimal effort, and with a bonus story.