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.

It would be nice if the answers turn into CW also so we can up-vote them. — Kaveh, Dec 05 '10 at 06:55
@Suresh: But we have already non-CW answers and they should be turned into CW, too. — Jukka Suomela, Dec 05 '10 at 10:43
@Alessandro Cosentino: click edit under your answer and then check the check-box for CW. — Kaveh, Dec 05 '10 at 14:52
See also Radu Grigore's answer for semantics books: http://cstheory.stackexchange.com/questions/3533/books-on-programming-language-semantics/3544#3544 — Suresh Venkat, Dec 05 '10 at 19:33
@Kaveh, @Suresh, @Jukka: Maybe we should have a policy of converting all answers to CW once a question has been made CW? (Can moderators make answers CW too, or does the original poster have to do that?) — Robin Kothari, Dec 06 '10 at 01:03
@Robin: It sounds reasonable but in general CW issues are not completely resolved for me and I would like to discuss CW more generally, so I started a meta discussion. — Kaveh, Dec 06 '10 at 01:28

score 45 · Answer 1 · edited Apr 13 '17 at 12:32

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.
Arithmetic Circuits: A Survey of Recent Results and Open Questions by Amir Shpilka and Amir Yehudayoff (2010), Foundations and Trends® in Theoretical Computer Science: Vol. 5: No. 3–4, pp 207-388. http://dx.doi.org/10.1561/0400000039

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.

score 38 · Answer 2 · answered Dec 05 '10 at 03:10

38

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

answered Dec 05 '10 at 03:10

Mohammad Alaggan

1,812
18
29

29

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) – Suresh Venkat Dec 05 '10 at 06:10
4

The book is really worth buying. Not expensive at all for its value and size. – Dai Le Dec 05 '10 at 15:40

Alessandro Cosentino · Answer 3 · 2015-09-16T21:57:57.230

37

~~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.

edited Sep 16 '15 at 21:57

answered Dec 05 '10 at 05:08

Alessandro Cosentino

4,000
35
43

The link is broken as of 12/10/2013. Perhaps the online access is no longer available? – Logan Mayfield Dec 10 '13 at 16:13
1

@LoganMayfield that's strange, because you can still access the single chapters here: http://www.cs.berkeley.edu/~vazirani/algorithms/ – Alessandro Cosentino Dec 10 '13 at 16:42
1

Here is a link for the book http://www.cse.iitd.ernet.in/~naveen/courses/CSL630/all.pdf – drzbir Feb 07 '17 at 19:54

score 35 · Answer 4 · edited Sep 05 '17 at 21:45

35

Let me add the following:

Analytic Combinatorics, by Flajolet and Sedgewick

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

edited Sep 05 '17 at 21:45

dtt

101
5

answered Dec 05 '10 at 23:57

Hermann Gruber

6,470
1
35
58

score 32 · Answer 5 · edited Feb 04 '17 at 15:22

32

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

edited Feb 04 '17 at 15:22

Clement C.

4,461
29
51

answered Dec 05 '10 at 06:40

Robin Kothari

13,617
2
60
116

score 27 · Answer 6 · answered Dec 05 '10 at 06:13

27

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

answered Dec 05 '10 at 06:13

Suresh Venkat

32,071
4
95
271

score 27 · Answer 7 · answered Dec 06 '10 at 16:35

27

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/

answered Dec 06 '10 at 16:35

Chandra Chekuri

6,999
31
39

arggh. how on earth did I forget that one ! – Suresh Venkat Dec 06 '10 at 17:09
1

@Suresh: (Just kidding) A senior moment, perhaps ;) – Sadeq Dousti Dec 07 '10 at 02:03
arggh. more like a lack-of-coffee moment :) – Suresh Venkat Dec 07 '10 at 06:06
5

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... – Sariel Har-Peled Mar 07 '11 at 02:53

score 25 · Answer 8 · answered Dec 05 '10 at 06:15

25

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

answered Dec 05 '10 at 06:15

Suresh Venkat

32,071
4
95
271

score 25 · Answer 9 · answered Dec 05 '10 at 06:32

25

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.

answered Dec 05 '10 at 06:32

Robin Kothari

13,617
2
60
116

1

On the topic of Boolean functions and Fourier analysis: Analysis of Boolean Functions, by Ryan O'Donnell (2014): the pdf version is available here. – Clement C. Dec 26 '14 at 13:10

score 24 · Answer 10 · answered Dec 05 '10 at 02:26

24

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.

answered Dec 05 '10 at 02:26

Michael Blondin

2,582
21
22

3

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. – Dai Le Dec 05 '10 at 03:56
3

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.) – Iddo Tzameret Dec 06 '10 at 08:00

