#415 in Computers & technology books
Use arrows to jump to the previous/next product
Reddit mentions of Computational Complexity: A Modern Approach
Sentiment score: 6
Reddit mentions: 8
We found 8 Reddit mentions of Computational Complexity: A Modern Approach. Here are the top ones.
or
Used Book in Good Condition
Specs:
| Height | 10 Inches |
| Length | 7 Inches |
| Number of items | 1 |
| Weight | 6.1288508836 Pounds |
| Width | 1.31 Inches |
What do you mean by "I want to be computer scientist?" Do you want to do research for a living, e.g, work in academia or for a lab? Or is your goal more along the lines of, "I want to learn more about computer science?" If the former, you're not going to get far without a degree, usually a Ph.D is necessary. If the latter is your goal then the 'traditional' math subjects would be 'discrete' subjects like probability and combinatorics. Linear algebra is heavily used in machine learning, and I believe PDEs are used as well.
On the computer science side, computability theory and computational complexity are necessary. Sipser is the standard for computability theory, and I like Arora/Barak for complexity (I don't necessarily recommend buying on amazon; that price for Sipser is outrageous).
You can self-study it pretty nicely using the Arora-Barak textbook. An intro to computability and complexity would cover the first 2 chapters (plus some computability stuff up to like Rice's theorem) and an advanced class would cover the book up to interactive proof protocols or the PCP theorem. Also, a nice detour once you picked up some knowledge is parameterized complexity theory -- there is a pretty nice textbook by Grohe and Flum which also touches descriptive complexity theory, but you might want to study some logic beforehand (being comfortable with FO and MSO as well as the complexity of model checking for those classes).
Edit: I dont know how stuff works at your university, but here you can enroll in pretty much any class if you just ask the professor to manually enroll you. Might be worth a try!
The fact that you are still operating under of the assumptions that the Chicago and Austrian schools provide shows that your personal understanding of economics is at least 60 years old.
Get a book on complexity theory. If you are the practical guy you claim to be, I'm sure you will enjoy it.
Here's one for the layman: http://www.amazon.com/COMPLEXITY-EMERGING-SCIENCE-ORDER-CHAOS/dp/0671872346
Her's one if you are into math:
http://www.amazon.com/Computational-Complexity-A-Modern-Approach/dp/0521424267/ref=pd_sim_sbs_b_2
To put it simply, We could argue for years about the examples you gave simply because the complexity of those situations allows for a multitude of different, yet similarly rational, arguments (a fact which, as an admirer of the Austrian school, I'm sure you can agree with). There is a great little bit on Wikipedia's page on economic models (http://en.wikipedia.org/wiki/Economic_model) - under the heading "Are economic models falsifiable?":
The sharp distinction between falsifiable economic models and those that are not is by no means a universally accepted one. Indeed one can argue that the ceteris paribus (all else being equal) qualification that accompanies any claim in economics is nothing more than an all-purpose escape clause (See N. de Marchi and M. Blaug.) The all else being equal claim allows holding all variables constant except the few that the model is attempting to reason about. This allows the separation and clarification of the specific relationship. However, in reality all else is never equal, so economic models are guaranteed to not be perfect. The goal of the model is that the isolated and simplified relationship has some predictive power that can be tested, mainly that it is a theory capable of being applied to reality.
So the point of an economic model, indeed the point of any model is to, in the words of Wolfram, "Examine certain essential features of a system and idealize away everything else." Models are, by their very nature incomplete. There is also an infinite number of possible models, each with a varying degree of accuracy. With these two points in mind, it seems foolish for one to plant a stake in the ground at any one of them and say, with certainty, that this one is the best one. It is also similarly foolish to ask others to provide, immediately, models which will yield better results in every standard, or else you will go back to the old ones. Unfortunately, progress is made through trial and error, not sitting at a desk with head in hands.
The most complete/modern book on it is Arora and Barak (a free draft is available online, but I think the published version is more complete). However, depending on your background, it might be too dense to start with, in which case maybe try Papadimitriou's book (though I'm less familiar with it, so I'm not confident in this recommendation).
Aaronson's book is probably more entertaining than either of these, but I don't think it can actually be used to learn the subject.
Read all of Aurora and Barak's Complexity Theory: A Modern Approach: http://www.amazon.com/Computational-Complexity-Approach-Sanjeev-Arora/dp/0521424267
If this book is too difficult, then I wouldn't suggest attempting to resolve P vs NP.
Oi. Disclaimer: I haven't bought a book in the field in a while, so there might be some new greats that I'm not familiar with. Also, I'm old and have no memory, so I may very well have forgotten some greats. But here is what I can recommend.
I got my start with Koblitz's Course in Number Theory and Cryptography and Schneier's Applied Cryptography. Schneier's is a bit basic, outdated, and erroneous in spots, and the guy is annoying as fuck, but it's still a pretty darned good intro to the field.
If you're strong at math (and computation and complexity theory) then Oded Goldreich's Foundations of Cryptography Volume 1 and Volume 2 are outstanding. If you're not so strong in those areas, you may want to come up to speed with the help of Sipser and Moret first.
Also, if you need to shore up your number theory and algebra, Victor Shoup is the man.
At this point, you ought to have a pretty good base for building on by reading research papers.
One other note, two books that I've not looked at but are written by people I really respect Introduction to Modern Cryptography by Katz and Lindell and Computational Complexity: A Modern Approach by Arora and Barak.
Hope that helps.
Well, canon would be Garey & Johnson, but it's a bit behind the times. Arora & Barak as /u/DarkSayed suggests, Papadimitriou, and Sipser are all good alternatives.
Maybe you should use all of that free time of yours to look at some CS theory then :)