Macs and Romanian keyboards

As I found out the other night, the effects of beer on laptops are not nearly as positive as on researchers.

Having to get a new laptop, I decided to bring a Mac "into the family." Everything seems great so far --- it didn't take more than a day to figure out the basics and install several Gb of software essentials (starting with MacTex and Aqumacs Emacs, on to Unison, and recovering all my files from the MIT servers).

Of course, the transition is helped by my insistence on pretending that my Windows was actually Unix (via Cygwin). It feels good to return to a true Unix (after 6 years or so) and stop the pretending. The Mac's superiority seems undeniable (it is Unix, and therefore strictly better than Windows, and it has a wonderful graphical interface, significantly better than X).

Keyboard layouts. The one thing that MacOS did lack was an ergonomic Romanian keyboard layout. As I mentioned before, I find the standard Romanian keyboard horrible, since it banishes some of the most useful Romanian characters (ășțîâ) to the end of keyboard, where they replace other useful characters ([, ], :, etc). The solution is to put the useful Romanian keys on the Latin letters that are not normally used in Romanian (q->ă, w->ș, x->â, k->î, y->ț). To get the original Latin key, press Alt+key. The mapping may seem ad hoc at first, but my experience is that you learn in within minutes, because ț is right next to t, ă right next to a, ș right next to s, and î right next to i. The credit for the original idea goes to ErgoRomanian, a keyboard layout for Windows.

Download. To get what I wanted, I hacked the standard US layout on the Mac. Here is the resulting Romanian Ergo keyboard layout. For the Romanian flag in the menu bar, also download this icon.

Installation:

1. Download the files and move them to ~/Library/Keyboard Layouts/
2. Log out and back in
3. Go to System Preferences > International > Input Menu. Look for Romanian Ergonomic, and check it.
4. [optional] Click on Keyboard Shortcuts, disable the Spotlight check buttons, and enable the Input Methods ones. This allows you to switch keyboard layouts by pressing Command-Space.
   

Alternative spelling. Admittedly, the one slightly annoying feature of this layout is the x->â replacement, since x does sometimes get used in Romanian. But if you did not adopt the spelling recommendations of the Romanian Academy (i.e., if you spell pîine instead of pâine), you shouldn't have a problem, since â is a very uncommon letter for you. I made an alternative Ergo-X layout, in which x remains the default, and Alt-x gives you â.

Download: the Romanian Ergo-X keyboard layout, and its icon. Follow the same instructions as above.

As always, please report any bugs or suggestions.

Tango trees

At the request of Sanjeev Arora, I prepared the following lecture notes about O(lglg n)-competitive binary search trees (our Tango trees).

The main innovation is the proof of the Wilber-1 bound. As opposed to the somewhat hairy proof in Wilber's paper and in our paper's appendix, I show Wilber-1 by arguing about the problem geometry and maintaining partial sums (forget trees!). Hopefully this gives a more intuitive proof. In any case, it shows the students something very important in its own right.

If you read these notes, I am interested in anything you have to say, including things you didn't understand, or suggestions for clarifications. 

SODA (II)

The SODA accepted papers, with abstracts, can be found in this text file, or as a PDF file (curtesy of Suresh). 

Each year, looking at the SODA list of papers makes me depressed. It is hard to see --- among all the quantum dogs and ponies exhibiting Braess's paradox in stochastic networks with piecewise linear costs --- how we are working to understand the fundamental questions about computation.

What we're missing badly is innovation in solution space, not innovation in problem space. Remember this when you sit down to work on your next paper.

SODA

I am happy to report that our SODA submission on The Geometry of Binary Search Trees was accepted.

This paper works on the old question of competitiveness in the binary search tree model (some old posts of mine: 1, 2, 3), and makes some progress that is not easy to quantify. We propose a geometric interpretation of the problem, which seems to eliminate all the messiness attached to trees, and makes previous lower bounds (the Wilber bounds) very clear. The geometric view is somehow very appealing; a referee called this "an amusing paper" (in a very positive comment), and I will happily agree to this description.

Unfortunately, our work does not lead to a new upper bound, though it leads to a reformulation of an old conjecture. Joan Lucas and Ian Munro independently introduced a natural offline greedy algorithm, which they conjectured to be an O(1) approximation. Speaking informally, the prevailing opinion seemed to be that this had to be an O(1) approximation (modulo technical details in proving it!), but the really interesting question was to show an online O(1)-competitive algorithm. Well, our work shows that this view was wrong: we can make the Lucas-Munro algorithm online, with a constant slow-down.

Thus, if the conjectures of Lucas and Munro are correct, this tree achieves dynamic optimality. This is the first proposal for dynamic optimality after the famous splay trees that started the whole field.