score 22 · Answer 11 · answered Dec 05 '10 at 08:05

22

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.

answered Dec 05 '10 at 08:05

Martin Schwarz

5,496
25
41

1

now that's a nice book. – Suresh Venkat Dec 05 '10 at 08:19

score 21 · Answer 12 · answered Dec 05 '10 at 04:54

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.

score 20 · Answer 13 · edited Jan 16 '13 at 13:32

20

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!

edited Jan 16 '13 at 13:32

Sadeq Dousti

16,479
9
69
152

answered Dec 05 '10 at 07:54

Dai Le

3,664
1
24
37

Oleksandr Bondarenko · Answer 14 · 2011-03-16T08:16:10.473

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.

score 16 · Answer 15 · answered Mar 08 '11 at 00:57

16

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.

answered Mar 08 '11 at 00:57

Hung Q. Ngo

311
3
7

score 15 · Answer 16 · answered Mar 15 '11 at 19:50

15

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

answered Mar 15 '11 at 19:50

Oleksandr Bondarenko

4,215
1
25
46

score 13 · Answer 17 · answered Aug 25 '11 at 07:49

13

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

answered Aug 25 '11 at 07:49

Martin Schwarz

5,496
25
41

score 12 · Answer 18 · edited Sep 05 '17 at 21:44

12

"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)

edited Sep 05 '17 at 21:44

dtt

101
5

answered Mar 14 '13 at 12:09

lgidwani

182
3
7

score 12 · Answer 19 · answered Jan 25 '11 at 18:59

12

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

answered Jan 25 '11 at 18:59

score 12 · Answer 20 · answered Mar 06 '11 at 18:33

12

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

answered Mar 06 '11 at 18:33

Hermann Gruber

6,470
1
35
58

score 11 · Answer 21 · answered Apr 16 '12 at 23:38

11

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

answered Apr 16 '12 at 23:38

user7545

251
4
8

score 11 · Answer 22 · answered Jan 30 '13 at 05:47

11

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

answered Jan 30 '13 at 05:47

lgidwani

182
3
7

score 11 · Answer 23 · answered Mar 20 '13 at 14:07

11

Automata Theory: An Algorithmic Approach by Javier Esparza

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

answered Mar 20 '13 at 14:07

Alin Stefanescu

1
1
2

score 10 · Answer 24 · answered Feb 14 '13 at 10:42

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

lgidwani · Answer 25 · 2014-02-26T06:29:15.183

"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.

score 10 · Answer 26 · edited Jan 09 '17 at 11:57

10

"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.

edited Jan 09 '17 at 11:57

Richard Cox

119
4

answered Dec 10 '13 at 16:24

Logan Mayfield

977
1
8
18

1

newer version: http://www.cs.cornell.edu/jeh/book112013.pdf – domotorp Dec 10 '13 at 18:34
and I think the title is Foundations of Data Science. – domotorp Dec 10 '13 at 18:35
Updated the link to the April 2014 version found on Hopcroft's website. – Logan Mayfield Jun 26 '14 at 00:09

score 10 · Answer 27 · answered Jun 14 '11 at 09:08

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.

score 8 · Answer 28 · answered Jan 31 '11 at 01:44

8

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.

answered Jan 31 '11 at 01:44

Sadeq Dousti

16,479
9
69
152

link please? I couldn't find that list on PlanetMath... – Joshua Grochow Mar 20 '13 at 15:37
@JoshuaGrochow: Unfortunately, the old link I provided above no longer works. I'll replace it as soon as I find the new link. – Sadeq Dousti Mar 23 '13 at 06:55

score 7 · Answer 29 · answered Jun 14 '11 at 07:56

7

Bayesian Reasoning and Machine Learning, by David Barber.

answered Jun 14 '11 at 07:56

Anthony Labarre

3,264
1
25
33

score 6 · Answer 30 · answered Nov 29 '12 at 12:45

6

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/

answered Nov 29 '12 at 12:45

Arindam Pal

1,591
12
23

score 6 · Answer 31 · answered May 14 '14 at 19:41

6

Devdatt Dubhashi and Alessandro Panconesi: Concentration of Measure for the Analysis of Randomised Algorithms. A first draft is available at http://wwwusers.di.uniroma1.it/~ale/Papers/master.pdf (via geomblog)

answered May 14 '14 at 19:41

Hermann Gruber

6,470
1
35
58

score 4 · Answer 32 · answered Apr 17 '13 at 09:37

4

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

answered Apr 17 '13 at 09:37

Kaveh

21,577
8
82
183

score 4 · Answer 33 · answered Sep 06 '17 at 09:52

4

Parameterized Algorithms by Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.

answered Sep 06 '17 at 09:52

Ronald de Haan

396
1
6

