<p>Several TCS books by <a href="http://www.nowpublishers.com/product.aspx?product=TCS" rel="noreferrer">Now Publishers</a> can be found in drafts:</p>

<ul>
<li><p><a href="http://www.nowpublishers.com/product.aspx?product=TCS&amp;doi=0400000001" rel="noreferrer">Foundations of Cryptography– A Primer</a> 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 <a href="https://cstheory.stackexchange.com/questions/3540/what-are-the-recent-tcs-books-whose-drafts-are-available-online/3556#3556">Robin's answer</a>.)</p></li>
<li><p><a href="http://www.cs.rutgers.edu/~muthu/stream-1-1.ps" rel="noreferrer">Data Streams: Algorithms and Applications</a> by S. Muthukrishnan.</p></li>
<li><p><a href="http://people.math.gatech.edu/~tetali/PUBLIS/survey.pdf" rel="noreferrer">Mathematical Aspects of Mixing Times in Markov Chains</a> by Montenegro &amp; Tetali.</p></li>
<li><p><a href="http://www.math.ias.edu/~avi/BOOKS/TCS003-1.pdf" rel="noreferrer">Pairwise Independence and Derandomization</a> by Luby &amp; Widgerson.</p></li>
<li><p><a href="http://arxiv.org/abs/cs.CC/0606037" rel="noreferrer">Average-Case Complexity</a> by Bogdanov &amp; Trevisan.</p></li>
<li><p><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.114.3402" rel="noreferrer">A Survey of Lower Bounds for Satisfiability and Related Problems</a> by Melkebeek.</p></li>
<li><p><a href="http://www.ittc.ku.edu/~jsv/Papers/Vit.IO_book.pdf" rel="noreferrer">Algorithms and Data Structures for External Memory</a> by Vitter.</p></li>
<li><p><a href="http://www.wisdom.weizmann.ac.il/~oded/pps-primer.html" rel="noreferrer">Probabilistic Proof Systems: A Primer</a> by Goldreich. Again, this is a summarized version of a part Goldreich's book <a href="http://www.wisdom.weizmann.ac.il/~oded/book1.html" rel="noreferrer">Modern Cryptography, Probabilistic Proofs and Pseudorandomness</a>.</p></li>
<li><p><a href="https://research.microsoft.com/en-us/um/people/nivbuchb/papers/pd-survey.pdf" rel="noreferrer">The Design of Competitive Online Algorithms via a Primal-Dual Approach</a> by Buchbinder &amp; Naor.</p></li>
<li><p><a href="http://www.cc.gatech.edu/~vempala/spectralbook.pdf" rel="noreferrer">Spectral Algorithms</a> by Kannan &amp; Vempala.</p></li>
<li><p><a href="http://www.ccs.neu.edu/home/viola/papers/shallow.pdf" rel="noreferrer">On the Power of Small-Depth Computation</a> by Viola.</p></li>
<li><p><a href="http://www.wisdom.weizmann.ac.il/~oded/PDF/dana-tech.pdf" rel="noreferrer">Algorithmic and Analysis Techniques in Property Testing</a> by Ron.</p></li>
<li><p><a href="http://www.cs.tau.ac.il/~shpilka/publications/SY10.pdf" rel="noreferrer">Arithmetic Circuits: A Survey of Recent Results and Open Questions</a>
by Amir Shpilka and Amir Yehudayoff (2010), Foundations and Trends® in Theoretical Computer Science: Vol. 5: No. 3–4, pp 207-388. <a href="http://dx.doi.org/10.1561/0400000039" rel="noreferrer">http://dx.doi.org/10.1561/0400000039</a></p></li>
</ul>

<hr>

<p>In addition, drafts of several <a href="http://www.springer.com/series/4752?detailsPage=titles" rel="noreferrer">Springer books on "Information Security and Cryptography"</a> can be found online:</p>

<ul>
<li><p><a href="http://www.eng.tau.ac.il/~bennyap/pubs/thesis.pdf" rel="noreferrer">Cryptography in Constant Parallel Time</a> by Applebaum.</p></li>
<li><p><a href="http://groups.csail.mit.edu/cis/theses/salil-phd.ps" rel="noreferrer">A Study of Statistical Zero-Knowledge Proofs</a> by Vadhan.</p></li>
<li><p><a href="http://dspace.mit.edu/handle/1721.1/42242" rel="noreferrer">Locally Decodable Codes and Private Information Retrieval Schemes</a> by Yekhanin.</p></li>
<li><p><a href="http://www.eecs.harvard.edu/~alon/PAPERS/thesis/thesis.ps" rel="noreferrer">Concurrent Zero Knowledge</a> by Rosen.</p></li>
</ul>

CC BY-SA 3.0
2010-12-08T23:33:24.340Z
2015-08-05T15:59:04.233Z
2017-04-13T12:32:28.117Z
Sadeq Dousti
<p>Arora and Barak <a href="http://www.cs.princeton.edu/theory/complexity/">Computational Complexity: A Modern Approach</a> , 2010.</p>

CC BY-SA 2.5
2010-12-05T06:10:38.040Z
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
CC BY-SA 2.5
2010-12-05T15:40:44.317Z
The book is really worth buying. Not expensive at all for its value and size.
Dai Le
CC BY-SA 2.5
2010-12-05T03:10:10.657Z
2010-12-05T03:10:10.657Z
Mohammad Alaggan
<p><strike><a href="http://www.cs.berkeley.edu/~vazirani/algorithms/all.pdf" rel="nofollow">Algorithms</a> by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani</strike></p>

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

CC BY-SA 3.0
2013-12-10T16:13:08.107Z
The link is broken as of 12/10/2013. Perhaps the online access is no longer available?
Logan Mayfield
CC BY-SA 3.0
2013-12-10T16:42:49.170Z
@LoganMayfield that's strange, because you can still access the single chapters here: http://www.cs.berkeley.edu/~vazirani/algorithms/
Alessandro Cosentino
CC BY-SA 3.0
2017-02-07T19:54:43.197Z
Here is a link for the book http://www.cse.iitd.ernet.in/~naveen/courses/CSL630/all.pdf
drzbir
CC BY-SA 3.0
2010-12-05T05:08:12.453Z
2015-09-16T21:57:57.230Z
2015-09-16T21:57:57.230Z
Alessandro Cosentino
<p>Let me add the following:</p>

