31
votes
Accepted
Where to learn more about what Theoretical Computer Science is?
First, "theoretical computer science" means different things to different people. I think for most users on this site, a historical caricature (which reflects some modern sociological tendencies) is ...
- 37.8k
7
votes
Information and Coding Theory Texts
Maybe not so math oriented but with math rigor:
Elements of Information Theory by Thomas M. Cover, Joy A. Thomas
Essential Coding Theory by Venkatesan Guruswami, Atri Rudra and Madhu Sudan
- 191
6
votes
What Books Should Everyone Read?
A new addition to the list is a book "Foundations of Data Science" by Blum, Hopcroft and Kannan: https://www.cs.cornell.edu/jeh/book.pdf
6
votes
Where to learn more about what Theoretical Computer Science is?
The Nature of Computation by Cristopher Moore and Stephan Mertens.
- 161
4
votes
Information and Coding Theory Texts
Both texts in the other answer are great texts, and the Guruswami, Rudra, Sudan book is more based in the TCS approach to coding theory, which may be relevant to the potential reader. The books below ...
- 2,070
4
votes
Free books (or course materials) on undergraduate algorithms
Jeff Erickson's lecture notes on Algorithms are free, with a Creative Commons license. Other than Algorithms, this site also contains lecture notes for Models of Computation, which are also with a CC ...
4
votes
What are the recent TCS books whose drafts are available online?
Parameterized Algorithms by Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.
4
votes
What Books Should Everyone Read?
Parameterized complexity
It might worth adding an answer since no one mentioned this area.
A comprehensible, well written quite recent book is
Parameterized Algorithms, M. Cygan et al., 2015
...
3
votes
What is the best text of computation theory/theory of computation?
I recommend Math and Computation by Avi Wigderson if you're mainly interested in complexity theory. This is probably best supplemented by other books mentioned in this thread, as it's less rigorous. ...
3
votes
What are the recent TCS books whose drafts are available online?
Introduction to Theoretical Computer Science
Boaz Barak
https://introtcs.org/public/index.html
3
votes
What Books Should Everyone Read?
Algorithmic Game Theory
Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani. Algorithmic Game Theory. Cambridge University Press, 24 de set. de 2007
History of Computer Science
COOPER, S. ...
2
votes
What are the recent TCS books whose drafts are available online?
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 ...
2
votes
What are the recent TCS books whose drafts are available online?
Venkatesan Guruswami, Atri Rudra, Madhu Sudan. Essential Coding Theory, 2019.
2
votes
What are the recent TCS books whose drafts are available online?
Jan Krajíček's Proof Complexity. It not only has lower bound but also upper bound and beyond.
2
votes
What are the recent TCS books whose drafts are available online?
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 ...
1
vote
Regarding Elements of Programming, is a uniqueness of the value type sufficient for equality testing?
Looking at the book, they give a really good example where representational equality doesn't imply equality. You have two unordered collections, which are equal if after sorting and removing ...
- 51
1
vote
What are the popular science books that inspire TCS?
I will suggest the following books.
The Golden Ticket: P, NP, and the Search for the Impossible by Lance Fortnow.
The book is written for all kind of readers and doesn't require you to know anything ...
1
vote
What are the recent TCS books whose drafts are available online?
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 ...
1
vote
What is the best text of computation theory/theory of computation?
It is very hard to define what best means! Anyway, The nature of computation by Cris Moore and Stephen Mertens is very good. The book is nice to either get an introduction to the big ideas of the ...
1
vote
What is the best text of computation theory/theory of computation?
I recommend "Computability and Logic" by George S. Boolos and John P. Burgess. It's formal, rigorous and fairly thorough. It's a book on computability only, not covering computational ...
1
vote
What is the best text of computation theory/theory of computation?
See Elements of Computation Theory by Arindama Singh.
Only top scored, non community-wiki answers of a minimum length are eligible