Changes in TCS

At the first BAM, I got an idea of how little complexity theory has changed in three decades: after I described Morgenstern's lower bound for arithmetic circuits with bounded constants, Christos noted that he gave a talk about the same paper in 1978, when he was a postdoc at Berkeley. We still have no clue how to prove a superlinear lower bound in the unrestricted model.

At the same meeting, I got to observe a change in the people that define our community, a change that fed right into my anxiety that "Theory of Computer Science" is becoming "Theory." After I defined and drew a butterfly graph, I asked how many people have seen this before; some 3 or 4 people raised their hands (which drops to a very small number once you subtract Christos and Dick Karp). But when I asked who knew that "Fourier characters are orthogonal," all but one had their hands up!

I, for one, grew up thinking supercomputers were cool, and knew all about routing messages, before I learned about those "linear systems" that people apparently wanted to solve on big machines. And, yes, I am suspicious of people who had a "theory is cool!" moment before 100 "CS is cool!" moments.

Berkeley Algorithmists' Meetings

I am starting a new reading group at Berkeley. (Actually, I prefer the term "discussion group," since I was never too passionate about reading papers anyway; instead, I very much enjoy cafe-style discussion of open problems.)

For lack of a better name, this series will go by BAM (Berkeley Algorithmists' Meetings). Regarding coverage, I did not promise anything more specific than:

Since nobody can decide whether I'm doing complexity or algorithms, I will aim to keep this discussion group at the same level of ambiguity.

Presentations will transcend the boundaries of any single paper, as we will try to get a more comprehensive view of each topic, without getting bogged down in technicalities. We will talk amply about open problems.

I am hoping that all presentations will be transcribed as posts on this blog. Thus, feel free to request topics that you want to read about. You will get slightly less weight than the physical audience, but your comments will be heard.

The pilot meeting is this Tuesday, at 3:30pm. If you are in the area and would like to attend, check back tomorrow for the room details.

The topic for the first meeting is convolution and the FFT:

• how to think combinatorially about the FFT
• an Ω(nlg n) lower bound for arithmetic circuits with bounded coefficients [Morgenstern, JACM'73]
• an Ω(nlglg n) lower bound for offline range counting [Chazelle, STOC'95]
• discussion of open problems

Three Days in San Francisco

I started the week with a Misfits concert, those 31-year-old punk classics that have influenced all-time favorites like Slayer and Metallica.

Historical note: If the following are familiar to you...

• "Die, die, die, my darling..."
• "Here in this place lies the genie of death"
• "I got something to say: I killed your baby today"

... chances are it is the Metallica inflections that are now ringing in your head. However, it is worth remembering that these are originally Misfits songs.

I continued with Alistair Sinclair's "Mixing times for the solid-on-solid model". As usual, I think this is great theory, but not theory of computer science. (Here, Mikkel tries to make a similar point, cutting even deeper to define theory of computer science.)

Personal note: Attending such talks is always very interesting to me. In a short previous life, I was a Physicist (I even won 1st and 2nd prizes in the Romanian Physics Olympiad in '96 - '97). This left me with great physics intuition, but not that much mathematical intuition on how to formalize "physics proofs" (at that age, my appreciation of Math was very limited). It is very rewarding to catch up on the mathematical intuition, whenever I get a chance.

Finally, I had a chance to listen to some great music from Nels Cline and his band. This led to the interesting exercise of trying to triangulate Cline's heavy, academic jazz relative to black jazz and the Béla Bartók classical music.

The U.S. is a big country, but there are not many places where you can hear the Misfits, Sinclair, and Cline in a span of three days.

STOC

I decided yesterday not to submit anything to STOC, so I spent my most relaxing deadline day yet. For one paper, I found a deadly bug, while for another I found an improvement (moving it back to the column of things I need to think more about).

The main lesson for me was that there are limits to everything, and that dealing with an endless stream of stuff (from my defense, to writing a thesis, to visa issues, to searching for an apartment, to IBM sign on stuff, to paperwork for buying a motorcycle...) can really kill research.

Now I look forward to a year without deadlines (I am on the FOCS program committee). I hope to spend the first month catching up with things, and the rest doing what I actually enjoy doing, i.e. thinking about my problems. If this plan fails, I might have to elope to Africa again for a few months :)

As for this blog, I will probably get back to writing interesting technical stuff soon. I expect the non-technical stuff to be kept to a minimum. (For one, we've got too much blogging in the community, and I'm bored. Plus, I've felt disappointed with the TCS community for quite a while, and there's not much I can say in between lying and insulting some folks.)

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.)