<p><a href="http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html" rel="nofollow noreferrer">Analytic Combinatorics</a>, by Flajolet and Sedgewick</p>

<p><strike><a href="http://www-igm.univ-mlv.fr/~berstel/LivreCodes/Old/newlivreCodesOld.pdf" rel="nofollow noreferrer">Codes and Automata</a></strike>  (Link Broken), by Berstel, Perrin and Reutenauer</p>

CC BY-SA 3.0
2010-12-05T23:57:08.107Z
2017-09-05T21:45:32.190Z
2017-09-05T21:45:32.190Z
Hermann Gruber
<p><a href="http://www.wisdom.weizmann.ac.il/~oded/books.html" rel="nofollow noreferrer">Oded Goldreich</a> has several drafts available for download on his webpage. </p>

<ul>
<li><p><a href="http://www.wisdom.weizmann.ac.il/~oded/cc-drafts.html" rel="nofollow noreferrer">Computational Complexity: A Conceptual Perspective (2008)</a></p></li>
<li><p><a href="http://www.wisdom.weizmann.ac.il/~oded/bc-drafts.html" rel="nofollow noreferrer">P, NP, and NP-Completeness: The Basics of Complexity Theory (2010)</a></p></li>
<li><p><a href="http://www.wisdom.weizmann.ac.il/~oded/foc-drafts.html" rel="nofollow noreferrer">The Foundations of Cryptography (2001 and 2004)</a></p></li>
<li><p><a href="http://www.wisdom.weizmann.ac.il/~oded/PDF/prg10.pdf" rel="nofollow noreferrer">A Primer on Pseudorandom Generators (2010)</a></p></li>
<li><p><a href="http://www.wisdom.weizmann.ac.il/~oded/pt-intro.html" rel="nofollow noreferrer">Introduction to Property Testing (2017)</a></p></li>
</ul>

CC BY-SA 3.0
2010-12-05T06:40:02.283Z
2017-02-04T15:22:17.113Z
2017-02-04T15:22:17.113Z
Robin Kothari
<p><a href="http://pages.uoregon.edu/dlevin/MARKOV/">Markov Chains and Mixing Times</a> by D.A. Levin, Y. Peres, E.L. Wilmer (2008). Finally a text book covering this broad and ubiquitous topic.</p>

CC BY-SA 2.5
2010-12-05T08:19:25.590Z
now that's a nice book.
Suresh Venkat
CC BY-SA 2.5
2010-12-05T08:05:40.463Z
2010-12-05T08:05:40.463Z
Martin Schwarz
<p>There is a new upcoming book on <a href="http://www.cc.gatech.edu/~vempala/spectralbook.html">Spectral Algorithms</a> 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.</p>

CC BY-SA 2.5
2010-12-05T04:54:57.377Z
2010-12-05T04:54:57.377Z
Shiva Kintali
<p>Since Suresh Venkat mentioned the monograph on expanders, I will also mention the following related monographs on the topic of <em>pseudorandomness</em>. The draft of <a href="http://people.seas.harvard.edu/~salil/pseudorandomness/" rel="noreferrer">Pseudorandomness</a> by Salil Vadhan (220 pages) is very worth reading. The monograph <a href="http://www.math.ias.edu/~avi/BOOKS/TCS003-1.pdf" rel="noreferrer">Parwise Independence and Derandomization</a> by Luby and Wigderson is also nice!</p>

CC BY-SA 3.0
2010-12-05T07:54:50.863Z
2013-01-16T13:32:14.970Z
2013-01-16T13:32:14.970Z
Dai Le
<p>The books in open access from the <a href="http://library.msri.org/books/">site</a> of Mathematical Sciences Research Institute: </p>

<ul>
<li>Volume 56, <a href="http://library.msri.org/books/Book56/index.html">Games of No Chance 3</a>, edited by Michael H. Albert and Richard J. Nowakowski, 2009.</li>
<li>Volume 52, <a href="http://library.msri.org/books/Book52/index.html">Combinatorial and Computational Geometry</a>, edited by Jacob E. Goodman, János Pach and Emo Welzl, 2005.</li>
<li>Volume 44, <a href="http://library.msri.org/books/Book44/index.html">Algorithmic Number Theory</a>, edited by Joe Buhler and Peter Stevenhagen, 2008.</li>
<li>Volume 42, <a href="http://library.msri.org/books/Book42/index.html">More Games of No Chance</a>, edited by Richard J. Nowakowski, 2002.</li>
<li>Volume 29, <a href="http://library.msri.org/books/Book29/index.html">Games of No Chance</a>, edited by Richard Nowakowski, 1996.</li>
</ul>

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

<p>NB. Books are not drafts and were published.</p>

CC BY-SA 2.5
2011-03-16T07:01:18.043Z
Wow, excellent source!
Dai Le
CC BY-SA 2.5
2011-01-26T18:34:32.523Z
2011-03-16T08:16:10.473Z
2011-03-16T08:16:10.473Z
Oleksandr Bondarenko
<p><a href="http://www.cs.princeton.edu/~chazelle/book.html">The discrepancy method</a>, Bernard Chazelle.</p>

<p><a href="http://mypage.iu.edu/~rdlyons/prbtree/prbtree.html">Probability on Trees and Networks</a>, Russell Lyons with Yuval Peres</p>

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

CC BY-SA 2.5
2011-03-08T00:57:37.477Z
2011-03-08T00:57:37.477Z
Hung Q. Ngo
<p><a href="http://diestel-graph-theory.com/">Reinhard Diestel's Graph Theory</a> (4th edition, 2010), in a variety of electronic formats. </p>

CC BY-SA 2.5
2010-12-05T06:13:46.387Z
2010-12-05T06:13:46.387Z
Suresh Venkat
<p>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.</p>

<p><a href="http://valis.cs.uiuc.edu/~sariel/teach/notes/aprx/">http://valis.cs.uiuc.edu/~sariel/teach/notes/aprx/</a></p>

