Monday, August 01, 2011

Does STOC/FOCS take simple-nice-ideas papers? A one-element case study

WRITTEN AUG 1,2011: It has been said that simple innovative ideas to not get into STOC/FOCS and only hard technical improvements do. This is one of the motivations for the INNOVATIONS conference. But is it true? People mostly toss out anecdotal stories and, alas, I will do the same. But with one difference. The next few paragraphs were were written in September 2010, BEFORE the STOC decisions came out.

WRITTEN IN SEP 2010: Dave Mount gave a brilliant talk at today's internal UMCP theory day on a joint paper he wrote with Sunil Arya and Guilherme da Fonseca. I actually understood it! It is a perfect example of something that is so simple, clever, obvious-after-you-see-it, and useful that it might not get into STOC. Dave thought it would not get in for this reason. I am less sure. However, Dave Mount and I agree that when the decision is made I will blog about it. If the paper gets in it will be an anecdote that counters the only-complicated-papers-get-into-STOC notion. If the paper does not get in then it will be an anecdote that supports this notion. Either way I get a post out of it and Dave, Sunil, and Guilherme get publicity for their results (either in anger or in joy).

Here is the problem of interest and their variant on it.
  1. Given a set S of n points in d-dim space create a data structure so that the question: given point q, find the point p in S that is closest to q. We want low space and quick time. This seems hard to achieve.
  2. Given a set S of n points in d-dim space, and a parameter ε, create a data structure so that the question: given point q, find the point p in S that is at worst (1+ε)OPT away from q. This is called Approx Nearest Neighbor. We call it ANN.

Here is what was known: In Space-Time Tradeoffs for approximate nearest neighbor searching, by Arya, Malamatos, Mount, they showed a very complicated algorithm that did the following. View d as being constant. S is a set of n points in d-dim space. ε is also an input.
  1. Let γ be a tradeoff parameter with 2 ≤ γ ≤ 1/ε. There is a data structure for ANN with
    1. space O(n γd-1log(1/ε)), and
    2. query time O(log(nγ) + 1/(ε γ)(d-1)/2).
  2. If γ=2 then space O(nlog(1/ε)) and query time O(log n + 1/ε(d-1)/2).

The new result was an improvement and was easy to code and use. I won't state it since it is not easy to typeset (AH HA- maybe being hard to typeset will give them an edge) but here is the paper: Approximate Polytope Membership Queries, (CONFESSION: that very last link was revised in July 2011, but the rest was written in SEPT 2010.)

WRITTEN IN FEB 2011: CONGRATS to Dave, Sunil, and Guil. Their paper got in. That's one anecdote against the notion that STOC does not nice simple ideas. If YOU (the reader) have some other ones, please leave them as comments.

WRITTEN IN JUNE 2011: The STOC talk was EXCELLENT. Here are the slides.


  1. Is this because STOC was always open to such papers, or more due to a recently created awareness via this blog, ITCS, the call for more flexibility in acceptances by a slew of big names, etc?

    Not to pick on STOC, it seems to me the field as a whole (TCS) tends to be generally not very receptive to such papers. We are obsessed with technical difficulty, and STOC being so the epitome of this is simply because it reflects our values more markedly, given its high selectivity.

    I've been paying attention since the early 90s to how simple papers are handled by program committees from all conferences, not just STOC and FOCS.

    For the last two years or so at least one of the reviewers speaks in their defense, rebuking criticisms based solely on technical difficulty. Upwards of 2/3rds make it into conferences nowadays.

  2. I have had a different experience, after few rejects, I changed title to 'A simple...' and the paper went through. One of the reviewers who rejected the paper said it was a simple idea - and we emphasized that by changing title.

    Also, based on the authors - in this case Arya & Mount are masters of ANN so, the paper will be taken lot more seriously.

    If the same happens to two unknown authors (as established in this area) then it is a true reflection that simple idea papers go through in top conferences.

  3. There are plenty of STOC/FOCS papers that are technically simple. The key for such a paper to be accepted is the excitement of a reviewer/PC member.

  4. My paper was rejected from FOCS (I was not surprised).
    The paper was split into one PNAS letter, and one Quantum Information and Computation paper, and another one under revision. I believe (and this work is an example) that a simple idea paper is better than technically complicated but incorrect papers, including FOCS/STOC.

  5. The point is not whether the ideas of the solution are simple or not, but which problem you are solving. There is a big difference between improving a known result using simple ideas and defining a new problem that can be solved with simple ideas. Then, there are the problems that have been around for a while, nobody has an idea how to handle it, and someone comes with a simple and useful idea. Then the authors should convince the reader that the problem has been around for some time several people failed.

  6. Einstein once said "make things as simple as possible, but not simpler".

    Nowadays one could add: "... to be accepted to STOC/FOCS or to an arrogant TCS journal like SIAM J. of Comput.".

    This approach in CS (being elegant = being trivial) has nothing to do with THE Book uncle Paul Erdos believed in.

  7. 1.


    Is it a coincidence that both the above "simple" papers were in SODA and not STOC/FOCS ?

  8. Anonymous 1:06 nails it. TCS doesn't seem to know the difference between elegant (or insightful) and trivial.

    If a question had been asked before, repeatedly, and turns out to have a short answer then clearly the answer is insightful, otherwise people asking the question before wouldn't have.

  9. Apropos the previous comment. Who is this individual called TCS? It has become quite easy and convenient to take a holier than thou attitude towards an entire field made up of many different individuals - one could feel smug and superior making such comments but serves no purpose really.

  10. I have a simple 5 page proof to show that finite programs will either complete or run forever. Though this has been done before I believe that this approach highlights some immediate and practical implications for moden OS and applications.

    My problem is that though I have a comp. sci. honours degree it has been some time since I graduated so I have lost contact with the academic world.

    I need some feedback on the proof from those who have published. I tried the usenet group comp.theory but since I only have access via Google groups it takes a week for my posts to show up.

    What would be the best way for me to get serious feedback on the proof before trying to publish?

  11. Who is this individual called TCS?

    To paraphrase Pogo, I have met TCS and it is us.

    to take a holier than thou attitude towards an entire field

    Far from it. Judging from the non anonymous handles most of us here are theoreticians (to various degrees) and hence discussions such as this are exercises in introspection.

  12. I do believe STOC/FOCS are very much into complicated technical stuff and against nice ideas. Worked on well-known problem (more than 10 publications in various conferences incl. STOC/FOCS) and improved all of them with a new algorithm that was simple and not too hard to analyze. Did not make it though some reviewer wrote: I am impressed by the strength of the results. Generalizing this one example: STOC/FOCS dudes do not go very much for strong results, but have fallen in love (too much) with complicated proofs. The write-up makes all the difference. Change your work from well readable to barely readable, i.e. make the reader feel that he gets some ideas, but it is really complicated after all...