Tuesday, June 24, 2008

FOCS Accepts

Accepted FOCS papers posted.


  1. What a great opportunity to test Lance's previous (exceedingly funny) post "the seven dirty words you cannot say at the Complexity Conference."

    The number of times each word (or a variant) from Lance's List appears in a FOCS title:

    1. Constants: twice
    2. Algorithm: nine times
    3. Application: once
    4. Heuristic: never
    5. Competitive: never
    6. Implementation: never
    7. Wolfram: never

    Obviously Lance's List is strongly predictive -- with the striking exception of the still-popular word "algorithm".

    Why is "algorithm!" the exception? Does this mean that algorithm papers are on their way out, but are not extinct yet? Like pandas? :)

  2. Algorithm is still somewhat an exception as Lance's list was for complexity and not focs.

  3. I'm curious. Anyone knows what are almost-natural proofs?

  4. try searching google.

  5. As a follow-up, in a idle moment I looked for the most common words -- the non-rigorous result was a tie between "approximate" (with variants) and "bounds" (with variants) -- each with fourteen instances (never adjacently).

    Has FOCS therefore become a conference mainly about approximations and bounds?

  6. Isn't it that both STOC and FOCS have always been mostly about approximations and bounds...