Internet Access

Some 18 days ago, I set up a contract with ATT to get internet access at home. Now, finally, it works. The level of incompetence that ATT demonstrated during this process makes me very happy --- if they ever decide to cut jobs starting with the least competent people in the company, it will be a long while before my research job is threatened.

The main issue was that they sent me a non-working modem, in the most basic sense: the power led didn't come on when I plugged it in (you get an idea of how much quality control is being done). To fix this, I had to assure a lady that I did check several power plugs before waiting on the phone for half an hour to talk to somebody, and then we counted together 30 seconds while I was holding the reset button pressed. When she was finally convinced the thing was broken, she told me the "replacements department" was closed at that hour, and I had to call the next day. (Some operators need to be specially trained to fill out the replacement form?)

After I went through the same routine the second day, the replacement department assured me that they would mail a replacement with overnight delivery. And that's exactly what they did, 3 days later. (I eventually got a tracking number from them, which tells me exactly when the mailing happened.) Somebody should explain that they could probably save money and time by sending things via regular mail, just promptly.

And then comes the most unbelievable part: the package had the wrong address! Yes, I mean the package from the phone company, which should know my address pretty damn well in order to activate my line and bill me. And yes, the package from the same company that had already sent me a modem at the correct address. I just can't believe that the guy at the "replacement department" has to type in my address manually, again!

Of course, the original delivery date had to be on a Friday, so I couldn't pick up the package from UPS until Monday... Hence the whole issue was only resolved today.

Updates

• US citizens ellected a professor instead of a military guy to run the country. Maybe there is hope after all.
  
  
• I am on the FOCS'09 PC, which basically means that the remaining 2 weeks until the STOC deadline will be crazy.
  
  
• As of this Monday, I finally started at IBM Almaden. (I had been stuck waiting for my work authorization for several months.) You can deterministically find me at IBM on Mondays, and probabilistically on other days. Finding me in space might be a bit difficult, since I greatly prefer the hills over my office.
  
  
• I am now physically at Berkeley, where I will be visiting each Wednesday and on other random days. I have a desk in Soda 645.
  
  
• The day before FOCS, I moved into an 18th floor apartment at the intersection of Market and 10th in San Francisco. The location is a compromise between many constraints...
  
  
• My commute plan (to IBM) is:
  
  1. use this to get to the train station (the English word is apparently "scooter", so I call it Vespa 1.0)
  2. take the Caltrain "baby bullet" (so called, because it travels slightly faster than the slowest trains in Europe, and decidedly faster than muels)
  3. ride a motorcycle (to be bought) for the remaining 12 miles to IBM.
     
     
• While you may hear me complain about IBM's location, I must admit that the benefit of a location up on a hill several miles from civilisation is that I share an office with 2 other people, and have a great view of the next wing of the building.
  
  
• My way to FOCS involved BART, Caltrain to San Jose, bus to SJC, flight to Santa Barbara, flight to LA, flight to New Ark, NJ transit to Trenton, and SEPTA to Philly. It all took a reasonable 16 hours, and cost under 200 (which is amazing given that I bought the tickets 2 days before, and important because unemployed people can't get their conference travel reimbursed.)
  
  

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.