FCRC 2011. Part I of... maybe I, maybe more.

I do not log on at conferences so I came back to 400 emails. Exactly 400- not sure how I managed that. TODAY I am posting about a few things from FCRC, I may post more next week as I remember them.

1. CCC finally no longer has proceedings. Most conferences at FCRC did not have proceedings. ISCA, the International Symposiusm on Computer Architecture, still has proceedings. I asked someone from ISCA why they still have proceedings. They gave an answer which boils down to That's the way we've always done it. Also, ISCA has MONEY so they don't need to save money as well.
2. The best student paper award at STOC went to Analyzing Network Coding Gossip made Easy by Bernard Haeupler. Great Talk!
3. The best paper award went to Electrical Flows, Laplacian Systems, and Faster Approximation of Network Flows in Undirected Graphs Electrical Flows, Laplacian Systems, and Faster Approximation of Network Flows in Undirected Graphs by It also might be a contender for longest title. A better title might have been Electrical Flows and Networks Flows. Great talk. Looks like a paper I can actually read and understand. Network flows is a well studied problem- one slide had over 30 references on it. (ADDED LATER: A helpful commenter pointed out that The Best Paper award was actually shared by the FLOWS paper and also by Subexpontential lower bounds for randomized pivoting rules for the simplex algorithm by Friedmann, Dueholm, Hansen, and Zwick. This seems to be unknown to thiswebsite.) (ADDED EVEN LATER- The page I just pointed to now DOES know about the two awards and has been updated.)
4. I skipped the talk on The Computational Complexity of Linear Optics by Aaronson and Arkhipov since I saw some version of it a while back. My mistake- talks I see twice I actually understand, and I heard it was an excellent talk. Going to Scott's webpage to make this post I spotted a paper on using Linear optics to prove the PERM is #P complete. THATS the paper I really want to read! Serendipity is alive and well.
5. Proof Complexity means two different things: (1) proving that theorem X NEEDED to use Axioms Y or had to be nonconstructive of level Z, and (2) proving that certain formulas need exponential number of steps to prove they are not satisfiable. This talk tried to use a theorem (the Paris Harrington Ramsey Theory) that is not provable in Peano Arithmetic requires a long proof in some systems. They end up saying that if a version of Paris Harrington (that CAN be proven in PA) has a short proof then Pigeon hole principle has a short proof. This is rather odd- the only thing they can prove DIRECTLY requires long proofs is PHP, so everything reduces to it. The talk is here, the paper is here, for a writeup of the version of Large Ramsey they were talking about see here
6. Ryan Williams won the Best Paper award at CCC for this paper. Lance did an excellent blog on the result a while back here. (NOTE- the link to the paper seems to be down now. Hopefully it will come back up soon.)
   1. On his website it has next to the paper Will receive Best Paper award. Did he put that there when he submitted ASSUMING that he would win it? That doesn't sound right. Did he put it there when he found out he would win it? That doesn't sound right either-- being notified that you won it is the same as receiving it.
   2. I would like to think that he was inspired by my April Fools Day post of 2011 which said we should all go out and PROVE things instead of whining about barriers and oracles. Actually its the other way around- Ryan inspired the post when, at some DAGSTUHL, we were all saying what we can't prove and he said When do you think we will separate NL from PSPACE? I fell for it and said Not for a while at which point he reminded me that its already known. That inspired the post.
   3. Whenever a new result appears the question arises Did it use new techniques or a clever combination of old techniques. Or more egocentric Could I have proven that? For example, if Wiles proof of FLT is really the only way to do it then Gauss could not have done it. Ryan's proof looks like a really really clever combination of older results. This is NOT to downgrade it. And NO, I could not have done it. A better question: will it lead to MORE results? IS P vs NP just around the corner? No.
7. CCC 2012 is in Portugal. CCC 2013 is at Stanford co-located with STOC. CCC 2014 MIGHT be in Koyoto Japan. Is that a good idea? If there exists N people who CAN go if its in Japan and NOT otherwise but M people who normally go but now can't then if N and M are roughly the same or even if N is a bit bigger, than I think we should do it. Not sure what the real values of N and M are.
8. Some grad students I talked to think that CCC and/or FCRC should have an after-conference Survey Form to fill out about the conference so that they can improve things for next time. I agree!