55

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.

Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271
  • 6
    http://www-cs-faculty.stanford.edu/~uno/klr.html – Kaveh Oct 15 '12 at 01:35
  • 2
    A PDF version of the Knuth, Larrabee, and Roberts course notes on Mathematical Writing are floating about the internet. For example, here: http://jmlr.csail.mit.edu/reviewing-papers/knuth_mathematical_writing.pdf – Logan Mayfield Oct 15 '12 at 11:48
  • 3
    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. – Vincent Russo Oct 15 '12 at 17:11
  • 9
    @VincentRusso they are here: http://scpd.stanford.edu/knuth/index.jsp – Suresh Venkat Oct 15 '12 at 17:23
  • @Kaveh, are these notes actually good? The first 15 pages were a good start, but the next 20 pages not so much. I skimmed through the rest of the notes, and they also didn't look that useful. The notes themselves were not so comfortable to read due to changing style, referring to external materials, and out-of-order presentation (e.g. frequent referral to section 2 in section 1). – Dmitry Dec 04 '23 at 07:56

7 Answers7

8

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.

Jagadish
  • 1,955
  • 21
  • 27
8

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.

Peter
  • 1,251
  • 7
  • 11
7

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.

Sasho Nikolov
  • 18,189
  • 2
  • 67
  • 115
6

Luca Trevisan's Extractors and pseudorandom generators (freely available from author's webpage) is beautifully written -- the idea, at that time, was revolutionary, and Luca's exposition of the intuition was great.

Ilk
  • 920
  • 4
  • 13
D. S.
  • 51
  • 2
5

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.

Panos Ipeirotis
  • 1
  • 1
4

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.

0

I am into Algebraic Complexity Theory. I recently read the paper Factorization of Polynomials given by Arithmetic Branching Programs. Also i have read some of Nitin Saxena's paper and they are very easy to read and self containd.

Soham Chatterjee
  • 280
  • 1
  • 6