Thursday, December 30, 2004

Complexity Year in Review

Theorem of the year goes to Omer Reingold who shows Undirected Connectivity in Logarithmic Space, settling the long-standing open problem. Also of note, Ran Raz's lower bounds on multilinear formulas and a series of paper extracting randomness from independent sources I had mentioned earlier as well as new improvements by Raz. We had many other great results throughout the year, check out the ECCC to sample many of them.

The National Science Foundation and computer science funding face a challenging future. We have seen the end of the ITR program that has poured needed money into IT research. CISE reorganizes (putting complexity theorists and numerical analysts into the same program for example) as they struggle to meet a new reality of CS funding. To add to the burden the NSF had an actual decrease in its funding for FY 2005.

The decrease in foreign graduate students as US schools made news over the past year. The difficulty in obtaining visas since the terrorist attacks in 2001 certainly play a role but I give more weight to stronger local alternatives manned by many of those foreign students we have educated over the last several decades.

We lost three prominent members of our community: Shimon Even, Carl Smith and Larry Stockmeyer.

Outside of complexity we had an election that divided this country (but not the scientists), the Red Sox winning the world series and an ongoing struggle in Iraq. Unfortunately the year ends with a terrible natural disaster and we all should support the efforts to help those affected recover from this tragedy.


  1. I wonder how the decrease in foreign students matches with the decrease in NSF funding? I think both are terrible losses, but I wonder what the net per capita funding effect is.

  2. Regarding the decrease in non-US students, I don't know what the reason is, but I doubt it's largely improved local alternatives.

    My local and completely unsytematic observations at the University of Queensland (UQ) are that:

    (a) The quality of non-Australian students applying at UQ has gone through the roof in the past few years. At least in my School (Physics, Mathematics and Earth Sciences), we've ended up where we're having to reject people who a few years back would have been shoe-ins in favour of people with even stronger records. I've little doubt that we're getting a lot of applications from people who formerly would have applied to (and been accepted by) the top US schools.

    (b) Our students seem to be increasingly looking to Europe or elsewhere in Australia rather than the US for grad school or postdocs. I realize it's anecdotal, but I keep hearing horror stories about experiences other people have had with US immigration since 911. Several times, I've heard these stories from people who say "I've decided not to apply in the US, since I heard that [insert horror story]."

    Michael Nielsen

  3. As you have mention the Red Sox winning the world series, you should have done the same to F.C.Porto :-) in 2003 they won the UEFA cup, and in 2004 the Champions League and the Intercontinental Cup :-)
    Luis Antunes

  4. The horror stories cited above are not anedoctal: I know people studying here in USA that went to their home countries for vacation and could not come back. You end up like a prisioner if you don't want to take risks. Nobody deserves his kind of treatment, and I am not surprised that people are looking for something else.

  5. Here's to hoping that TV show "Numb3rs" isn't total hogwash.