Good exposition in Theoretical Computer Science

What makes a great article in Theoretical Computer Science?

  • clarity of the exposition
  • conceptual perspective
  • exposition of the intuition
  • reflections about the meaning of the results
  • self-contained
  • paints the bigger picture

To give an example, the introduction should always contain:

  1. the problem
  2. the contribution
  3. the context (including related works)

Examples

The following are examples recognized for their exposition.

General

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

Oded Goldreich’s In a World of P=BPP https://www.wisdom.weizmann.ac.il/~oded/PDF/bpp.pdf

Proof outline

“Undirected Connectivity in Log-Space” by Omer Reingold. https://omereingold.files.wordpress.com/2014/10/sl.pdf

“Geometry, Flows, and Graph-Partitioning Algorithms” by Sanjeev Arora, Satish Rao, and Umesh Vazirani. https://www.cs.princeton.edu/~arora/pubs/arvcacm.pdf Doi:10.1145/1400181.1400204

Intuition

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. https://arxiv.org/abs/math/0406038

Luca Trevisan’s Extractors and pseudorandom generators https://lucatrevisan.github.io/pubs/extractor-full.pdf

Big picture

http://arxiv.org/pdf/0806.1978v5.pdf

Resources