What are the recent TCS books whose drafts are available online?

Question

Following the post What Books Should Everyone Read, I noticed that there are recent books whose drafts are available online.

For instance, the Approximation Algorithms entry of the above post cites a 2011 book (yet to be published) titled The design of approximation algorithms.

I think knowing recent works is really useful for whoever wants to get a taste of TCS trends. When drafts are available, one can check the books before actually buying them.

So,

What are the recent TCS books whose drafts are available online?

Here, by "recent", I mean something that's no older than ~5 years.

Answer 1

Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani

Answer 2

Several TCS books by Now Publishers can be found in drafts:

• Foundations of Cryptography– A Primer by Oded Goldreich. This is a summarized version of his famous two-volume book on cryptography. (The draft of the two-volume version can be found in Robin's answer.)

• Data Streams: Algorithms and Applications by S. Muthukrishnan.

• Mathematical Aspects of Mixing Times in Markov Chains by Montenegro & Tetali.

• Pairwise Independence and Derandomization by Luby & Widgerson.

• Average-Case Complexity by Bogdanov & Trevisan.

• A Survey of Lower Bounds for Satisfiability and Related Problems by Melkebeek.

• Algorithms and Data Structures for External Memory by Vitter.

• Probabilistic Proof Systems: A Primer by Goldreich. Again, this is a summarized version of a part Goldreich's book Modern Cryptography, Probabilistic Proofs and Pseudorandomness.

• The Design of Competitive Online Algorithms via a Primal-Dual Approach by Buchbinder & Naor.

• Spectral Algorithms by Kannan & Vempala.

• On the Power of Small-Depth Computation by Viola.

• Algorithmic and Analysis Techniques in Property Testing by Ron.

---

In addition, drafts of several Springer books on "Information Security and Cryptography" can be found online:

• Cryptography in Constant Parallel Time by Applebaum.

• A Study of Statistical Zero-Knowledge Proofs by Vadhan.

• Locally Decodable Codes and Private Information Retrieval Schemes by Yekhanin.

• Concurrent Zero Knowledge by Rosen.

Answer 3

Arora and Barak Computational Complexity: A Modern Approach , 2010.

Answer 4

Let me add the following:

Analytic Combinatorics, by Flajolet and Sedgewick

Codes and Automata, by Berstel, Perrin and Reutenauer

Answer 5

Oded Goldreich has several drafts available for download on his webpage.

• Computational Complexity: A Conceptual Perspective (2008)

• P, NP, and NP-Completeness: The Basics of Complexity Theory (2010)

• The Foundations of Cryptography (2001 and 2004)

• A Primer on Pseudorandom Generators (2010)

Answer 6

Expander Graphs and their applications, by Hoory, Linial and Wigderson. This is verging on monograph territory at 123 pages.

Answer 7

Stephen Cook & Phuong Nguyen published a book named Logical Foundations of Proof Complexity in March 2010. There is a draft on Cook's website: here. Unfortunately, I haven't read it.

Answer 8

Reinhard Diestel's Graph Theory (4th edition, 2010), in a variety of electronic formats.

Answer 9

Boolean Function Complexity: Advances and Frontiers by Stasys Jukna.

(Preface) (Table of Contents)

A free draft used to be available as a direct download a while ago (if I remember correctly), but now it seems you can obtain it by filling out a form on his webpage or emailing him.

Answer 10

Sariel Har-Peled has an upcoming book on Geometric Approximation Algorithms. It has been available in draft form as lecture notes for a while now.

http://valis.cs.uiuc.edu/~sariel/teach/notes/aprx/

Answer 11

There is a new upcoming book on Spectral Algorithms by Ravi Kannan and Santosh Vempala covering several latest developments. It covers several applications of spectral methods, algorithms for estimating spectral parameters and low rank approximation of matrices.

Answer 12

Markov Chains and Mixing Times by D.A. Levin, Y. Peres, E.L. Wilmer (2008). Finally a text book covering this broad and ubiquitous topic.

Answer 13

Since Suresh Venkat mentioned the monograph on expanders, I will also mention the following related monographs on the topic of pseudorandomness. The draft of Pseudorandomness by Salil Vadhan (220 pages) is very worth reading. The monograph Parwise Independence and Derandomization by Luby and Wigderson is also nice!

Answer 14

The books in open access from the site of Mathematical Sciences Research Institute:

• Volume 56, Games of No Chance 3, edited by Michael H. Albert and Richard J. Nowakowski, 2009.
• Volume 52, Combinatorial and Computational Geometry, edited by Jacob E. Goodman, János Pach and Emo Welzl, 2005.
• Volume 44, Algorithmic Number Theory, edited by Joe Buhler and Peter Stevenhagen, 2008.
• Volume 42, More Games of No Chance, edited by Richard J. Nowakowski, 2002.
• Volume 29, Games of No Chance, edited by Richard Nowakowski, 1996.

Here I have listed only those books which to me best fit in the definition of TCS.

NB. Books are not drafts and were published.

Answer 15

The discrepancy method, Bernard Chazelle.

Probability on Trees and Networks, Russell Lyons with Yuval Peres

Both are great reads! You might want to grab Lyons-Peres now before they take it offline.

Answer 16

Algorithmic Game Theory, by Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani (2007).

Answer 17

"Models of Computation, Exploring the Power of Computing," by John E. Savage. Available at http://www.cs.brown.edu/~jes/book/pdfs/ModelsOfComputation.pdf.

Answer 18

Hubert Comon, Max Dauchet, Remi Gilleron, Florent Jacquemard, Denis Lugiez, Christof Löding, Sophie Tison, Marc Tommasi: Tree Automata Techniques and Applications

Answer 19

Book by Bruno Courcelle "Graph structure and monadic second-order logic, a language theoretic approach".

Answer 20

Modern Computer Arithmetic by R. P. Brent and P. Zimmermann.

Answer 21

"Descriptive Complexity, Canonisation, and Definable Graph Structure Theory," by Martin Grohe. Date on manuscript: March 7, 2013. Available at: http://www.automata.rwth-aachen.de/~grohe/pub.en.

Answer 22

There is an online draft of the new book "Iterative Methods in Combinatorial Optimization" by Lap Chi Lau, R. Ravi, and Mohit Singh:

http://www.cs.mcgill.ca/~mohit/book/book.html

It is about the iterative rounding method: a new techhnique that can be used to design approximation algorithms for many problems.

Answer 23

Spectra of Graphs by Brouwer and Haemers. I came to this book by way of Chapter 16 (written by Spielman) in Combinatorial Scientific Computing.

Answer 24

PlanetMath lists over 150 books which are available online. The list is updated regularly (the most recent addition being 2011-01-09, as of this writing). Books are math-related, but some of them are useful in TCS, too.

Answer 25

Bayesian Reasoning and Machine Learning, by David Barber.

Answer 26

Automata Theory: An Algorithmic Approach by Javier Esparza

http://www7.in.tum.de/~esparza/automatanotes.html

Answer 27

Networks, Crowds, and Markets: Reasoning About a Highly Connected World by David Easley and Jon Kleinberg.

http://www.cs.cornell.edu/home/kleinber/networks-book/

Answer 28

Notes or books about Distributed Algorithms:

• "A Course on Deterministic Distributed Algorithms" by Jukka Suomela. Available at http://www.cs.helsinki.fi/u/josuomel/dda/dda-print.pdf
• "Principles of Distributed Computing" by Roger Wattenhofer. Available at http://dcg.ethz.ch/lectures/podc_allstars/lecture/podc.pdf

Answer 29

Rajaraman A., Leskovec J., and Ullman J.D. - Mining of Massive Datasets