Tuesday, June 14, 2011

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!


  1. "Part I of I" is a title I would actually understand, I think. It requires some knowledge of Roman numerals, no? Or maybe some ability to distinguish vertical strokes from ones and eyes. So it's nontrivial.

    Something like "Part II of I" would be somewhat incomprehensible.

    Although maybe not, as in the slide Bo'az Klartag posted for his STOC talk: "Quantum Junction,
    Get In Both Lanes".

  2. Regarding "Non-Uniform ACC Circuit Lower Bounds" being unavailable because it is hosted privately, there is this new site called the ECCC (http://eccc.hpi-web.de/) that hosts papers forever!!! And now another new one called the arXiv (http://arxiv.org/)! It truly is a remarkable age; what will people dream up next? (Maybe a cell phone with a camera?)

  3. The link to my paper is not down. The link has always been


    That link does not appear on my projects page -- sorry about that. I can update the page.

    I can also put a version on ECCC. I didn't think the paper's absence from ECCC was such an important issue.

  4. What a nice post, Bill. Thanks!

  5. The STOC best paper award was shared by two papers.

  6. Ryan: Actually yesterday the link, and part of CMU, was actually down.
    However, when it came back the link I had only pointed to a page which listed the paper. I have changed it so that it now links to the link you specified.

    Anonymous who says there were two STOC best paper awards- I was unable to find any mention of a second paper that also got Best Paper
    so please email me or post the name of the second paper and I will correct my post. OR post that you were in error.

  7. From page iii of the (electronic) proceedings:

    The committee selected two papers for a Best Paper Award: “Electrical Flows, Laplacian Systems, and
    Faster Approximation of Maximum Flow in Undirected Graphs,” by Paul Christiano, Jonathan A. Kelner,
    Aleksander Madry, Daniel A. Spielman, and Shang-Hua Teng, and “Subexponential Lower Bounds for
    Randomized Pivoting Rules for the Simplex Algorithm,” by Oliver Friedmann, Thomas Dueholm Hansen,
    and Uri Zwick. The committee selected “Analyzing Network Coding Gossip Made Easy” by Bernhard
    Haeupler for the Danny Lewin Best Student Paper Award.

    PS: I'm not an author of any of these papers.

  8. Anon: THANKS, I have ADDED that information to the post.
    (about the shared BEST PAPER award)

  9. GASARCH: Sorry about missing the second best paper award -- it was unintentional and I added it to my page (the page mentioned in "This seems to be unknown to thiswebsite.").

  10. Anyone knows if STOC is going to be make the talks available online like FOCS (http://techtalks.tv/events/13/)?

  11. Some points about your point 5.

    1. the link to the "writeup of the version of Large Ramsey they were talking about" is broken.

    2. the following sentence is ill-formed.
    "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."

    3. "This is rather odd-": are reductions and conditional results so odd? Also, the paper says an upper bound is also proved. The status of the standard Ramsey Theorem in Proof Complexity seems to be similar.

    4. I have never heard "Proof Complexity" used in connection with your meaning "(1) proving that theorem X NEEDED to use Axioms Y or had to be nonconstructive of level Z", although it might make sense! Usually (1) is referred to generically as Proof Theory, or more specifically as Reverse Mathematics, isn't it?

  12. Anon

    1) THANKS for telling me the link was broken. I have fixed it.

    2) The papers original motivation was as follows: Large Ramsey is NOT provable in PA. Hence, if we formulate its negation in Prop Logic this may lead to a prop fml that requires a long proof in some proof system.
    They ended up showing (contingent on a resonable assumption) that a
    VERSION of Large Ramsey, that IS
    probable in PA (and is in the notes I linked to) requires a long proof.

    3) What I find odd is that since
    Ramsey and Large Ramsey seem HARDER than PHP, proving that proofs of them are long should be easier. A direct proof that (say)
    Ramsey requires a long proof may lead to better bounds.

    4) My definition of Proof Theory was probably not broad enough.
    If you have a good alternative definition that encompasses more of it then please comment.
    (Wikipedia had an entry on it but not real definition of it.)