Saturday, December 10, 2005

Great conference papers that never made it to a journal, part 327...

It's no secret that theory folk are somewhat allergic to journal papers, only publishing them to kowtow to the tenure gods, and even then grudgingly. On that note, I recently "discovered" that two (more) very influential papers that I was familiar with had never made it to a journal.

Both are by Andy Yao, their influence is staggering, and at least one of them was directly mentioned in his Turing Award citation:
  1. Some complexity questions related to distributive computing: The paper that introduced the idea of communication complexity appeared in STOC 1979.
  2. Lower bounds by probabilistic arguments: This paper introduced the idea of minimax reasoning for lower bounding randomized algorithms, and appeared only in FOCS 83.

Footnote: If you haven't seen it, it's "new to you" :).

1 comment:

  1. Even more amazing is something like Yao's "garbled circuit" (used in cryptographic secure computation) which never even appears in a paper of his but was apparently mentioned during one of his talks...

    Posted by Anonymous


Disqus for The Geomblog