Monday, August 18, 2014

Complexity versus Algorithms: The FOCS Challenge

In recent years, I've heard complaints from my complexity colleagues that FOCS and STOC are mostly algorithms and from the algorithm buddies that STOC and FOCS are mostly complexity. What exactly counts as a complexity or algorithms paper has become quite blurred in recent years. So let's try an experiment. Below is a poll I've created using titles from the upcoming FOCS conference. Which of these papers do you consider complexity? Does complexity in the title make them a complexity paper? 

If you are interested, you can find the manuscripts for most of these papers on the FOCS accepted papers list.

survey tools

Disclaimer: This is a completely non-scientific poll solely for the interest of the readers of this blog. The results will have no effect on future conference papers.


  1. You can't really guarantee that the result will not have an effect.

  2. The poll does not allow me to vote on for the empty set.

  3. Wouldn't this have been a slightly less ad hoc survey if it had included, say, *all* the papers from FOCS this year? How did you pick which ones to include in the survey (e.g. it definitely wasn't just all papers with the word "complexity" in the title)?

  4. I think here the attempt is to decide on a small sample size, but Anonymous7:12 PM makes a point that cannot be ignored.

  5. A caveman takes the liberty to digress:
    1. Will there be an expensive book called proceedings or pointers to arxiv?
    2. Are videos going to be recorded for all the talks?
    Recalling the context from a STOC 2013 post..