It's fascinating that this is only six pages long. The complexity analysis and corresponding math is sufficiently light as to be both straightforwardly comprehensible and inline with the body of the paper (instead of thrown into a "Theorem Appendix" at the end). The entire paper is exceptionally readable.<p>In contrast, new research that could be called "fundamental" in algorithms and theoretical computer science is typically several times longer and more complex. On one hand it seems intuitive that the more mature a field is, the higher the prerequisites for review and contribution. Computer science papers from the 60s seem much easier to read these days that what's been put out in the JACM since 2000, and modern papers in pure mathematics research are dense and incomprehensible (and commensurately more difficult to publish results in) even when placed next to modern research in computer science.<p>On the other hand, a fundamental improvement to Quicksort was developed in 2009 and the author's paper comes in only five pages [1]. Is that because the improvement is "minor", because the author is exceptional at explaining the fundamental ideas clearly and succinctly, or because the author was relatively lazy about putting in the things usually demanded for publication (long sections on methodology, historical context, problem motivation, complexity analysis in different implementation contexts...)? It's hard to know whether some of these academic papers actually require their significant length, or if the presentation of material is simply inefficient. Cuckoo hash [2] was developed in 2001, but its paper comes in at 26 pages despite it being a fairly intuitive construction. The authors didn't just explain the fundamental result, they included two full pages of reference citations, a section on empirical performance characteristics and complete details of their experimental lab setup.<p>I'm not advocating that modern papers should necessarily be shorter, but I think it's an interesting question.<p>__________________________<p>1. <a href="http://codeblab.com/wp-content/uploads/2009/09/DualPivotQuicksort.pdf" rel="nofollow">http://codeblab.com/wp-content/uploads/2009/09/DualPivotQuic...</a><p>2. <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.25.4189&rep=rep1&type=pdf" rel="nofollow">http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.25....</a>