[Computational Complexity] STOC and More
- The Snows of Maryland are keeping Bill away from this blog again. Here in Chicago we deal with snow (and even earthquakes) in stride--my kids still have yet to have a snow day this year.So I'm back for a day to bring you some news.
The STOC accepted papers list is up, Shiva Kintali is collecting PDF pointers and Noam Nisan pulls out the AGT papers. Lots of goodies this year. You can change base without losing space (love that rhyming title), save space with algebrization and adding quantum to interactive proofs keeps it in PSPACE.You just don't see a lot of BLANK is computable results in STOC these days so nice to see a paper with BLANK=HOM=Is a given homomorphism of a regular languages expressed by a tree automata itself regular? Sound technical but it actually has connections to XML.
So come to the conference. As Bill mentioned earlier, there are travel awards available for needy students even if you don't have a paper. Apply for visas if needed as soon as possible (click here if you need a letter). The Complexity and EC conferences will both be held also in Cambridge immediately following STOC.
The other big news, according to the Center for Computational Intractability, theory's own Subhash Khot wins the 2010 NSF Waterman award. The NSF gives away only one of these awards each year to a young researcher across all of science.
We are entering CS award season so keep an eye out for the Knuth Prize (the Knuth Prize Lecture will be at STOC), the EATCS award and Gödel Prize (presented at ICALP), Turing and other ACM awards. The SIGACT Distinguished Service award nominations are still open until March 1st which will also be presented at STOC.
Posted By Lance to Computational Complexity at 2/10/2010 08:58:00 AM