Our geometric view also has consequences for the lower bounds (which are crucial if we want constant approximation). The only known lower bounds were Wilber's 2 bounds from FOCS'06. Wilber's first bound was used in our O(lg lg n)-competitive algorithm. Though Wilber conjectured that his second bound is stronger, we still have no idea how the two compare.

In our framework, Wilber's bounds are special cases of a very natural class of "cut bounds," and they get very simple descriptions. Instead of comparing the two Wilber bounds, we now face a broader question of finding the best possible cut bound. We solve this by proposing a new lower bound that is shown to be an O(1)-approximation to the best cut bound. This supersedes Wilber's results, though we do not know that it is strictly stronger than Wilber's bounds.

FOCS Best Student Paper

It seems I won the best student paper at FOCS. Yay. I suppose having 3 of the 5 student papers finally did the trick. :)

The prize goes to Succincter, which seems to make it the first "best student paper" at STOC or FOCS given for a data structure. I can't remember any "best paper" given for a data structure either, though I cannot find these lists. My special thanks for people in approximation algorithms, hardness of approximation, game theory, coding theory, complexity theory, quantum computing, and cryptography for making this possible :)

All in all, I think "Succincter" is a decent pick. It's a paper that might have a big impact on how we think about succinct data structures in the future. It's also a problem that's been pestering me since June'05, when Seth described it to me during my visit at Max Planck, Saarbrücken. (Thanks, Seth!) Finally, it got some brilliant reviews, including one that only said "Yes" and one calling the question a "target known for at least 2 decades".

On this last point, the key lesson seems to be that you should write your introduction in the last 45 minutes before the deadline, after sleeping 2 hours/night for 3 days in a row. After an incoherent introduction, the reviewers will feel the need to sing their praise of the paper. By contrast, as I learned from the reviews of another student paper, it is "incredibly poor taste" to say in your introduction that your results are clean, or, god forbid, explain how they simplify a proof by some other people.

Olympics

It's been a bad olympics year...

In rowing/women's eights, Romania got a scandalous Bronze, breaking a streak of Golds lasting since '92. It was also the first time since 1976 when they didn't get Gold or Silver.

Gymnastics disappointed badly, with nothing more than a Bronze in women's team and a Gold in women's floor (compared, say, to 4 Golds + 3 Silvers + 3 Bronze in Athens 2004).

Handball is bound to finish on the 7th or 8th place. As a Romanian editorialist aptly noted, the intensity of online swearing that this has produced was previously reserved for soccer.

But above all, Romania got 1 Gold, 1 Silver, 1 Bronze (and 1 nothing) in the IOI happening this week. While the team deserve our warm congratulations, we must be honest and say that this is a disappointing result. In my years, we got 2 Golds + 1 Silver + 1 Bronze several times, and we kept thinking that we should do better...

Nevertheless, our IOI performance was stellar compared to what Romania did in the IMO. For a country used to perfect scores and top participants, getting no Gold in IMO'08 is outright abysmal.

Romania has to get its act together before it's too late. The one thing that we cannot afford to learn from Europe is their acceptance of mediocrity. It is not particularly bad being a mediocre Westerner, in no small part due to a pervasive feeling of entitlement. But Romanians share no feeling of this sort. In the global conscience, the mediocre Romanian is the strawberry harvester of Spain, the construction worked of Israel, and the purse snatcher of Italy. Without a constant flow of outstanding results, these images will define how the nation thinks of itself.

Puzzles

I have a deep aversion of the "puzzle" concept. Delving into a problem is a very taxing process for me, and I just refuse to do it for the gratification of solving something that people actually expected me to solve fairly quickly. My brain can only internalize so many concepts in one day (like, maybe 2), and I can't waste this resource just so I can feel good about solving a small little problem.

Thus, when I read a recent blog post about how a theorist and two mathematicians spent their time after meeting randomly on a bus tour, I felt as if I was reading about an entirely outlandish experience, and I couldn't stop thinking "Why the heck... I can't believe they actually did this..."

Of course, I reminded myself that many people seem to love puzzles. An old friend used to say that "the brain doesn't rest, it atrophies." My adviser's office is the nightmare of any claustrophobic person: it is overflowing with small physical puzzles. I often fidget with them when I'm talking to Erik. The fact that I usually "solve" these problems by 5 minutes of random hand movement only confirms that I should never think about such things :)

My brain applies the same self-defense strategies when it comes to olympiad problems, which is why you don't see too many olympiad problems on this blog. When I originally read the Dwarves problem, I said "DP" (dynamic programming) and stopped. Only the next day, when 3 IOI guys claimed they really couldn't solve it, did I persuade myself to think about it...