Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
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 ...
Joshua Grochow's user avatar
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
hddmss's user avatar
  • 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.
John Donn's user avatar
  • 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 ...
kodlu's user avatar
  • 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 ...
Aravind Reddy's user avatar
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 ...
ian.p.swift's user avatar
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