Linked Questions

485 votes
72 answers

What papers should everyone read?

This question is (inspired by)/(shamefully stolen from) a similar question at MathOverflow, but I expect the answers here will be quite different. We all have favorite papers in our own respective ...
155 votes
39 answers

What videos should everybody watch?

Stanford University now has a Youtube channel, with free access to HD video of full courses on everything from dynamical systems to quantum entanglement. More conferences and workshops are ...
102 votes
41 answers

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

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 ...
123 votes
15 answers

What Lecture Notes Should Everyone Read?

There has been several questions with the same scheme as this one: What papers should everyone read What books should everyone read What are the recent TCS books whose drafts are available online ...
93 votes
14 answers

What kind of mathematical background is needed for complexity theory?

I am currently an undergraduate student, bound to graduate this year. After graduation, I am considering to work towards a TCS master/PhD. I have begun wondering what fields of mathematics are ...
chazisop's user avatar
  • 3,751
43 votes
9 answers

References for TCS proof techniques

Are there any references (online or in book form) that organize and discuss TCS theorems by proof technique? Garey and Johnson do this for the various kinds of widget constructions needed for NP-...
36 votes
14 answers

Book on Probability

While I have passed some courses on probability theory, both in the high school and the university, I have a hard time reading TCS papers when it comes to probability. It seems that the authors of ...
38 votes
12 answers

Books on automata theory for self-study

I need a finite automata theory book with lots of examples that I can use for self-study and to prepare for exams.
52 votes
4 answers

Why do we consider log-space as a model of efficient computation (instead of polylog-space) ?

This might be a subjective question rather than one with a concrete answer, but anyway. In complexity theory we study the notion of efficient computations. There are classes like $\mathsf{P}$ stands ...
Hsien-Chih Chang 張顯之's user avatar
38 votes
7 answers

Books on programming language semantics

I've been reading Nielson & Nielson's "Semantics with Applications", and I really like the subject. I'd like to have one more book on programming language semantics -- but I really can get only ...
Jay's user avatar
  • 982
27 votes
12 answers

What are the popular science books that inspire TCS?

There is a reputation, that in computer science, we do not have popular science books. Of course that's not really true! (In the same spirit of list of What Books Should Everyone Read?, What papers ...
58 votes
5 answers

What CS blogs should everyone read?

Many top notch computer science researchers and research groups) maintain active blogs that keep us updated on the latest research in the authors' fields of interest. In most cases, blog posts are ...
22 votes
6 answers

References on Circuit Lower Bounds

Preamble Interactive proof systems and Arthur-Merlin protocols were introduced by Goldwasser, Micali and Rackoff and Babai back in 1985. At first, it was thought that the former is more powerful than ...
Sadeq Dousti's user avatar
  • 16.5k
12 votes
7 answers

What is the best text of computation theory/theory of computation?

In University we used the Sipser text and while at the time I understood most of it, I forgot most of it as well, so it of course didn't leave all to great of an impression. I borrowed that book and ...
17 votes
3 answers

Formal representation of rings in computations

While reading a paper about using algebraic methods to detect some induced subgraphs, it appears that edge ideal is an important tool connecting commutative algebra and graph theory. Since I'm not ...
Hsien-Chih Chang 張顯之's user avatar

15 30 50 per page