For SODA attendees

Howard Karloff asked me to post the following:


Outing To See "South Pacific" on Broadway During SODA'09

I have reserved, for SODA attendees and their friends / spouses / significant others, 50 tickets in the loge section at Lincoln Center for the 7:00 PM, Tuesday, Jan. 6 show of "South Pacific," so popular a show that already both Saturday Jan. 3 performances are sold out. If you want to buy one or two tickets, send mail to howard@research.att.com with "South Pacific" as the subject field, specifying the number of tickets you want in the body of the e-mail. Tickets will go to the first SODA attendees who pay by credit card via PayPal. I'll send instructions by e-mail. The tickets are $120 each--the face value is $115, and the extra $5 is to cover the PayPal fee--and are NONREFUNDABLE: once you pay, there will be no refunds. However, I imagine someone at SODA, some random theatre-goer, or an ebay user would be thrilled to take tickets to such a popular show off your hands.

So, please, start those e-mails coming. Should the demand far exceed 50 tickets, I may arrange a second outing, to a different play, either Saturday or Tuesday.

A few reminders: "South Pacific" starts at 7PM, not the typical 8PM start time, on the last day of SODA. The venue is Lincoln Center, not in the heart of Broadway. Once you pay, there's no backing out.

See you in New York in a couple months!

Howard Karloff

Cheaper Arguments

A New York Times opinion piece spends two pages bashing classical economists for not understanding the computational aspects of economics and phase transitions. But who comes to the rescue? It is not theoretical computer scientists, with all our love of phase transitions and computational economics --- it is the damned PHYSICISTS!

Of course, 90% of this post is meant as a joke :). But I would like to point out that 10% is not.

We have witnessed a trend in TCS to focus on the philosophical implications of our work. But it should be obvious that those same philosophical implications can be obtained through cheaper arguments by other fields. When a new proposal to deregulate the Illinois energy market is made (to take the Times' example), who will be the first to point out a potential issue? The Physicists / whoever decides to run some simulations of the new market over the weekend? Or the TCS researchers, who have spent a month proving that a phase transition occurs, assuming that their precise model makes sense?

The point is that if you only want philosophical implications, a solid proof is not necessary ("Dear members of the Illinois Congress, I know you took the issues pointed out by our colleagues in the Physics Department very seriously, but you should realize they never had a complete proof before!"). Think about how hard it is to prove some things about random graphs or random SAT, even though they are obvious from experiments.

I would hate it if we became so engaged in the market for philosophical implications, that we would sacrifice our core TCS values to avoiding always coming in second place.

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.