102
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ I have flagged it for becoming CW. $\endgroup$
    – Rahab
    Commented Dec 5, 2010 at 2:01
  • 2
    $\begingroup$ It would be nice if the answers turn into CW also so we can up-vote them. $\endgroup$
    – Kaveh
    Commented Dec 5, 2010 at 6:55
  • $\begingroup$ answers become CW by default if the question is CW. $\endgroup$
    – Suresh Venkat
    Commented Dec 5, 2010 at 8:17
  • 3
    $\begingroup$ @Suresh: But we have already non-CW answers and they should be turned into CW, too. $\endgroup$
    – Jukka Suomela
    Commented Dec 5, 2010 at 10:43
  • $\begingroup$ @Suresh and @Jukka, how do I CWize my answer? $\endgroup$
    – Alessandro Cosentino
    Commented Dec 5, 2010 at 13:58

41 Answers 41

Reset to default
1
2
46
$\begingroup$

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

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

Improve this answer
$\endgroup$
38
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 29
    $\begingroup$ A warning. the draft is really just that: a draft. There are numerous errors in the draft that got fixed in the printed version (I know this because I ran a summer reading group using the draft and had to constantly correct it from the book) $\endgroup$
    – Suresh Venkat
    Commented Dec 5, 2010 at 6:10
  • 4
    $\begingroup$ The book is really worth buying. Not expensive at all for its value and size. $\endgroup$
    – Dai Le
    Commented Dec 5, 2010 at 15:40
37
$\begingroup$

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

EDIT (Sept 16 '15): The link is broken, I believe the draft is no longer available online.

Improve this answer
$\endgroup$
3
35
$\begingroup$

Let me add the following:

Analytic Combinatorics, by Flajolet and Sedgewick

Codes and Automata (Link Broken), by Berstel, Perrin and Reutenauer

Improve this answer
$\endgroup$
27
$\begingroup$

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

Improve this answer
$\endgroup$
27
$\begingroup$

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/

Improve this answer
$\endgroup$
4
  • $\begingroup$ arggh. how on earth did I forget that one ! $\endgroup$
    – Suresh Venkat
    Commented Dec 6, 2010 at 17:09
  • 1
    $\begingroup$ @Suresh: (Just kidding) A senior moment, perhaps ;) $\endgroup$
    – Sadeq Dousti
    Commented Dec 7, 2010 at 2:03
  • $\begingroup$ arggh. more like a lack-of-coffee moment :) $\endgroup$
    – Suresh Venkat
    Commented Dec 7, 2010 at 6:06
  • 5
    $\begingroup$ And it is no longer available online - the publication date is getting nearer, and I promised the publisher (AMS) not to put it online. Sorry... $\endgroup$
    – Sariel Har-Peled
    Commented Mar 7, 2011 at 2:53
26
$\begingroup$

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

Improve this answer
$\endgroup$
25
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ On the topic of Boolean functions and Fourier analysis: Analysis of Boolean Functions, by Ryan O'Donnell (2014): the pdf version is available here. $\endgroup$
    – Clement C.
    Commented Dec 26, 2014 at 13:10
24
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ Chapter 2 itself is already a very elegant introduction to propositional logic and first order logic, with important tools like Completeness, Compactness, Löwenheim–Skolem, and Hebrand's Theorem. $\endgroup$
    – Dai Le
    Commented Dec 5, 2010 at 3:56
  • 3
    $\begingroup$ I've read many parts of the book, and I highly recommend it for people interested in complexity and logic. For people working in proof complexity I think it's possibly a must. It does not deal with proof complexity lower bounds, which is the major issue of the topic, but it gives the essential logical context of proof complexity. It is especially suited for beginners, and for self study. Literally, no prior knowledge is assumed, everything is explained from scratch and full details are provided for everything. (Also, the draft is almost the same as the book.) $\endgroup$
    – Iddo Tzameret
    Commented Dec 6, 2010 at 8:00
