[Computational Complexity] 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.
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.
Posted by Lance to Computational Complexity at 12/30/2004 11:33:26 AM