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" :).