Survey Papers and Essays
General Audience | CS/Math/Science Audience |
Research-oriented | Blogs | Popular Books | Other Fields
Click here for instructions on how to make edits, including the password.
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 caputes the small world phenomenon and our ability to find "paths" in such networks.
- 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 Clay Public Lecture by Michael Sipser on the P vs. NP question.
- P, NP 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 2005, a Google search finds in excess of 300,000 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
- 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.
Research-oriented
Blogs
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 byDennis 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)