[Computational Complexity] FOCS Part I
- Some thoughts from the FOCS conference in Las Vegas. One result I hadn't seen before I heard people excited by, Determinant Sums for Undirected Hamiltonicity by Andreas Björklund, giving an O(1.657n) algorithm for testing Hamiltonian Graphs beating the O(2n) bound of Bellman and Held-Karp from the 60's.I spend much more time hanging in the halls than attending talks. And much of the hall discussion focused on the Simons Institute whose letters for intent are due Wednesday. Most major theory groups seem to be putting together a letter, the interest is in what consortiums are forming, i.e., how are the theory groups being partitioned. Various conjectures about what the Simons Foundation is looking for. For example, will it help or hurt to already have a strong center for theory? What is the right balance of "core theory" and connections to other fields? Should be interesting to see which groups make it to the second round.Wherever this institute ends up, if run well it will immediately become a major influence in our community. Luca made a good point, that even this process where we all talked to our deans and other administrators about the proposal, helps to sell the importance of theoretical computer science to academic leaders.I won't give the blow by blow at the business meeting, Suresh already did so on his Twitter. I watched Suresh type furiously into his phone two rows ahead of me and see what he typed immediately on my iPhone. Cool.This will be the last FOCS with paper proceedings. Luca Trevisan asked some questions about moving to a larger PC or allowing PC members to submit but no one took the bait for a discussion.The biggest issue came from Dmitry Maslov from the NSF. The Algorithmic Foundations program that funds core theory has one of the highest acceptance rates at the NSF. With the complete turnover of NSF leadership, there is a concern that some might thing theory is over-funded. The CATCS committee is working to educate the new NSF directors that theory funding is going to strong proposals but still it would help to submit more proposals to bring down the rate. Large and small proposals are due soon so submit early and often. If you don't get funding, thanks for taking one for the team.
Posted By Lance to Computational Complexity at 10/25/2010 07:24:00 AM