This year's STOC was in Chicago as most of the readers of this blog already know. It was the first time in Chicago for me. The hotel was in downtown right across from Grant Park near Lake Michigan. I went early on Saturday and had a chance to walk around and check out the Blues Festival in the park and walked the Magnificient Mile. Didn't have much time to do anything else touristy but had a very positive impression of the city. Maybe I should also visit during the winter to have a balanced view!
I felt that the papers in this STOC were particularly good. In addition to the usual breadth of topics, several papers in each topic were quite interesting. The two best award papers and the two best student papers were very well received.
Best Papers:
* Multilinear Formulas for Permanent and Determinant are of Super-Polynomial Size, by Ran Raz.
* Expander Flows, Geometric Embeddings and Geometric Partitioning, by Sanjeev Arora, Satish Rao, and Umesh Vazirani.
Best student papers:
* Spectral Partitioning, Eigenvalue Bounds, and Circle Packings for Graphs of Bounded Genus, by Jonathan Kelner
* Lower bounds for local search by Quantum Arguments, by Scott Aaronson.
Interestingly there was one algorithms paper and one lower bounds paper in each category. Algorithmic game theory, quantum algorithms/complexity, and sub-linear time algorithms (including property testing) are still the relatively new topics along with the more established areas.
The invited talks reflected the invasion by the new areas. The most interesting of the invited talks was by Avi Wigderson who was asked by Laszlo Babai to comment on whether theory of computing is still a unified discipline given the many diverse sub-areas that are represented at STOC/FOCS. Avi gave a very nice talk on this. He showed how communication complexity is central to many of the topics. He also connected interactive proofs to many areas and finally concluded with what he thought was the glue between the areas. He promised to put up his slides on his web page soon and you can see them for yourself (ed:
Most of the Business meeting was taken up by the discussion on moving the STOC special issue from JCSS to other journals. You can read more about this on Lance Fortnow's and Jeff Erickson's blogs. I am all for moving away from for-profit journals (especially Elsevier and Kluwer) to either society journals (ACM, SIAM, IEEE, Math Programming, INFORMS etc) or free electronic journals. Laszlo Babai very recently started a new free electronic journal ToC (Theory of Computing). With several very highly respected journals such as JACM and SICOMP available as society journals, will authors send their good papers to ToC? Or will this journal turn out to be like the Chicago Journal of TCS that was started by Babai many years ago and failed to catch on? I think times have changed and there is a higher probability for ToC to be successful. One thing that did bother me was that Babai chose to have most of the STOC'04 committee (of which he was the chair) as editors. The STOC'04 committee is filled with many fantastic young researchers, however some of the comments that Babai made and the way he went about choosing the editors makes one feel that ToC is his own show. In my opinion a respected journal should have a certain reputation that is independent from the editor-in-chief even though the editor-in-chief is well known and respected through out the community. I wish the best for ToC and I hope the editors lead the way in making it a success.
STOC 2005 is in Baltimore and there was a bid from U. Washington faculty Paul Beam and Anna Karlin (delivered by Venkat Guruswami) to host STOC 2006 in Seattle. Vladen Koltun compared the registration fees and hotel rates at STOC with those of SoCG and was wondering why we don't make more of an effort to make the whole thing cheaper. This issue keeps coming up but people ignore it - my take is that the people who care about it the most are not present at the business meeting! Another potential reason is that we have several conferences (at least three major ones, STOC/FOCS/SODA) each year and it is difficulty to find volunteers to make all this work out cheaply. That brings up the topic of the next conference, FOCS 2004, to be held in Rome, Italy. The accepted papers list will be out soon, June 25th according to the call for papers.
Another post will detail some of the papers and ideas that I liked the most at STOC.
No comments:
Post a Comment