Surveys

General audience (including high-school students)

• Description of TCS by Avrim Blum.
• Could Your iPod Be Holding the Greatest Mystery in Modern Science? by Bernard Chazelle
• The Importance of Mathematics by Timothy Gowers – talks also about specific theoretical computer science examples, but also the general points apply very strongly to TCS as well.
• The Small-World Phenomenon and Decentralized Search by Jon Kleinberg, SIAM News, Volume 37, Number 3, April 2004
  A mathematical model of social networks that captures the small world phenomenon and our ability to find “paths” in such networks.
• A New Map Traces the Limits of Computation, Quanta Magazine, 2015.
  Consequences of the Strong Exponential Time Hypothesis, in the broader context of computational complexity theory.
• Who can name the bigger number? by Scott Aaronson
  From a child’s game to the definition of the Ackermann’s function, the busy beaver problem, the undecidability of the halting problem, and definability paradoxes.
• Quantum computing for high-school students by Scott Aaronson
  The title says it all.
• Computer Scientists Optimize Innovative Ad Auction by Sara Robinson
• Richard Kaye’s Minesweeper NP-Completeness Pages
  Web page and associated articles that introduce the notion of NP-completeness and show that “Minesweeper is NP-complete.” Minsweeper was the focus in 2000 for a series of popular lectures by Ian Stewart on NP-completeness connected with the Clay Mathematics Institute. Includes a link to a talk about the result and a followup article, but unfortunately not the original Mathematical Intelligencer article.
• How To Explain Zero-Knowledge Protocols To Your Children
  Bedtime story that illustrates the notion of “simulator” used in cryptographic zero-knowledge proofs. Introduces the exceedingly clever Mick Ali as the descendant of Ali Baba. Beware: most people I try this on ask me “but why didn’t Mick Ali just walk in one side of the cave and then walk out the other?” Replying “because that’s how the math we are trying to allegorize actually works” is not so satisfying.
• Kid Krypto by Neal Koblitz. Article that discusses strategies for teaching “kid cryptography” to high school (and younger) students. Includes “Kid RSA,” an averaging protocol secure against honest but curious kids, and “perfect codes.” Also includes experience with trying out these ideas with actual high school students.
• Computer Science Unplugged by Tim Bell, Ian H. Witten and Mike Fellows. A number of games designed to teach a variety of mostly TCS concepts.
• Theory of Computation: A Scientific Perspective by Oded Goldreich and Avi Wigderson – provides an assessment of the Theory of Computing (TOC) as a fundamental scientific discipline. The focus is on the important scientific role of TOC, and on its great achievements, productivity and impact (both scientific and technological) so far. Also includes brief layman-level introductions to four concrete topics.
• Can Random Coin Flips Speed Up a Computer? by David Zuckerman. An introduction to randomness and computation targeting a general audience.

For CS/Math/Science audience

• Beyond Computation, video of a public lecture (sponsored by the Simons Institute) by Michael Sipser on the P vs. NP question, with a panel discussion moderated by Richard Karp
• P, NP and Mathematics by Avi Wigderson
• On the Interaction of Theoretical Computer Science and Mathematics by Avi Wigderson
• NP-completeness: A retrospective by Christos Papadimitriou
  In 1995, a library search found that 6,000 papers a year were published with “NP-complete” in their title, abstract or list of keywords. In 2015, a Google search finds in excess of 13 million hits. What makes this notion so useful and ubiquitous?
• The history and status of the P vs NP question by Mike Sipser
  It includes the famous letter of Godel to Von Neumann
• The Computational Worldview and the Sciences: a Report on Two Workshops, by Sanjeev Arora, Avrim Blum, Leonard Schulman, Alistair Sinclair, and Vijay Vazirani (2007). Discusses many connections between theoretical computer science and game theory and economics, quantum information and computation, statistical physics, neuroscience, systems biology and genetics, synthetic biology, control theory, nanotechnology, astrophysics, social sciences, and mathematics.
• An Introduction to Bioinformatics Algorithms by Jones and Pevzner. A good introduction to how the study of algorithms has shaped the course of Biology in recent decades. Also has good biopics of some of the leading figures from TCS in bioinformatics, including Karp, Myers, and Haussler.
• Randomness and Computation by Oded Goldreich
  Following a general introduction to the two notions and their possible relation, the essey contains brief accounts of pseudorandomness and probabilistic proof systems and every shorter accounts of cryptography and sub-linear time algorithms.
• Algorithms Unplugged, 41 chapters on many facets of algorithms, written for a general scientific audience (edited by Berthold Voecking, Helmut Alt, Martin Dietzfelbinger, Rudiger Reischuk, Christian Scheideler, Heribert Vollmer, and Dorothea Wagner).

Research-oriented

• A personal view of average-case complexity by Russell Impagliazzo
  From Pessiland to Algorithmica, a tour of the five possible worlds that result from the possible answers to various open questions in complexity theory.
• Email and the unexpected powers of interaction by Laszlo Babai On the events and the results leading up to interactive proofs for space-bounded computation. (IP=PSPACE).
• Massive Data Streams Research: Where to Go by S. Muthukrishnan.
• Lattice Cryptography: A White Paper by Daniele Micciancio.
• Theory in Practice for System Design and Verification, by Rajeev Alur, Tom Henzinger, and Moshe Y. Vardi. Success stories about turning theoretical advances into practical impact.
• Recent Interactions between TCS and Quantum Physics, by Scott Aaronson. Three case studies to illustrate influence of theoretical computer science on quantum physics.

Popular books (not aimed at students)

• Computers Ltd: What they really can’t do by David Harel. This is a beautiful, well-written and enjoyable book. It presents with meticulous clarity the fundamental results of computability and complexity theory to a non-mathematical audience, and briefly surveys novel models of computation such as quantum computing and molecular computing. Harel also explains how the computational intractability of some problems can be put to good use in fields like public-key cryptography. There should be more books like this one!
• Algorithmics: The Spirit of Computing by David Harel and Yishai Feldman. From the Amazon page: “First published in 1987, explains the basic ideas of algorithms, their structures, and how they manipulate data in computer programs. Of interest to programmers, systems analysts and designers, and software engineers, but the technical level is low enough to be accessible to readers with almost no mathematics or computer background.” Makes it sound like a version of _What Is Mathematics?_ for TCS.
• Godel, Escher Bach: An Eternal Golden Braid by Douglas Hofstadter. Belongs at least as much to TCS as it does to AI. This book is the first exposure to TCS ideas for many people.
• Turing by Christos Papadimitriou. A novel about computation.
• Alan Turing: The Enigma by Andrew Hodges. The biography of one of our founding fathers.
• Out Of Their Minds by Dennis Shasha and Cathy Lazere. Interviews with 15 notable computer scientists, including our own Edsger Dijkstra, Michael Rabin, Donald Knuth, Robert Tarjan, Leslie Lamport, Steve Cook, and Leonid Levin.

Ideas from Other Fields (to inspire us)

• The physicists are the unquestioned masters in exposition and outreach. Here are some inspirations: http://interactions.org/quantumdiaries/ http://www.interactions.org/cms/
• The Clay Mathematics Institute sponsored a series of popular lectures on NP-completeness in 2000. They also provided support for the PCMI/IAS program on Computational Complexity that year. They also do outreach and education concerning pure and applied mathematical topics.