7
$\begingroup$

I'm very interested in Computer Science (computational complexity, etc.). I've already finished a University course in the subject (using Sipser's "Introduction to the Theory of Computation").

I know the basics, i.e. Turing Machines, Computability (Halting problem and related reductions), Complexity classes (time and space, P/NP, L/NL, a little about BPP).

Now, I'm looking for a good book to learn about some more advanced concepts. Any ideas?

  • 2
    I think this would be more appropriate at Stack Overflow, no?2010-07-21
  • 2
    What is your definition of CS? The post looks like you are referring to theory of computation.2010-07-21
  • 2
    @Ben - Good question. It's sort of the reason I asked this. Computer Science is a mathematical field, as such it belongs here. There is some overlap, but for serious analysis of computational complexity, I don't think Stack Overflow is the right place (most people there are programmer, not mathematicians).2010-07-21
  • 0
    @Mgccl - Yes, I'm referring to theory of computation / computational complexity. But that entire branch of mathematics is called "Computer Science" (confusing it with "Computer Science" as used to mean "a degree in programming"). [edit - ok this cross posting has got to stop! Cross posted Mgccl, then Katie! :)]2010-07-21
  • 6
    can I ask why this was closed? Besides a possible need to change "Computer Science" to "Theoretical Computer Science" or somesuch in the title, and maybe remove "Best," this seems an appropriate question related to learning mathematics.2010-07-21
  • 0
    I'm voting to reopen, because I think questions about books should be appropriate. Even MO does not typically close them. It should be community wiki, though.2010-07-21
  • 0
    @Akhil - I think the problem wasn't that it was about a book, it was the Computer Science aspect of it. Agree about the cw, my bad.2010-07-21
  • 1
    @Edan: Theoretical computer science is essentially mathematics, and MO has accepted it on its website -- note that there are people like Scott Aaronson and Peter Shor active there. I don't see why we should kick out lower level tcs questions.2010-07-21
  • 0
    @Akhil - I *don't* think we should kick it out, I think we should include it. By the way, I knew Scott Aaronson was active in MO, didn't know Peter Shor was there as well.2010-07-22
  • 0
    I did a little digging and from what I can find, most of the books on computational theory appear to be introductory books that cover all of the topics you mentioned (automata, regular expressions, regular languages, context-free languages, undecidability, complexity). The more advanced books appear to be exclusively on a specific topic. Can you specify what topics you are interested in - that might help with book suggestions.2010-07-23
  • 0
    This question could be more appropriate here: http://cstheory.stackexchange.com/2010-12-04
  • 0
    @Akhil: I can think of all sorts of advanced computational complexity texts, but I'm at a loss to think of a modern advanced text on automata (concepts touched on via the Chomsky hierarchy).2011-05-09

6 Answers 6