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
6
$\begingroup$

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)

Improve this answer
$\endgroup$
4
$\begingroup$

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

Improve this answer
$\endgroup$
4
$\begingroup$

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

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

Introduction to Theoretical Computer Science

Boaz Barak

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

Improve this answer
$\endgroup$
2
$\begingroup$

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

Some recent books on learning theory

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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... :) $\endgroup$
    – Joshua Grochow
    Commented Sep 6, 2017 at 2:04
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
$\begingroup$

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:

This includes the solutions to the exercises.

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

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
-2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
1
2

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