General audience (including high-school students)

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
  • 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).



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)

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Get every new post delivered to your Inbox.

Join 55 other followers

%d bloggers like this: