[Computational Complexity] Math books you can actually read
- How many math books can you read cover-to-cover? How many have you? The problem is that while you can certainly read any discrete math (for ugrads) textbooks cover-to-cover you don't want to- you know most of it.
Computer Science Theory is better than math for this since the field is younger and the books often do not need as much background.
So, which books are just right- hard enough to have things in them of interest, but not so hard that you can't read them. Demanding you be able to read it `cover-to-cover' is rather demanding and also ambigous- do you need to understand everything? I'll define this to just be `read/understood over 90% of the book'
With that in mind, here are the books I've done that for. Its a short list.
- Recursively Enumerable Sets and Degrees by Soare. I had a course in 1980 (by Michael Stob- a PhD student of Soare) that covered about 1/2 of it (in preprint form). I understood about 3/4 of that course. But over the next 20 years I (slowly) read and understood the rest. By 2000 I had it all. I try to retain it by presenting a priority argument argument to someone once in a while. Its getting harder to find someone who wants to see these things who doesn't already know them. I did drag Steven Fenner into a room at CCC06 and forced him to see the proof that there is a minimal pair of r.e. degrees using a tree argument,
- Ramsey Theory by Graham, Rothchild, Spencer. I had about 1/3 of this in a course (by Spencer) in 1978. Over the next 30 years I've read more of it. Now I'm about done.
- Linear Orderings by Rosenstein. Great book, out of print now. Does lots of model theory (E-F games) and recursion theory in a more concrete setting.
- I've read several books by Brams and Taylor about fair division. All are readable. The nice things here is that the math is easy but probably new to most of us. Hardest theorem: there is an envy free discrete protocol to divide a cake between 4 people (or more).
- Communication Complexity by Kushilevitz and Nisan. Reviewed it and used it in a course twice. By the second time I had it all read.
- Proofs that really count by Benjamin and Quinn. This is about proofs of combinatorial identities done by showing that two expressions solve the same problem. Great topic, Great book.
Posted By GASARCH to Computational Complexity at 1/16/2008 01:08:00 PM