Looking at the list of important papers in computer science one notices that the majority are authored by a single author. Those include classic papers of Turing, Shannon, Karp and Cook. Cook's solo paper started the most important question of computer science.

How can we explain this? What are the implications to the creative process in theoretical computer science?

I am aware of paradigm shifts and paradigm blindness. However, I doubt they fully explain this phenomena.

Here is the list that includes important papers in TCS which motivated my question.

  • 15
    $\begingroup$ The papers you allude to in the question were all written 35+ years ago when the field was small and collaboration was harder. That alone could explain their having only one author. And one can probably come up with a large list of counterexamples, which I'll kick off with RSA and the Agrawal-Kayal-Saxena primality paper. $\endgroup$ Jun 2, 2014 at 12:41
  • 7
    $\begingroup$ It seems that you're not the only person concerned with this. For example, it was asked by Frank Ruskey to Donald Knuth (#16 in informit.com/articles/article.aspx?p=2213858). On this issue I totally agree with Ruskey, and it seems extremely rare and hard to believe that more than two persons make real contribution to a single paper. But if four authors write four papers together, they get significantly better chance to get jobs, funding, etc. than each publishing a single-authored one. $\endgroup$
    – Yixin Cao
    Jun 2, 2014 at 13:07
  • 4
    $\begingroup$ I've added a more descriptive title, since the previous title could make one think that this is suppose to be a "big list" of break-through papers. Also, I think it is important to take @DavidRicherby's comment seriously, and make sure you are actually seeing a real pattern. If we look at breakthrough papers and look at their publication dates, how does their authorship statistics compare to the statistics of authorship at that time? Is there really an abnormality, or would you expect it to come from age and chance due to small sample? $\endgroup$ Jun 2, 2014 at 13:55
  • 9
    $\begingroup$ For a long list of counter examples, please see the Gödel prize list (en.wikipedia.org/wiki/G%C3%B6del_Prize): only 5 of the 22 papers awarded prizes are single-authored, and Johan Håstad counts for two of those. $\endgroup$ Jun 2, 2014 at 18:46
  • 8
    $\begingroup$ @Suresh: you're miscounting. There are 11 single-authored papers (out of 33) in that list. For example, Immerman and Szelepcsényi shared the prize for two single-authored papers that proved essentially the same result. $\endgroup$ Jun 3, 2014 at 1:24


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.