score 3 · Answer 34 · answered Dec 25 '18 at 05:55

3

Introduction to Theoretical Computer Science

Boaz Barak

https://introtcs.org/public/index.html

answered Dec 25 '18 at 05:55

kauray

135
5

score 2 · Answer 35 · edited Aug 18 '15 at 20:54

These 3 books on arithmetic complexity don't seem to have been mentioned till now,

(Amir Shpilka, Amir Yehudayoff)
http://www.cs.tau.ac.il/~shpilka/publications/SY10.pdf
(Xi Chen, Neeraj Kayal, and Avi Wigderson) http://research.microsoft.com/apps/pubs/default.aspx?id=154351
(Neeraj Kayal and Ramprasad Saptharishi) http://research.microsoft.com/apps/pubs/default.aspx?id=212431

Some recent books on learning theory

(Toby Segaran) http://edc.tversu.ru/elib/inf/0251.pdf
(Hastie-Tisbshirani-Friedman)
http://statweb.stanford.edu/~tibs/ElemStatLearn/
(Rakhlin-Sridharan) http://www.cs.cornell.edu/~sridharan/lecnotes.pdf
(Hazan) Online convex optimization: http://ocobook.cs.princeton.edu/

Kayal-Saptharishi is just a survey, not a book. The other two are essentially "survey monographs", which are somewhere in between books and "just surveys," but I suppose they should count, esp. because they are some of the only free book-like expositions of algebraic circuits... :) — Joshua Grochow, Sep 06 '17 at 02:04

Clement C. · Answer 36 · 2017-09-06T01:52:57.157

Tutorials on the Foundations of Cryptography (edited by Yehuda Lindell)

Dedicated to Oded Goldreich

From the Springer page:

Advanced tutorials developed by Benny Applebaum, Boaz Barak, Andrej Bogdanov, Iftach Haitner, Shai Halevi, Yehuda Lindell, Alon Rosen, and Salil Vadhan

Domain and authors inspired by Oded Goldreich, a pioneering scientist, educator and mentor

Appropriate for graduate tutorials and seminars, and for self-study by experienced researchers

5 of the 7 chapters (so far) are available online, on ECCC.

Chapter 1 (ECCC TR17-067): Garbled Circuits as Randomized Encodings of Functions: a Primer (Benny Applebaum)
Chapter 2 (ECCC TR17-065): The Complexity of Public-Key Cryptography (Boaz Barak)
Chapter 3 (ECCC TR17-113): Pseudorandom Functions: Three Decades Later (Andrej Bogdanov, Alon Rosen)
Chapter 4 (ECCC TR17-084): The Many Entropies in One-Way Functions (Iftach Haitner and Salil Vadhan)
Chapter 6 (ECCC TR17-112): How To Simulate It — A Tutorial on the Simulation Proof Technique (Yehuda Lindell)

score 2 · Answer 37 · answered Aug 24 '21 at 21:49

2

Jan Krajíček's Proof Complexity. It not only has lower bound but also upper bound and beyond.

answered Aug 24 '21 at 21:49

hddmss

181
5

score 2 · Answer 38 · answered Aug 25 '21 at 12:29

2

Venkatesan Guruswami, Atri Rudra, Madhu Sudan. Essential Coding Theory, 2019.

answered Aug 25 '21 at 12:29

Bruno

4,449
33
45

score 2 · Answer 39 · answered Nov 12 '23 at 06:01

A bit awkward as it's my own, but the draft of my monograph on distribution testing, "Topics and Techniques in Distribution Testing: A Biased but Representative Sample" (Now Publishers, FnT CIT, 2022) is available online here:

https://ccanonne.github.io/survey-topics-dt.html (direct link to PDF here)

This includes the solutions to the exercises.

Also, if you want the LaTeX source, you can find it here:

https://github.com/ccanonne/survey-dt-fnt-cit

score 1 · Answer 40 · answered Nov 07 '23 at 19:54

1

The following book is about Database Theory, a small subarea of TCS at the border to Data Management: Principles of Databases by Marcelo Arenas, Pablo Barcelo, Leonid Libkin, Wim Martens, and Andreas Pieris.

answered Nov 07 '23 at 19:54

Thomas S

1,417
11
14

score -2 · Answer 41 · answered Mar 24 '14 at 10:59

-2

Foundations of Data Science by John Hopcroft and Ravindran Kannan. It's an amazing book on Algorithms for Big Data Analytics. They call it the 21st century algorithms.

answered Mar 24 '14 at 10:59

Arindam Pal

1,591
12
23

3

It is already mentioned: http://cstheory.stackexchange.com/a/20164 – Kaveh Mar 24 '14 at 11:11

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

41 Answers41

Linked