CC BY-SA 2.5
2011-03-07T02:53:55.063Z
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
CC BY-SA 2.5
2010-12-06T17:09:20.483Z
arggh. how on earth did I forget that one !
Suresh Venkat
CC BY-SA 2.5
2010-12-07T02:03:27.557Z
@Suresh: (Just kidding) A senior moment, perhaps ;)
Sadeq Dousti
CC BY-SA 2.5
2010-12-07T06:06:00.617Z
arggh. more like a lack-of-coffee moment :)
Suresh Venkat
CC BY-SA 2.5
2010-12-06T16:35:53.010Z
2010-12-06T16:35:53.010Z
Chandra Chekuri
<p><a href="http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf">Expander Graphs and their applications</a>, by Hoory, Linial and Wigderson. This is verging on monograph territory at 123 pages. </p>

CC BY-SA 2.5
2010-12-05T06:15:42.750Z
2010-12-05T06:15:42.750Z
Suresh Venkat
<p><a href="http://www.thi.informatik.uni-frankfurt.de/~jukna/BFC.html">Boolean Function Complexity: Advances and Frontiers</a> by Stasys Jukna. </p>

<p><a href="http://www.thi.informatik.uni-frankfurt.de/~jukna/pref.html">(Preface)</a> <a href="http://www.thi.informatik.uni-frankfurt.de/~jukna/TOC.html">(Table of Contents)</a></p>

<p>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.</p>