22
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ now that's a nice book. $\endgroup$
    – Suresh Venkat
    Commented Dec 5, 2010 at 8:19
21
$\begingroup$

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.

Improve this answer
$\endgroup$
20
$\begingroup$

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!

Improve this answer
$\endgroup$
18
$\begingroup$

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

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.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Wow, excellent source! $\endgroup$
    – Dai Le
    Commented Mar 16, 2011 at 7:01
16
$\begingroup$

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.

Improve this answer
$\endgroup$
15
$\begingroup$

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

Improve this answer
$\endgroup$
0
13
$\begingroup$

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

Improve this answer
$\endgroup$
12
$\begingroup$

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

Improve this answer
$\endgroup$
12
$\begingroup$

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

Improve this answer
$\endgroup$
12
$\begingroup$

"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. (Link Broken)

Improve this answer
$\endgroup$
11
$\begingroup$

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

Improve this answer
$\endgroup$
11
$\begingroup$

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

Improve this answer
$\endgroup$
11
$\begingroup$

Automata Theory: An Algorithmic Approach by Javier Esparza

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

Improve this answer
$\endgroup$
10
$\begingroup$

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.

Improve this answer
$\endgroup$
10
$\begingroup$

Notes or books about Distributed Algorithms:

Improve this answer
$\endgroup$
10
$\begingroup$

"Logic and Discrete Mathematics for Computer Scientists", by James Caldwell. Manuscript Date: August 22, 2011. Available at: http://www.cs.uwyo.edu/~jlc/courses/2300/book.pdf.

"Data Structures and Algorithms, The Basic Toolbox", by Kurt Mehlhorn. Manuscript Date: August 2008. Available at: http://www.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/.

"An Introduction to Graph Theory and Complex Networks", by Martin Van Steen. Manuscript Date: January 2010. Available at: http://www.distributed-systems.net.

"Category Theory for Computing Science," by Michael Barr and Charles Wells. Available at http://www.tac.mta.ca/tac/reprints/articles/22/tr22.pdf.

"Philosophy of Computer Science," by William J. Rappaport. Manuscript Date: December 24, 2013. Available at: http://www.cse.buffalo.edu/~rapaport/Papers/phics.pdf.

"Fractional Graph Theory: A Rational Approach To The Theory Of Graphs," by Edward Scheinerman And Daniel Ullman. Available at http://www.ams.jhu.edu/~ers/fgt/fgt.pdf.

Improve this answer
$\endgroup$
10
$\begingroup$

"Foundations of Data Science" (pdf) by Hopcroft and Kannan. The text was discussed by Lipton on his blog. As the title implies, the emphasis of the text seems to be applications and issues related to Big Data and Learning problems. It seems to have grown out of this course.

(Update 8/2015) The book now has a third author, Avrim Blum. The pdf link has been updated.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ newer version: cs.cornell.edu/jeh/book112013.pdf $\endgroup$
    – domotorp
    Commented Dec 10, 2013 at 18:34
  • $\begingroup$ and I think the title is Foundations of Data Science. $\endgroup$
    – domotorp
    Commented Dec 10, 2013 at 18:35
  • $\begingroup$ Updated the link to the April 2014 version found on Hopcroft's website. $\endgroup$
    – Logan Mayfield
    Commented Jun 26, 2014 at 0:09
8
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ link please? I couldn't find that list on PlanetMath... $\endgroup$
    – Joshua Grochow
    Commented Mar 20, 2013 at 15:37
  • $\begingroup$ @JoshuaGrochow: Unfortunately, the old link I provided above no longer works. I'll replace it as soon as I find the new link. $\endgroup$
    – Sadeq Dousti
    Commented Mar 23, 2013 at 6:55
7
$\begingroup$

Bayesian Reasoning and Machine Learning, by David Barber.

Improve this answer
$\endgroup$
6
$\begingroup$

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/

Improve this answer
$\endgroup$
1
2

Not the answer you're looking for? Browse other questions tagged or ask your own question.