Computational Complexity

Tuesday, December 30, 2003

 
End of Year Thoughts

Posted by Lance

We had another solid year for theoretical computer science and computational complexity with many exciting results such as the polynomial algorithm for perfect graphs developed in a series of papers by Chudnovsky, Cornuéjols, Liu, Seymour and Vuškovic. We also saw a number of strong papers in derandomization, extractor construction, dimension reduction and many other areas of complexity.

In 2003 we celebrated the 100th anniversary of the births of Alonzo Church, Andrey Kolmogorov, John von Neumann and Frank Ramsey, mathematicians who work played a big role in complexity. Next up, Kurt Gödel in 2006.

Trends to watch for in 2004:

• How will the reorganization of CISE and the end of the ITR affect NSF funding for theoretical computer science?
• Will a hopefully improving economy push universities to increase their resources in computer science?
• What trends will we see in recruiting this year? More and more Ph.D.'s seem to prefer postdoc positions though the number of these positions continue to decrease, especially in industry.
• How will the choice of the US president in 2004 affect the future of scientific research in America? A critical question, but not one that a journalist will ask in any debate.

Happy new year to all! May we prove P≠NP in 2004.

6:53 AM #

Comment Feeds: This Post All