Monday, October 25, 2010

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. 

16 comments:

  1. we should submit bad proposals to make the others look good? nice.

    ReplyDelete
  2. How do you decide which blog posts to have moderated comments on? I have noticed that some comments post right away but some comments are held for moderation.

    ReplyDelete
  3. Who seem to be the major contenders for the Simons Institute. Are departments applying together? (i.e. it would seem to make sense for Columbia and NYU to combine forces for a New York center)

    ReplyDelete
  4. Probably there will be a couple proposals from the NY/NJ area, maybe Cornell, MIT/Harvard, and something from the Bay Area.

    Those would seem to be the big contenders.

    ReplyDelete
  5. 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.

    I cannot believe you wrote this.

    So all the people who are less well known (and therefore have no shot at being funded through this program) should apply just so they can make the people who are already getting funding look better?! Nice.

    ReplyDelete
  6. And why do you think theory is _not_ overfunded? Particularly, relative to any actual good that comes out of it?

    ReplyDelete
  7. The ~ 1-1.5 hour Amtrak radius around New York has a huge collection of theorists. In the city itself you have Columbia and NYU, together with Google and Yahoo research. And then going out a bit, there is Yale, Rutgers, Princeton, and UPenn. An NYC center would be useful, because there are lots of theorists, spread around in a currently disorganized way.

    Many other theory hubs are already centralized (big, and the only game in town): Cornell, MIT, CMU, etc.

    ReplyDelete
  8. You forget the Chicago area.

    ReplyDelete
  9. I don't think the research labs (Yahoo!, Google, IBM ..) would participate in the Simons Center. If you look at the FAQ, they don't appear to want to support for-profit centers. So having Google and Yahoo! in the NY area is likely not going to be a factor.

    ReplyDelete
  10. Sure Google Yahoo IBM labs will not receive funding from the center, but their presence in NY provides a ready source/audience for talks, collaborators for postdocs, etc.

    ReplyDelete
  11. Does the end of paper proceedings mean that paper proceedings won't exist at *all*, ie, not even an option to buy them?

    ReplyDelete
  12. Lance is not saying to submit bad proposals to make others look better. He's saying that if people submitted grant applications even if they didn't think they'd get accepted, the NSF will see how much interest there is in the area instead of lowering funding because of the high acceptance rate.

    ReplyDelete
  13. You do realize that preparing a proposal takes a lot of time and effort, which (under the assumption that the proposal is not going to be funded) will be better spent elsewhere.

    ReplyDelete
  14. Of course everyone realizes that. Sadly other fields realize it less than we do, so TCS funding will be cut.

    We should try to triple our number of proposals, so that our rejection is the very highest. If the mathematicians come back, then we should triple it again. The only way to win this war is to be relentless. Ultimately, we can drive the acceptance rate to zero if they don't give in. I feel like I am channeling Rumsfeld right now.

    ReplyDelete
  15. We should try to triple our number of proposals, so that our rejection is the very highest.

    In certain circles, these kind of things are called juking the stats :-)

    ReplyDelete
  16. Does the end of paper proceedings mean that paper proceedings won't exist at *all*, ie, not even an option to buy them?

    Yes. They will not be produced. It turns out that as of lasy year there were only 15 library subscriptions for printed IEEE proceedings and almost none are sold outside of the conferences.

    ReplyDelete