46
$\begingroup$

I was editing a student manuscript. The student remarked that it would be nice to see examples of quality writing in published work, and I realized that I couldn't really come up with good examples off the top of my head

What are the best examples of quality mathematical writing you've seen ?

Rules:

  • I'd prefer TCS papers as far as possible. Our style is different enough from standard math papers that I think it's better to focus on TCS (also why I'm asking here and not on MO)
  • it would help if you mentioned what exactly you thought the paper did well. Not all exposition is good at everything - some papers have great proof outlines, some use notation really effectively and others convey intuition masterfully.
  • if possible, please link to the paper.

I'm hoping this can become a resource, like many of our other broad questions. I'm marking it CW for that reason.

$\endgroup$
  • 5
    $\begingroup$ www-cs-faculty.stanford.edu/~uno/klr.html $\endgroup$ – Kaveh Oct 15 '12 at 1:35
  • 2
    $\begingroup$ A PDF version of the Knuth, Larrabee, and Roberts course notes on Mathematical Writing are floating about the internet. For example, here: jmlr.csail.mit.edu/reviewing-papers/… $\endgroup$ – Logan Mayfield Oct 15 '12 at 11:48
  • 3
    $\begingroup$ Adding to Kaveh and Logan's comments, Don Knuth did a series of video lectures at Stanford based on the curriculum of "Mathematical Writing". I have the videos, but can't seem to find them hosted anywhere online. I wouldn't mind putting them up somewhere, but I'm sure there would be some copyright loop holes to jump through first. $\endgroup$ – Vincent Russo Oct 15 '12 at 17:11
  • 9
    $\begingroup$ @VincentRusso they are here: scpd.stanford.edu/knuth/index.jsp $\endgroup$ – Suresh Venkat Oct 15 '12 at 17:23
7
$\begingroup$

In the 'Great proof outline' category, these are my favorites:

"Undirected Connectivity in Log-Space" by Omer Reingold.

"Geometry, Flows, and Graph-Partitioning Algorithms" by Sanjeev Arora, Satish Rao, and Umesh Vazirani.

$\endgroup$
7
$\begingroup$

Entropy waves, the zig-zag graph product, and new constant-degree expanders conveys a lot of intuition about graph products and expander graphs and the ideas are accessible to anyone with basic knowledge of linear algebra.

$\endgroup$
6
$\begingroup$

I remember really liking Luca's paper giving a spectral approximation to Max Cut: http://arxiv.org/pdf/0806.1978v5.pdf.

Except for the clear exposition, he nicely paints the bigger picture: why is any better-than-factor-of-2 approximation to MaxCut hard, why one would expect that spectral techniques could work, how his algorithm relates to Cheeger's inequality, and to the Goemans-Williamson SDP. In addition to the algorithm itself being very neat.

$\endgroup$
6
$\begingroup$

Luca Trevisan's extractor paper is beautifully written -- the idea, at that time, was revolutionary, and Luca's exposition of the intuition was great.

$\endgroup$
  • 5
    $\begingroup$ Link to the paper ? $\endgroup$ – Suresh Venkat Oct 15 '12 at 6:40
5
$\begingroup$

Not sure if it qualifies for TCS, but the classic paper by Kleinberg is a good example for good writing. At least this is what I use as an example when I am asked this question.

Authoritative Sources in a Hyperlinked Environment by Jon M. Kleinberg http://www.cs.cornell.edu/home/kleinber/auth.pdf

It is also quite interested to contrast this paper with the "Google paper" that was published in WWW. The Kleinberg paper is much better written.

$\endgroup$
4
$\begingroup$

Oded Goldreich's In a World of P=BPP is one of the best written papers that I read. This is mostly due to the clarity of the exposition, the conceptual perspective, and the choice to include reflections regarding the meaning of the results in the paper.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.