Friday, July 17, 2009

Complexity Wrap-Up

I twittered about some interesting papers, the business meeting and various other impressions. Since I don't have much time to write up this post I'll just list my conference related twitters here in chronological order.

  • At CCC in Paris. Arrived half way through Ryan giving talk of our paper. Paris attracted impressive group of researchers.
  • If a talk starts with a warning about simplifying, it won't be simple enough.
  • Steve Cook: Not surprised P vs NP taking so long to solve.
  • Manindra bring back the BH isomorphism conjecture to CCC. I had posted about it back in April.
  • Bill during Manindra's talk. He claims the room is too warm.

  • Prajakta Nimbhorkar gives last CCC talk of the day with log-space alg for planar graph iso. Nice application of L=SL.
  • CCC banquet at Macéo easily beats EC banquet at Google but we got caught in a hail storm on way back to hotel.
  • Scott talks quantum money with no intentional jokes or proofs.
  • Live Tweeting the CCC business meeting. Promised 30 mins/35 if discussion. 100+ attendees with 36 students. USA 28, France 18, Israel 11
  • Hastad PC report: 37 papers accepted out of 113 (32.7%). High because after STOC announcements. PC more fun in person maybe not crucial.
  • CCC 2010 in Boston in Harvard, June 9-12 after STOC and same as EC all in Cambridge. Dieter van Melkebeek PC chair. Salil Vadhan local.
  • CCC 2011 at FCRC (June 4-11) in San Jose. Again with STOC and EC as well as many others.
  • Discussion on paper v. electronic proceedings. Straw vote: 28 electronic vs. 11 paper. Steering committee will decide.
    • @geomblog replies: why do all theory confs have straw polls and let the steering committee decide ? let's be democractic or autocratic, not neither !
  • Scott brings up problems with ECCC, server often down, papers get delayed or rejected. I'll post more next week.
  • New steering committee chair: Peter Bro Miltersen. New members: Johan Hastad and Manindra Agrawal. Meeting over, lasted 50 minutes.


  1. Hi,

    I was trying to find more details on:
    "Steve Cook: Not surprised P vs NP taking so long to solve."
    Can we find more details on Steve's talk? [at least the high level idea of this]


  2. Hi, Steve Cook didn't give a talk. Bill asked him a question along the lines of: "When you first posed it, did you think P vs NP would turn out to be so hard?" during one of the breaks.

  3. Re: "Scott brings up problems with ECCC..."

    ECCC was great for the last decade and a half, but perhaps its time now to fold it into the arXiv?

  4. Does anyone know how arxiv is supported/hosted? What is the long-term guarantee? i.e. if it is hosted at a university that goes out of business, what will happen to the repository of articles? Just curious.

  5. The arXiv is currently hosted at Cornell, with a number of mirrors. It is funded both by Cornell and the NSF. The entire arXiv is only a few hundred gigabytes of data. Also, it started at Los Alamos, so has already moved once.

    The arXiv seems clearly superior to the ECCC in many respects. For example, the arXiv has a Wikipedia article, while the ECCC shows up after the "Extraordinary Chambers in the Courts of Cambodia" in Google searches. :) The ECCC could make a lot of changes to catch up, but why?

  6. > @geomblog replies: why do all
    > theory confs have straw polls and
    > let the steering committee decide?
    > let's be democractic or
    > autocratic, not neither !

    I second that. Why do we make a vote during the business meeting and then frequently leave the final decision to the steering committee?

    For example, will SODA'2011 be in Paris, as was the vote during SODA business meeting, or will SIAM and the steering committee decide about some other location?

  7. Hopefully SODA 2011 will NOT be in Paris. With the economy the way it is, most people, esp students, can not afford a trip across the atlantic plus the hotels in paris. Please, please keep it cheap. Pay for your vacations with your own money! Conferences should be in the most accessible, cheapest location that facilitate the highest attendance. They should not be designed to give free vacations to people using their government grants!!

  8. Also, note that the people who voted for SODA 2011 in Paris were the attendees of SODA 2009, not the attendees of SODA 2011. Maybe we can have a vote that includes the entire algorithms community, even the people who were not able to attend SODA 2009.

  9. Also, I am not sure I really want to visit Paris in January.....a summer or fall conference in Paris, sounds like a lot more fun.
    (Ofcourse the conf. talks can be fun anywhere, but the location can be a draw if you have time to hang out before or after the conference).

  10. SODA 2011 will be in San Francisco. SIAM cannot on their own run a conference outside of North America, but needs a local organizer. We could not find anyone to host the conference in Paris proper. The best we could do was a suburban location, which I do not think would have counted as "Paris" even to the voters. So in the future, proposals for European locations will not be considered at Business Meetings unless they are made by people prepared to act as local organizers (as is done with STOC and FOCS).

    David Johnson

  11. ECCC is without any doubt superior to ArXiv for computational complexity.

    While ECCC continues to be a repository for serious up to date research in complexity, ArXiv is just a collection of P=NP junk and the like, with some minor exceptions.

    Also, one cannot easily sort out this crap from the list, because there are many papers completely unrelated to complexity there.

    Without having a filtering mechanism, there is no real alternative to ECCC for now.

  12. That's really not true. I usually read the algorithms and data structures feed (e.g. paper titles) and certainly the stuff is not all junk--only a small fraction. Mostly its stuff people have submitted to mainstream conferences.

    Is this really different for complexity?

  13. I agree with the last anonymous. I've been subscribed to arxiv.CC/CS/DM (computational complexity/data structures/discrete math) for the last 1.5-2 years, and bogus manuscripts are rare. When they do appear, they're obviously bogus (usually from the title, but sometimes you're tricked into reading the first sentence of the abstract), and you waste only a few seconds before moving on. I personally prefer spending a minute a day to filter things on my own if it means I can see manuscripts within 24 hours of their submission, versus the longer delays ECCC often has.

    Anyway, I don't understand why arXiv and ECCC have to compete. If the point of ECCC is to designate which manuscripts are worth reading, how about building ECCC on top of arXiv? It can be a "best of cs.CC" list. All papers appearing on cs.CC are treated as ECCC submissions, and those which are deemed non-junk are replicated (or simply linked to) by ECCC. Now, readers who are OK with spam-filtering on their own, and readers who don't want to do this, can be simultaneously satisfied.

  14. I've just checked one by one all papers in ArXiv (computational complexity section) for 2009 and found out that at least 32 papers, out of 96, do not belong to computational complexity per-se (e.g., these are papers in data-structures, numerical analysis, game theory, etc., with only a marginal, if any, connection to complexity). At least four papers from this 32, are P=NP junk.

    So one third of the papers do not really belong there. This is hardly useful.

    For the suggestion to incorporate ECCC on top of ArXiv, and maintaining the filtering mechanism, this sounds like a pretty good idea.

  15. Safely-anonymous commenter #14, why don't you name names? If a third of the cs.CC papers are non-computational-complexity, which ones are they? I'd prefer to avoid the junk vs good research distinction, since that's not relevant for arxiv moderation, but if papers are being misclassified then that can be fixed. Your comment that at least four of these non-computational-complexity papers are on the P vs NP problem argues against your credibility, though, since P vs NP is clearly a complexity theory question.

    As for whether the readers are better served by a server that lets some junk through versus a server that takes two months to bounce some good papers, I think it's reasonable for different people to have different ideas. The overlay solution sounds like a good one to me, though: that way both camps can get what they want, and not have to worry that they're missing some of the papers because they were sent to the other repository.

  16. It is not a difficult problem to filter out papers, either according to a community consensus or according to the opinions of a scientific board like the ECCC currently has.

    This should be done on top of the arxiv. Running it separately creates tons of problems and fixes none.

    I guess the problem is that there is inertia. There is a sort-of working system now, so nobody will want to change. If the board is letting reasonable papers expire after two months, then there does not seem to be enough initiative there to make any changes.

    A fast solution would be to set up something like the "Theory of Computing Blog Aggregator." This can be done without involving the ECCC board. To avoid a single dictator controlling which papers make the list, a few people can be given control, or all registered users could contribute. It would be easy to prevent abuse.

  17. Even without an aggregator, a 2/3 usefulness rate doesn't seem bad at all to me for research papers. And 4 papers out of 100 on P=NP doesn't seem like nearly enough to swamp all the good contributions. How is this "hardly useful"? You don't have to read every paper. Read the good ones, and two months before the ECCC gets them out, if the website is even working.

  18. I'm confused: in arxiv you can cross reference papers, i.e. if I have a data structures paper, it goes into the data structures and algorithms feed and I can also register it in the CC feed. At least that is my assumption because I see that many papers are cross listed.

    So it is not a case of these papers being mis-classified. Just that they have primary and secondary classifications.

    Also, I'm confused: isn't data structures a topic under computational complexity? Why is this a misclassification?

  19. To #15

    1. I'm not impressed by snarky remarks about anonymity. Generally those who oppose anonymity just want to maintain their power of intimidation.

    2. I have written a full list of the titles I claim are irrelevant to computational complexity. I have then decided not to send this list as not to offend anyone.

    3. The discussion moved to the latest computational complexity blog post, so I'll continue my remarks there.

  20. I have no particular opposition to anonymity, especially for untenured researchers. But as long as you are anonymous, there's no reason to also be timid in other ways.