CC BY-SA 3.0
2014-12-26T13:10:58.180Z
On the topic of Boolean functions and Fourier analysis: [Analysis of Boolean Functions](http://analysisofbooleanfunctions.org/), by Ryan O'Donnell (2014): the pdf version is available [here](http://get.analysisofbooleanfunctions.org/).
Clement C.
CC BY-SA 2.5
2010-12-05T06:32:37.253Z
2010-12-05T06:32:37.253Z
Robin Kothari
<p>Stephen Cook &amp; Phuong Nguyen published a book named <a href="http://www.cambridge.org/gb/knowledge/isbn/item2708116/?site_locale=en_GB">Logical Foundations of Proof Complexity</a> in March 2010. There is a draft on Cook's website: <a href="http://www.cs.toronto.edu/~sacook/homepage/book/">here</a>. Unfortunately, I haven't read it.</p>

CC BY-SA 2.5
2010-12-05T03:56:00.943Z
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
CC BY-SA 2.5
2010-12-06T08:00:55.817Z
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
CC BY-SA 2.5
2010-12-05T02:26:20.827Z
2010-12-05T02:26:20.827Z
Michael Blondin
<p><a href="http://www.cambridge.org/journals/nisan/downloads/Nisan_Non-printable.pdf">Algorithmic Game Theory</a>, by Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani (2007).</p>

CC BY-SA 3.0
2011-08-25T07:49:25.673Z
2011-08-25T07:49:25.673Z
Martin Schwarz
<p>Hubert Comon, Max Dauchet, Remi Gilleron, Florent Jacquemard, Denis Lugiez, Christof Löding, Sophie Tison, Marc Tommasi: <a href="http://tata.gforge.inria.fr/">Tree Automata Techniques and Applications</a> </p>

CC BY-SA 2.5
2011-03-06T18:33:53.647Z
2011-03-06T18:33:53.647Z
Hermann Gruber
<p>"Descriptive Complexity, Canonisation, and Definable Graph Structure Theory," by Martin Grohe. Date on manuscript: March 7, 2013. Available at: <strike><a href="http://www.automata.rwth-aachen.de/~grohe/pub.en" rel="nofollow noreferrer">http://www.automata.rwth-aachen.de/~grohe/pub.en</a>.</strike> (Link Broken)</p>

CC BY-SA 3.0
2013-03-14T12:09:00.710Z
2017-09-05T21:44:24.527Z
2017-09-05T21:44:24.527Z
lgidwani
<p>Automata Theory: An Algorithmic Approach 
by Javier Esparza</p>

<p><a href="http://www7.in.tum.de/~esparza/automatanotes.html">http://www7.in.tum.de/~esparza/automatanotes.html</a></p>

CC BY-SA 3.0
2013-03-20T14:07:11.793Z
2013-03-20T14:07:11.793Z
Alin Stefanescu
<p>"Models of Computation, Exploring the Power of Computing," by John E. Savage. Available at <a href="http://www.cs.brown.edu/~jes/book/pdfs/ModelsOfComputation.pdf">http://www.cs.brown.edu/~jes/book/pdfs/ModelsOfComputation.pdf</a>.</p>

CC BY-SA 3.0
2013-01-30T05:47:07.797Z
2013-01-30T05:47:07.797Z
lgidwani
<p><a href="http://www.win.tue.nl/~aeb/2WF02/spectra.pdf">Spectra of Graphs</a> by <a href="http://www.win.tue.nl/~aeb/">Brouwer</a> and <a href="http://lyrawww.uvt.nl/~haemers/home.html">Haemers</a>. I came to this book by way of <a href="http://cs-www.cs.yale.edu/homes/spielman/PAPERS/SGTChapter.pdf">Chapter 16</a> (written by Spielman) in <a href="http://www.crcpress.com/product/isbn/9781439827352">Combinatorial Scientific Computing</a>.</p>

CC BY-SA 3.0
2012-04-16T23:38:57.063Z
2012-04-16T23:38:57.063Z
user7545
<p>Book by Bruno Courcelle "<a href="http://www.labri.fr/perso/courcell/Book/TheBook.pdf">Graph structure and monadic second-order logic, a language theoretic approach</a>".</p>

CC BY-SA 2.5
2011-03-15T19:50:37.733Z
2011-03-15T19:50:37.733Z
Oleksandr Bondarenko
<p>There is an online draft of the new book "Iterative Methods in Combinatorial Optimization" by Lap Chi Lau, R. Ravi, and Mohit Singh:</p>

<p><a href="http://www.cs.mcgill.ca/~mohit/book/book.html">http://www.cs.mcgill.ca/~mohit/book/book.html</a></p>

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

CC BY-SA 3.0
2011-06-14T09:08:44.670Z
2011-06-14T09:08:44.670Z
Bart
<p>"Logic and Discrete Mathematics for Computer Scientists", by James Caldwell. Manuscript Date: August 22, 2011. Available at: <a href="http://www.cs.uwyo.edu/~jlc/courses/2300/book.pdf">http://www.cs.uwyo.edu/~jlc/courses/2300/book.pdf</a>. </p>

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

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

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

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

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

CC BY-SA 3.0
2013-07-03T02:57:14.073Z
2014-02-26T06:29:15.183Z
2014-02-26T06:29:15.183Z
lgidwani
<p>"Foundations of Data Science" (<a href="https://www.cs.cornell.edu/jeh/book.pdf" rel="nofollow noreferrer">pdf</a>) by Hopcroft and Kannan. The text was <a href="http://rjlipton.wordpress.com/2013/12/09/a-negative-impossibility-theorem/" rel="nofollow noreferrer">discussed by Lipton</a> 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 <a href="http://www.cs.cmu.edu/~venkatg/teaching/CStheory-infoage/" rel="nofollow noreferrer">this course</a>.   </p>

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

CC BY-SA 3.0
2013-12-10T18:34:03.410Z
newer version: http://www.cs.cornell.edu/jeh/book112013.pdf
domotorp
CC BY-SA 3.0
2013-12-10T18:35:21.117Z
and I think the title is Foundations of Data Science.
domotorp
CC BY-SA 3.0
2014-06-26T00:09:59.050Z
Updated the link to the April 2014 version found on Hopcroft's website.
Logan Mayfield
CC BY-SA 3.0
2013-12-10T16:24:27.987Z
2017-01-09T11:57:58.200Z
2017-01-09T11:57:58.200Z
Logan Mayfield
<p><a href="http://planetmath.org/?op=listobj&amp;from=books">PlanetMath</a> 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.</p>

CC BY-SA 3.0
2013-03-20T15:37:09.573Z
link please? I couldn't find that list on PlanetMath...
Joshua Grochow
CC BY-SA 3.0
2013-03-23T06:55:26.160Z
@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
CC BY-SA 2.5
2011-01-31T01:44:50.533Z
2011-01-31T01:44:50.533Z
Sadeq Dousti
<p>Notes or books about Distributed Algorithms:</p>

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

CC BY-SA 3.0
2013-02-14T10:42:24.920Z
2013-02-14T10:42:24.920Z
Claudio Biale
<p><a href="http://web4.cs.ucl.ac.uk/staff/D.Barber/pmwiki/pmwiki.php?n=Main.Textbook">Bayesian Reasoning and Machine Learning</a>, by David Barber.</p>

CC BY-SA 3.0
2011-06-14T07:56:42.800Z
2011-06-14T07:56:42.800Z
Anthony Labarre
<p>Networks, Crowds, and Markets: Reasoning About a Highly Connected World by David Easley and Jon Kleinberg.</p>

<p><a href="http://www.cs.cornell.edu/home/kleinber/networks-book/">http://www.cs.cornell.edu/home/kleinber/networks-book/</a></p>

CC BY-SA 3.0
2012-11-29T12:45:07.553Z
2012-11-29T12:45:07.553Z
Arindam Pal
<p>Devdatt Dubhashi and Alessandro Panconesi: Concentration of Measure for the Analysis of Randomised Algorithms. A first draft is available at <a href="http://wwwusers.di.uniroma1.it/~ale/Papers/master.pdf">http://wwwusers.di.uniroma1.it/~ale/Papers/master.pdf</a> (via geomblog)</p>

CC BY-SA 3.0
2014-05-14T19:41:39.397Z
2014-05-14T19:41:39.397Z
Hermann Gruber
<p><a href="http://parameterized-algorithms.mimuw.edu.pl/parameterized-algorithms.pdf" rel="nofollow noreferrer">Parameterized Algorithms</a> by Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.</p>

CC BY-SA 3.0
2017-09-06T09:52:39.027Z
2017-09-06T09:52:39.027Z
Ronald de Haan
<p>Rajaraman A., Leskovec J., and Ullman J.D. - <a href="http://infolab.stanford.edu/~ullman/mmds.html" rel="nofollow">Mining of Massive Datasets</a></p>

CC BY-SA 3.0
2013-04-17T09:37:59.413Z
2013-04-17T09:37:59.413Z
Kaveh
<p><strong>Introduction to Theoretical Computer Science</strong></p>

<p><em>Boaz Barak</em></p>

<p><a href="https://introtcs.org/public/index.html" rel="nofollow noreferrer">https://introtcs.org/public/index.html</a></p>

CC BY-SA 4.0
2018-12-25T05:55:49.547Z
2018-12-25T05:55:49.547Z
kauray
<p>Venkatesan Guruswami, Atri Rudra, Madhu Sudan. <a href="https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/web-coding-book.pdf" rel="nofollow noreferrer">Essential Coding Theory</a>, 2019.</p>

CC BY-SA 4.0
2021-08-25T12:29:20.920Z
2021-08-25T12:29:20.920Z
Bruno
<p>Jan Krajíček's <a href="https://www2.karlin.mff.cuni.cz/%7Ekrajicek/prfdraft.html" rel="nofollow noreferrer">Proof Complexity</a>. It not only has lower bound but also upper bound and beyond.</p>

CC BY-SA 4.0
2021-08-24T21:49:56.940Z
2021-08-24T21:49:56.940Z
Zunchen Huang
<p>A bit awkward as it's my own, but the draft of my monograph on distribution testing, <a href="https://www.nowpublishers.com/article/Details/CIT-114" rel="nofollow noreferrer">&quot;Topics and Techniques in Distribution Testing: A Biased but Representative Sample&quot;</a> (Now Publishers, FnT CIT, 2022) is available online here:</p>
<ul>
<li><a href="https://ccanonne.github.io/survey-topics-dt.html" rel="nofollow noreferrer">https://ccanonne.github.io/survey-topics-dt.html</a> (direct link to PDF <a href="https://ccanonne.github.io/files/misc/main-survey-fnt.pdf" rel="nofollow noreferrer">here</a>)</li>
</ul>
<p>This includes the <a href="https://ccanonne.github.io/files/misc/main-survey-exercises.pdf" rel="nofollow noreferrer">solutions to the exercises</a>.</p>
<p>Also, if you want the LaTeX source, you can find it here:</p>
<ul>
<li><a href="https://github.com/ccanonne/survey-dt-fnt-cit" rel="nofollow noreferrer">https://github.com/ccanonne/survey-dt-fnt-cit</a></li>
</ul>

CC BY-SA 4.0
2023-11-12T06:01:24.690Z
2023-11-12T06:01:24.690Z
Clement C.
<p>These 3 books on arithmetic complexity don't seem to have been mentioned till now, </p>

<ul>
<li><p>(Amir Shpilka, Amir Yehudayoff)<br>
<a href="http://www.cs.tau.ac.il/~shpilka/publications/SY10.pdf" rel="nofollow">http://www.cs.tau.ac.il/~shpilka/publications/SY10.pdf</a></p></li>
<li><p>(Xi Chen, Neeraj Kayal, and Avi Wigderson)        <a href="http://research.microsoft.com/apps/pubs/default.aspx?id=154351" rel="nofollow">http://research.microsoft.com/apps/pubs/default.aspx?id=154351</a></p></li>
<li><p>(Neeraj Kayal and Ramprasad Saptharishi)   <a href="http://research.microsoft.com/apps/pubs/default.aspx?id=212431" rel="nofollow">http://research.microsoft.com/apps/pubs/default.aspx?id=212431</a></p></li>
</ul>

<p>Some recent books on learning theory</p>

<ul>
<li><p>(Toby Segaran) <a href="http://edc.tversu.ru/elib/inf/0251.pdf" rel="nofollow">http://edc.tversu.ru/elib/inf/0251.pdf</a></p></li>
<li><p>(Hastie-Tisbshirani-Friedman)<br>
          <a href="http://statweb.stanford.edu/~tibs/ElemStatLearn/" rel="nofollow">http://statweb.stanford.edu/~tibs/ElemStatLearn/</a></p></li>
<li><p>(Rakhlin-Sridharan)
<a href="http://www.cs.cornell.edu/~sridharan/lecnotes.pdf" rel="nofollow">http://www.cs.cornell.edu/~sridharan/lecnotes.pdf</a></p></li>
<li><p>(Hazan) Online convex optimization: <a href="http://ocobook.cs.princeton.edu/" rel="nofollow">http://ocobook.cs.princeton.edu/</a></p></li>
</ul>

CC BY-SA 3.0
2017-09-06T02:04:48.727Z
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
CC BY-SA 3.0
2015-08-06T04:55:09.767Z
2015-08-18T20:54:14.643Z
2015-08-18T20:54:14.643Z
Student
<p><strong>Tutorials on the Foundations of Cryptography</strong> (edited by Yehuda Lindell)</p>

<p><em>Dedicated to Oded Goldreich</em></p>

<p>From the <a href="http://www.springer.com/us/book/9783319570471" rel="nofollow noreferrer">Springer page</a>:</p>

<blockquote>
  <p>Advanced tutorials developed by Benny Applebaum, Boaz Barak, Andrej Bogdanov, Iftach Haitner, Shai Halevi, Yehuda Lindell, Alon Rosen, and Salil Vadhan</p>
  
  <p>Domain and authors inspired by Oded Goldreich, a pioneering scientist, educator and mentor</p>
  
  <p>Appropriate for graduate tutorials and seminars, and for self-study by experienced researchers</p>
</blockquote>

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

<ul>
<li><p><a href="https://eccc.weizmann.ac.il/report/2017/067/" rel="nofollow noreferrer">Chapter 1 (ECCC TR17-067)</a>: Garbled Circuits as Randomized Encodings of Functions: a Primer (Benny Applebaum)</p></li>
<li><p><a href="https://eccc.weizmann.ac.il/report/2017/065/" rel="nofollow noreferrer">Chapter 2 (ECCC TR17-065)</a>: The Complexity of Public-Key Cryptography (Boaz Barak)</p></li>
<li><p><a href="https://eccc.weizmann.ac.il/report/2017/113/" rel="nofollow noreferrer">Chapter 3 (ECCC TR17-113)</a>: Pseudorandom Functions: Three Decades Later (Andrej Bogdanov, Alon Rosen)</p></li>
<li><p><a href="https://eccc.weizmann.ac.il/report/2017/084/" rel="nofollow noreferrer">Chapter 4 (ECCC TR17-084)</a>: The Many Entropies in One-Way Functions (Iftach Haitner and Salil Vadhan)</p></li>
<li><p><a href="https://eccc.weizmann.ac.il/report/2017/112/" rel="nofollow noreferrer">Chapter 6 (ECCC TR17-112)</a>: How To Simulate It — A Tutorial on the Simulation Proof Technique (Yehuda Lindell)</p></li>
</ul>

CC BY-SA 3.0
2017-09-05T23:49:24.843Z
2017-09-06T01:52:57.157Z
2017-09-06T01:52:57.157Z
Clement C.
<p>The following book is about Database Theory, a small subarea of TCS at the border to Data Management:
<a href="https://github.com/pdm-book/community" rel="nofollow noreferrer">Principles of Databases by Marcelo Arenas, Pablo Barcelo, Leonid Libkin, Wim Martens, and Andreas Pieris.</a></p>

CC BY-SA 4.0
2023-11-07T19:54:23.223Z
2023-11-07T19:54:23.223Z
Thomas S
<p><a href="http://research.microsoft.com/en-us/people/kannan/book-dec-30-2013.pdf" rel="nofollow">Foundations of Data Science</a> by John Hopcroft and Ravindran Kannan. It's an amazing book on Algorithms for Big Data Analytics. They call it the 21st century algorithms.</p>

CC BY-SA 3.0
2014-03-24T11:11:50.853Z
It is already mentioned: http://cstheory.stackexchange.com/a/20164
Kaveh
CC BY-SA 3.0
2014-03-24T10:59:43.780Z
2014-03-24T10:59:43.780Z
Arindam Pal
<p>Following the post <a href="https://cstheory.stackexchange.com/questions/3253/what-books-should-everyone-read">What Books Should Everyone Read</a>, I noticed that there are recent books whose drafts are available online. </p>

<p>For instance, the <a href="https://cstheory.stackexchange.com/questions/3253/what-books-should-everyone-read/3466#3466">Approximation Algorithms</a> entry of the above post cites a 2011 book (yet to be published) titled <a href="http://www.designofapproxalgs.com/" rel="noreferrer">The design of approximation algorithms</a>.</p>

<p>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.</p>

<p>So,</p>

<blockquote>
  <p>What are the recent TCS books whose drafts are available online?</p>
</blockquote>

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

CC BY-SA 2.5
2010-12-05T02:01:44.133Z
I have flagged it for becoming CW.
Rahab
CC BY-SA 2.5
2010-12-05T06:55:23.820Z
It would be nice if the answers turn into CW also so we can up-vote them.
Kaveh
CC BY-SA 2.5
2010-12-05T08:17:42.113Z
answers become CW by default if the question is CW.
Suresh Venkat
CC BY-SA 2.5
2010-12-05T10:43:30.647Z
@Suresh: But we have already non-CW answers and they should be turned into CW, too.
Jukka Suomela
CC BY-SA 2.5
2010-12-05T13:58:23.403Z
@Suresh and @Jukka, how do I CWize my answer?
Alessandro Cosentino
CC BY-SA 2.5
2010-12-05T14:52:28.167Z
@Alessandro Cosentino: click edit under your answer and then check the check-box for CW.
Kaveh
CC BY-SA 2.5
2010-12-05T19:33:15.767Z
See also Radu Grigore's answer for semantics books: http://cstheory.stackexchange.com/questions/3533/books-on-programming-language-semantics/3544#3544
Suresh Venkat
CC BY-SA 2.5
2010-12-06T01:03:38.257Z
@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
CC BY-SA 2.5
2010-12-06T01:28:00.273Z
@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](http://meta.cstheory.stackexchange.com/questions/759/new-community-wiki-policy).
Kaveh
<reference-request><big-list><books>
What are the recent TCS books whose drafts are available online?
Rahab
# What are the recent TCS books whose drafts are available online?

(Asked by: username_0 on 2010-12-05)

Following the post [What Books Should Everyone Read](https://cstheory.stackexchange.com/questions/3253/what-books-should-everyone-read), I noticed that there are recent books whose drafts are available online.

For instance, the [Approximation Algorithms](https://cstheory.stackexchange.com/questions/3253/what-books-should-everyone-read/3466#3466) entry of the above post cites a 2011 book (yet to be published) titled [The design of approximation algorithms](http://www.designofapproxalgs.com/).

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.

**Tags:** reference-request, big-list, books

> **Comments:**
> **username_0**: I have flagged it for becoming CW.  
> **username_1**: It would be nice if the answers turn into CW also so we can up-vote them.  
> **username_2**: answers become CW by default if the question is CW.  
> **username_3**: @Suresh: But we have already non-CW answers and they should be turned into CW, too.  
> **username_4**: @Suresh and @Jukka, how do I CWize my answer?  
> **username_1**: @username_4: click edit under your answer and then check the check-box for CW.  
> **username_2**: See also Radu Grigore's answer for semantics books: http://cstheory.stackexchange.com/questions/3533/books-on-programming-language-semantics/3544#3544  
> **username_5**: @username_1, @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?)  
> **username_1**: @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](http://meta.cstheory.stackexchange.com/questions/759/new-community-wiki-policy).  

---

## 40 answers

### Answer by username_6 on 2010-12-08. Score: 46

Several TCS books by [Now Publishers](http://www.nowpublishers.com/product.aspx?product=TCS) can be found in drafts:

* [Foundations of Cryptography– A Primer](http://www.nowpublishers.com/product.aspx?product=TCS&doi=0400000001) 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](https://cstheory.stackexchange.com/questions/3540/what-are-the-recent-tcs-books-whose-drafts-are-available-online/3556#3556).)
* [Data Streams: Algorithms and Applications](http://www.cs.rutgers.edu/~muthu/stream-1-1.ps) by S. Muthukrishnan.
* [Mathematical Aspects of Mixing Times in Markov Chains](http://people.math.gatech.edu/~tetali/PUBLIS/survey.pdf) by Montenegro & Tetali.
* [Pairwise Independence and Derandomization](http://www.math.ias.edu/~avi/BOOKS/TCS003-1.pdf) by Luby & Widgerson.
* [Average-Case Complexity](http://arxiv.org/abs/cs.CC/0606037) by Bogdanov & Trevisan.
* [A Survey of Lower Bounds for Satisfiability and Related Problems](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.114.3402) by Melkebeek.
* [Algorithms and Data Structures for External Memory](http://www.ittc.ku.edu/~jsv/Papers/Vit.IO_book.pdf) by Vitter.
* [Probabilistic Proof Systems: A Primer](http://www.wisdom.weizmann.ac.il/~oded/pps-primer.html) by Goldreich. Again, this is a summarized version of a part Goldreich's book [Modern Cryptography, Probabilistic Proofs and Pseudorandomness](http://www.wisdom.weizmann.ac.il/~oded/book1.html).
* [The Design of Competitive Online Algorithms via a Primal-Dual Approach](https://research.microsoft.com/en-us/um/people/nivbuchb/papers/pd-survey.pdf) by Buchbinder & Naor.
* [Spectral Algorithms](http://www.cc.gatech.edu/~vempala/spectralbook.pdf) by Kannan & Vempala.
* [On the Power of Small-Depth Computation](http://www.ccs.neu.edu/home/viola/papers/shallow.pdf) by Viola.
* [Algorithmic and Analysis Techniques in Property Testing](http://www.wisdom.weizmann.ac.il/~oded/PDF/dana-tech.pdf) by Ron.
* [Arithmetic Circuits: A Survey of Recent Results and Open Questions](http://www.cs.tau.ac.il/~shpilka/publications/SY10.pdf)
  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"](http://www.springer.com/series/4752?detailsPage=titles) can be found online:

* [Cryptography in Constant Parallel Time](http://www.eng.tau.ac.il/~bennyap/pubs/thesis.pdf) by Applebaum.
* [A Study of Statistical Zero-Knowledge Proofs](http://groups.csail.mit.edu/cis/theses/salil-phd.ps) by Vadhan.
* [Locally Decodable Codes and Private Information Retrieval Schemes](http://dspace.mit.edu/handle/1721.1/42242) by Yekhanin.
* [Concurrent Zero Knowledge](http://www.eecs.harvard.edu/~alon/PAPERS/thesis/thesis.ps) by Rosen.


---

### Answer by username_7 on 2010-12-05. Score: 38

Arora and Barak [Computational Complexity: A Modern Approach](http://www.cs.princeton.edu/theory/complexity/) , 2010.

> **Comments:**
> **username_2**: 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)  
> **username_8**: The book is really worth buying. Not expensive at all for its value and size.  

---

### Answer by username_4 on 2010-12-05. Score: 37

[Algorithms](http://www.cs.berkeley.edu/~vazirani/algorithms/all.pdf) 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.

> **Comments:**
> **username_9**: The link is broken as of 12/10/2013. Perhaps the online access is no longer available?  
> **username_4**: @LoganMayfield that's strange, because you can still access the single chapters here: http://www.cs.berkeley.edu/~vazirani/algorithms/  
> **username_10**: Here is a link for the book http://www.cse.iitd.ernet.in/~naveen/courses/CSL630/all.pdf  

---

### Answer by username_11 on 2010-12-05. Score: 35

Let me add the following:

[Analytic Combinatorics](http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html), by Flajolet and Sedgewick

[Codes and Automata](http://www-igm.univ-mlv.fr/~berstel/LivreCodes/Old/newlivreCodesOld.pdf) (Link Broken), by Berstel, Perrin and Reutenauer


---

### Answer by username_5 on 2010-12-05. Score: 32

[Oded Goldreich](http://www.wisdom.weizmann.ac.il/~oded/books.html) has several drafts available for download on his webpage.

* [Computational Complexity: A Conceptual Perspective (2008)](http://www.wisdom.weizmann.ac.il/~oded/cc-drafts.html)
* [P, NP, and NP-Completeness: The Basics of Complexity Theory (2010)](http://www.wisdom.weizmann.ac.il/~oded/bc-drafts.html)
* [The Foundations of Cryptography (2001 and 2004)](http://www.wisdom.weizmann.ac.il/~oded/foc-drafts.html)
* [A Primer on Pseudorandom Generators (2010)](http://www.wisdom.weizmann.ac.il/~oded/PDF/prg10.pdf)
* [Introduction to Property Testing (2017)](http://www.wisdom.weizmann.ac.il/~oded/pt-intro.html)


---

### Answer by username_2 on 2010-12-05. Score: 27

[Reinhard Diestel's Graph Theory](http://diestel-graph-theory.com/) (4th edition, 2010), in a variety of electronic formats.


---

### Answer by username_16 on 2010-12-06. Score: 27

username_17 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/>

> **Comments:**
> **username_2**: arggh. how on earth did I forget that one !  
> **username_6**: @Suresh: (Just kidding) A senior moment, perhaps ;)  
> **username_2**: arggh. more like a lack-of-coffee moment :)  
> **username_17**: 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...  

---

### Answer by username_2 on 2010-12-05. Score: 26

[Expander Graphs and their applications](http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf), by Hoory, Linial and Wigderson. This is verging on monograph territory at 123 pages.


---

### Answer by username_5 on 2010-12-05. Score: 25

[Boolean Function Complexity: Advances and Frontiers](http://www.thi.informatik.uni-frankfurt.de/~jukna/BFC.html) by Stasys Jukna.

[(Preface)](http://www.thi.informatik.uni-frankfurt.de/~jukna/pref.html) [(Table of Contents)](http://www.thi.informatik.uni-frankfurt.de/~jukna/TOC.html)

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.

> **Comments:**
> **username_18**: On the topic of Boolean functions and Fourier analysis: [Analysis of Boolean Functions](http://analysisofbooleanfunctions.org/), by Ryan O'Donnell (2014): the pdf version is available [here](http://get.analysisofbooleanfunctions.org/).  

---

### Answer by username_19 on 2010-12-05. Score: 24

Stephen Cook & Phuong Nguyen published a book named [Logical Foundations of Proof Complexity](http://www.cambridge.org/gb/knowledge/isbn/item2708116/?site_locale=en_GB) in March 2010. There is a draft on Cook's website: [here](http://www.cs.toronto.edu/~sacook/homepage/book/). Unfortunately, I haven't read it.

> **Comments:**
> **username_8**: 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.  
> **username_20**: 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.)  

---

### Answer by username_12 on 2010-12-05. Score: 22

[Markov Chains and Mixing Times](http://pages.uoregon.edu/dlevin/MARKOV/) by D.A. Levin, Y. Peres, E.L. Wilmer (2008). Finally a text book covering this broad and ubiquitous topic.

> **Comments:**
> **username_2**: now that's a nice book.  

---

### Answer by username_13 on 2010-12-05. Score: 21

There is a new upcoming book on [Spectral Algorithms](http://www.cc.gatech.edu/~vempala/spectralbook.html) 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 by username_8 on 2010-12-05. Score: 20

Since username_2 mentioned the monograph on expanders, I will also mention the following related monographs on the topic of *pseudorandomness*. The draft of [Pseudorandomness](http://people.seas.harvard.edu/~salil/pseudorandomness/) by Salil Vadhan (220 pages) is very worth reading. The monograph [Parwise Independence and Derandomization](http://www.math.ias.edu/~avi/BOOKS/TCS003-1.pdf) by Luby and Wigderson is also nice!


---

### Answer by username_14 on 2011-01-26. Score: 18

The books in open access from the [site](http://library.msri.org/books/) of Mathematical Sciences Research Institute:

* Volume 56, [Games of No Chance 3](http://library.msri.org/books/Book56/index.html), edited by Michael H. Albert and Richard J. Nowakowski, 2009.
* Volume 52, [Combinatorial and Computational Geometry](http://library.msri.org/books/Book52/index.html), edited by Jacob E. Goodman, János Pach and Emo Welzl, 2005.
* Volume 44, [Algorithmic Number Theory](http://library.msri.org/books/Book44/index.html), edited by Joe Buhler and Peter Stevenhagen, 2008.
* Volume 42, [More Games of No Chance](http://library.msri.org/books/Book42/index.html), edited by Richard J. Nowakowski, 2002.
* Volume 29, [Games of No Chance](http://library.msri.org/books/Book29/index.html), 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.

> **Comments:**
> **username_8**: Wow, excellent source!  

---

### Answer by username_15 on 2011-03-08. Score: 16

[The discrepancy method](http://www.cs.princeton.edu/~chazelle/book.html), Bernard Chazelle.

[Probability on Trees and Networks](http://mypage.iu.edu/~rdlyons/prbtree/prbtree.html), Russell Lyons with Yuval Peres

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


---

### Answer by username_14 on 2011-03-15. Score: 15

Book by username_32 Courcelle "[Graph structure and monadic second-order logic, a language theoretic approach](http://www.labri.fr/perso/courcell/Book/TheBook.pdf)".


---

### Answer by username_12 on 2011-08-25. Score: 13

[Algorithmic Game Theory](http://www.cambridge.org/journals/nisan/downloads/Nisan_Non-printable.pdf), by Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani (2007).


---

### Answer by username_11 on 2011-03-06. Score: 12

Hubert Comon, Max Dauchet, Remi Gilleron, Florent Jacquemard, Denis Lugiez, Christof Löding, Sophie Tison, Marc Tommasi: [Tree Automata Techniques and Applications](http://tata.gforge.inria.fr/)


---

### Answer by username_21 on 2013-03-14. Score: 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)


---

### Answer by username_22 on 2013-03-20. Score: 11

Automata Theory: An Algorithmic Approach
by Javier Esparza

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


---

### Answer by username_21 on 2013-01-30. Score: 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>.


---

### Answer by username_23 on 2012-04-16. Score: 11

[Spectra of Graphs](http://www.win.tue.nl/~aeb/2WF02/spectra.pdf) by [Brouwer](http://www.win.tue.nl/~aeb/) and [Haemers](http://lyrawww.uvt.nl/~haemers/home.html). I came to this book by way of [Chapter 16](http://cs-www.cs.yale.edu/homes/spielman/PAPERS/SGTChapter.pdf) (written by Spielman) in [Combinatorial Scientific Computing](http://www.crcpress.com/product/isbn/9781439827352).


---

### Answer by username_24 on 2011-06-14. Score: 10

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 by username_21 on 2013-07-03. Score: 10

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


---

### Answer by username_9 on 2013-12-10. Score: 10

"Foundations of Data Science" ([pdf](https://www.cs.cornell.edu/jeh/book.pdf)) by Hopcroft and Kannan. The text was [discussed by Lipton](http://rjlipton.wordpress.com/2013/12/09/a-negative-impossibility-theorem/) 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](http://www.cs.cmu.edu/~venkatg/teaching/CStheory-infoage/).

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

> **Comments:**
> **username_25**: newer version: http://www.cs.cornell.edu/jeh/book112013.pdf  
> **username_25**: and I think the title is Foundations of Data Science.  
> **username_9**: Updated the link to the April 2014 version found on Hopcroft's website.  

---

### Answer by username_27 on 2013-02-14. Score: 10

Notes or books about Distributed Algorithms:

* "A Course on Deterministic Distributed Algorithms" by username_3. 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 by username_6 on 2011-01-31. Score: 8

[PlanetMath](http://planetmath.org/?op=listobj&from=books) 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.

> **Comments:**
> **username_26**: link please? I couldn't find that list on PlanetMath...  
> **username_6**: @JoshuaGrochow: Unfortunately, the old link I provided above no longer works. I'll replace it as soon as I find the new link.  

---

### Answer by username_28 on 2011-06-14. Score: 7

[Bayesian Reasoning and Machine Learning](http://web4.cs.ucl.ac.uk/staff/D.Barber/pmwiki/pmwiki.php?n=Main.Textbook), by David Barber.


---

### Answer by username_29 on 2012-11-29. Score: 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/>


---

### Answer by username_11 on 2014-05-14. Score: 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)


---

### Answer by username_30 on 2017-09-06. Score: 4

[Parameterized Algorithms](http://parameterized-algorithms.mimuw.edu.pl/parameterized-algorithms.pdf) by Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.


---

### Answer by username_1 on 2013-04-17. Score: 4

Rajaraman A., Leskovec J., and Ullman J.D. - [Mining of Massive Datasets](http://infolab.stanford.edu/~ullman/mmds.html)


---

### Answer by username_31 on 2018-12-25. Score: 3

**Introduction to Theoretical Computer Science**

*Boaz Barak*

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


---

### Answer by username_32 on 2021-08-25. Score: 2

Venkatesan Guruswami, Atri Rudra, Madhu Sudan. [Essential Coding Theory](https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/web-coding-book.pdf), 2019.


---

### Answer by username_33 on 2021-08-24. Score: 2

Jan Krajíček's [Proof Complexity](https://www2.karlin.mff.cuni.cz/%7Ekrajicek/prfdraft.html). It not only has lower bound but also upper bound and beyond.


---

### Answer by username_18 on 2023-11-12. Score: 2

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"](https://www.nowpublishers.com/article/Details/CIT-114) (Now Publishers, FnT CIT, 2022) is available online here:

* <https://ccanonne.github.io/survey-topics-dt.html> (direct link to PDF [here](https://ccanonne.github.io/files/misc/main-survey-fnt.pdf))

This includes the [solutions to the exercises](https://ccanonne.github.io/files/misc/main-survey-exercises.pdf).

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

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


---

### Answer by username_34 on 2015-08-06. Score: 2

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/>

> **Comments:**
> **username_26**: 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... :)  

---

### Answer by username_18 on 2017-09-05. Score: 2

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

*Dedicated to Oded Goldreich*

From the [Springer page](http://www.springer.com/us/book/9783319570471):

> 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)](https://eccc.weizmann.ac.il/report/2017/067/): Garbled Circuits as Randomized Encodings of Functions: a Primer (Benny Applebaum)
* [Chapter 2 (ECCC TR17-065)](https://eccc.weizmann.ac.il/report/2017/065/): The Complexity of Public-Key Cryptography (Boaz Barak)
* [Chapter 3 (ECCC TR17-113)](https://eccc.weizmann.ac.il/report/2017/113/): Pseudorandom Functions: Three Decades Later (Andrej Bogdanov, Alon Rosen)
* [Chapter 4 (ECCC TR17-084)](https://eccc.weizmann.ac.il/report/2017/084/): The Many Entropies in One-Way Functions (Iftach Haitner and Salil Vadhan)
* [Chapter 6 (ECCC TR17-112)](https://eccc.weizmann.ac.il/report/2017/112/): How To Simulate It — A Tutorial on the Simulation Proof Technique (Yehuda Lindell)


---

### Answer by username_35 on 2023-11-07. Score: 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.](https://github.com/pdm-book/community)


---

### Answer by username_29 on 2014-03-24. Score: -2

[Foundations of Data Science](http://research.microsoft.com/en-us/people/kannan/book-dec-30-2013.pdf) by John Hopcroft and Ravindran Kannan. It's an amazing book on Algorithms for Big Data Analytics. They call it the 21st century algorithms.

> **Comments:**
> **username_1**: It is already mentioned: http://cstheory.stackexchange.com/a/20164  

---

