<p>In the 'Great proof outline' category, these are my favorites:</p>

<p>"<a href="http://www.wisdom.weizmann.ac.il/~reingold/publications/sl.ps">Undirected Connectivity in Log-Space</a>" by Omer Reingold.</p>

<p>"<a href="http://www.cs.princeton.edu/~arora/pubs/arvcacm.pdf">Geometry, Flows, and Graph-Partitioning Algorithms</a>" by Sanjeev Arora, Satish Rao, and Umesh Vazirani.</p>

CC BY-SA 3.0
2012-10-15T09:34:03.373Z
2012-10-15T09:39:15.770Z
2012-10-15T09:39:15.770Z
Jagadish
<p><a href="http://arxiv.org/abs/math.CO/0406038">Entropy waves, the zig-zag graph product, and new constant-degree  expanders</a> conveys a lot of intuition about graph products and expander graphs and the ideas are accessible to anyone with basic knowledge of linear algebra.</p>

CC BY-SA 3.0
2012-10-15T10:23:57.247Z
2012-10-15T10:23:57.247Z
Peter
<p>I remember really liking Luca's paper giving a spectral approximation to Max Cut: <a href="http://arxiv.org/pdf/0806.1978v5.pdf">http://arxiv.org/pdf/0806.1978v5.pdf</a>. </p>

<p>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.  </p>

CC BY-SA 3.0
2012-10-15T04:07:28.247Z
2012-10-15T04:07:28.247Z
Sasho Nikolov
<p>Luca Trevisan's <a href="https://doi.org/10.1145/502090.502099" rel="nofollow noreferrer">Extractors and pseudorandom generators</a> (<a href="https://lucatrevisan.github.io/pubs/extractor-full.pdf" rel="nofollow noreferrer">freely available from author's webpage</a>) is beautifully written -- the idea, at that time, was revolutionary, and Luca's exposition of the intuition was great.</p>

CC BY-SA 3.0
2012-10-15T06:40:30.130Z
Link to the paper ?
Suresh Venkat
CC BY-SA 4.0
2022-10-05T04:10:57.150Z
shared link is dead
alper
CC BY-SA 4.0
2023-11-27T18:21:21.587Z
Fixed the rotten link
Hermann Gruber
CC BY-SA 4.0
2012-10-15T04:18:47.570Z
2023-11-28T17:13:47.153Z
2023-11-28T17:13:47.153Z
D. S.
<p>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.</p>

<p>Authoritative Sources in a Hyperlinked Environment by Jon M. Kleinberg 
<a href="http://www.cs.cornell.edu/home/kleinber/auth.pdf">http://www.cs.cornell.edu/home/kleinber/auth.pdf</a></p>

<p>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.</p>

CC BY-SA 3.0
2012-10-15T01:42:30.707Z
2012-10-15T01:42:30.707Z
Panos Ipeirotis
<p>I am into Algebraic Complexity Theory. I recently read the paper <a href="https://link.springer.com/article/10.1007/s00037-021-00215-0" rel="nofollow noreferrer">Factorization of Polynomials given by Arithmetic Branching Programs</a>. Also  i have read some of Nitin Saxena's paper and they are very easy to read and self containd.</p>

CC BY-SA 4.0
2023-11-26T06:52:09.937Z
2023-11-26T06:52:09.937Z
Sassy Math
<p>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</p>

<blockquote>
  <p>What are the best examples of quality mathematical writing you've seen
  ?</p>
</blockquote>

<p>Rules:</p>

<ul>
<li>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)</li>
<li>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. </li>
<li>if possible, please link to the paper. </li>
</ul>

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

CC BY-SA 3.0
2012-10-15T01:35:04.143Z
http://www-cs-faculty.stanford.edu/~uno/klr.html
Kaveh
CC BY-SA 3.0
2012-10-15T11:48:37.803Z
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
CC BY-SA 3.0
2012-10-15T17:11:57.383Z
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
CC BY-SA 3.0
2012-10-15T17:23:09.133Z
@VincentRusso they are here: http://scpd.stanford.edu/knuth/index.jsp
Suresh Venkat
CC BY-SA 4.0
2023-12-04T07:56:21.440Z
@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
<soft-question><writing>
Good examples for how to write well in TCS
Suresh Venkat
# Good examples for how to write well in TCS

(Asked by: username_0 on 2012-10-15)

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.

**Tags:** soft-question, writing
> **Comments:**
> **username_1**: http://www-cs-faculty.stanford.edu/~uno/klr.html  
> **username_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  
> **username_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.  
> **username_0**: @VincentRusso they are here: http://scpd.stanford.edu/knuth/index.jsp  
> **username_4**: @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).  

---

## 6 answers

### Answer by username_5 on 2012-10-15. Score: 8

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

"[Undirected Connectivity in Log-Space](http://www.wisdom.weizmann.ac.il/~reingold/publications/sl.ps)" by Omer Reingold.

"[Geometry, Flows, and Graph-Partitioning Algorithms](http://www.cs.princeton.edu/~arora/pubs/arvcacm.pdf)" by Sanjeev Arora, Satish Rao, and Umesh Vazirani.


---

### Answer by username_6 on 2012-10-15. Score: 8

[Entropy waves, the zig-zag graph product, and new constant-degree expanders](http://arxiv.org/abs/math.CO/0406038) conveys a lot of intuition about graph products and expander graphs and the ideas are accessible to anyone with basic knowledge of linear algebra.


---

### Answer by username_7 on 2012-10-15. Score: 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.


---

### Answer by username_8 on 2012-10-15. Score: 6

Luca Trevisan's [Extractors and pseudorandom generators](https://doi.org/10.1145/502090.502099) ([freely available from author's webpage](https://lucatrevisan.github.io/pubs/extractor-full.pdf)) is beautifully written -- the idea, at that time, was revolutionary, and Luca's exposition of the intuition was great.

> **Comments:**
> **username_0**: Link to the paper ?  
> **username_9**: shared link is dead  
> **username_10**: Fixed the rotten link  

---

### Answer by username_11 on 2012-10-15. Score: 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.


---

### Answer by username_12 on 2023-11-26. Score: 0

I am into Algebraic Complexity Theory. I recently read the paper [Factorization of Polynomials given by Arithmetic Branching Programs](https://link.springer.com/article/10.1007/s00037-021-00215-0). Also i have read some of Nitin Saxena's paper and they are very easy to read and self containd.


---

