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.

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

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

ReplyDeleteWouldn'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)?

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

ReplyDeleteA caveman takes the liberty to digress:

ReplyDelete1. 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..