tag:blogger.com,1999:blog-3722233.post6501442359420419161..comments2024-06-20T12:36:16.541-05:00Comments on Computational Complexity: Math books you can actually readLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger32125tag:blogger.com,1999:blog-3722233.post-60176330306649404212013-07-26T03:35:42.792-05:002013-07-26T03:35:42.792-05:00 number theory books by William Levque number theory books by William LevqueAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70577772448769600442013-06-06T12:10:14.702-05:002013-06-06T12:10:14.702-05:00This comment has been removed by the author.Anonymoushttps://www.blogger.com/profile/03612059057559268183noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58852073112829489482009-03-12T14:12:00.000-05:002009-03-12T14:12:00.000-05:00Complex Variables and Applications by Brown/Church...Complex Variables and Applications by Brown/Churchill<BR/><BR/>Principles of Mathematical Analysis by RudinAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79801358623765719802009-03-09T07:16:00.000-05:002009-03-09T07:16:00.000-05:00"How to prove it" best book ever"How to prove it" best book everAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18217781192192479572008-04-12T04:47:00.000-05:002008-04-12T04:47:00.000-05:00The Best books about cryptography are:Introductio...The Best books about cryptography are:<BR/>Introduction to modern cryptography by Katz and Lindell.<BR/>Foundations of Cryptography by Goldreich.<BR/><BR/>They follow an axiomatic and rigorous approach using computational complexity theory.<BR/><BR/>Generating Functionology by Wilf is very clear and beautiful book on combinatorics.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7720263628901180772008-02-04T14:37:00.000-06:002008-02-04T14:37:00.000-06:00Well I survived Bill's inflicting priority argumen...Well I survived Bill's inflicting priority arguments on me ;)<BR/><BR/>Most of these are (reasonably) short and sweet:<BR/><BR/>Garey and Johnson's classic, "Computers and Intractability" Including doing <B>ALL</B> the exercises. (I didn't read through the whole catalogue of NP-complete problems at the end, though.)<BR/><BR/>Oxtoby, "Measure and Category (2nd ed)" (Springer GTM 2)<BR/><BR/>Koblitz, "An Intro to Number Theory and Cryptography" (Chock full of useful and elegant stuff. I just looked and can't find it on my shelf!! Somebody must have "borrowed" it (gasp).)<BR/><BR/>Quigley, "Manual of Axiomatic Set Theory" Tiny little paperback on set theory. Where I first learned about AC, Zorn, well-orders, ordinals, cardinals, etc. Lets you fill in most of the proofs.<BR/><BR/>Kunen, "Set Theory" While I'm on the subject ... Made it most of the way through this one, but petered out after Chapter 6 (in the middle of forcing).<BR/><BR/>There are several other books that I enjoyed reading from the beginning but never got through, usually just running out of time. E.g.,<BR/>Hartley Rogers's Recursive Functions text;<BR/>Aki Kanamori's "The Higher Infinite" (great title, excruciatingly exact attention to detail in the writing)Unknownhttps://www.blogger.com/profile/07167707679832856429noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25708277991771808532008-01-31T15:18:00.000-06:002008-01-31T15:18:00.000-06:00"Visual Complex Analysis" by Tristan Needham."Visual Complex Analysis" by Tristan Needham.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20114342934511153812008-01-18T14:45:00.000-06:002008-01-18T14:45:00.000-06:00i'll heartily second sipser's intro to theory of c...i'll heartily second sipser's intro to theory of computation. it's the only textbook i ever truly read cover-to-cover (and a solid fraction of it in one sitting)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10193967634279656232008-01-18T14:22:00.000-06:002008-01-18T14:22:00.000-06:00"Ideals, Varieties, and Algorithms" by Cox, Little..."Ideals, Varieties, and Algorithms" by Cox, Little and O'Shea.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10424620993058117382008-01-18T14:21:00.000-06:002008-01-18T14:21:00.000-06:00"Ideals, Varieties, and Algorithms" by Cox, Little..."Ideals, Varieties, and Algorithms" by Cox, Little and O'Shea.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48184195193477271422008-01-17T16:39:00.000-06:002008-01-17T16:39:00.000-06:00If you give me thirty years, I feel confident that...If you give me thirty years, I feel confident that I could read and understand almost any math book.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75950206680252016572008-01-17T12:21:00.000-06:002008-01-17T12:21:00.000-06:00While we are on the subject.... I'm looking for a ...While we are on the subject.... I'm looking for a book with many worked out practical problems in probability (what we used to cal "word problems"). I'd like to periodically do some "drills" and build up my intuition in this area.<BR/><BR/>Thanks.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39713448417779306942008-01-17T07:31:00.000-06:002008-01-17T07:31:00.000-06:00"Linear Algebra Done Right" by Axler."Linear Algebra Done Right" by Axler.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4584000237795227112008-01-17T02:46:00.000-06:002008-01-17T02:46:00.000-06:00"Characteristic Classes" by Milnor and Stasheff is..."Characteristic Classes" by Milnor and Stasheff is pretty much essential reading for an algebraic topology graduate student. I think I must have read and understood about 90% of the book, it's extremely well written and I always go back to it.<BR/><BR/>Otherwise, Nick Higham's "Writing for the Mathematical Sciences" is probably the only maths book that I've read cover-to-cover. But that's not quite a hardcore maths book.Craighttps://www.blogger.com/profile/11394692743596031574noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46506873750294144472008-01-16T23:48:00.000-06:002008-01-16T23:48:00.000-06:00A couple more:Finite Dimensional Vector Spaces - P...A couple more:<BR/><BR/>Finite Dimensional Vector Spaces - Paul Halmos<BR/><BR/>Algebra - Michael ArtinAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44459559913433743472008-01-16T21:22:00.000-06:002008-01-16T21:22:00.000-06:00I read Sipser's Introduction to the Theory of Comp...I read Sipser's Introduction to the Theory of Computation cover-to-cover, and I liked it a lot better than Kozen. It also does go into some topics that are seriously upper-level, which is pleasant.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1717993843189298062008-01-16T21:02:00.000-06:002008-01-16T21:02:00.000-06:00Anonymous 11: Did you do all the problems? Reading...Anonymous 11: Did you do all the problems? Reading Alon & Spencer is just not complete without doing the problems (much more so than other books I thnk)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36081566065066738372008-01-16T19:49:00.000-06:002008-01-16T19:49:00.000-06:00The Probabilistic Method is great. And, although t...The Probabilistic Method is great. And, although they aren't textbooks, I'm amazed that nobody's mentioned John Allen Paulos.Johnhttps://www.blogger.com/profile/18079824074256670713noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81251480120390169832008-01-16T17:51:00.000-06:002008-01-16T17:51:00.000-06:001. Naive Set Theory, by Paul Halmos. Just awesome....1. Naive Set Theory, by Paul Halmos. Just awesome.<BR/>2. Conceptual Mathematics, by F. William Lawvere and Stephen H. Schanuel. An excellent introduction to category theory, and contains a picture-only proof of Cantor's Theorem that card(R) >!= card(N).<BR/>3. Generatingfunctionology, by Herb Wilf. As cool as the title.<BR/>4. Jewels of Stringology, by Maxime Crochemore and Wojciech Rytter. Yeah, it's an algorithms book, but it's still hot.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-620990040574704282008-01-16T17:30:00.000-06:002008-01-16T17:30:00.000-06:00You consider a book readable if you can get throug...You consider a book readable if you can get through it in 20-30 years? Odd...<BR/><BR/>It's also interesting how I disagree with some suggestions on this list. CLR and Motwani-Raghavan are pretty good as references, but I find their organization disjointed making them hard to read straight through. Cover and Thomas I found hugely disappointing (poorly written and a lot of uninteresting material [to me]). Arora-Barak I have found good as a refresher if you already know the material, but hard to learn from.<BR/><BR/>Oh, well, to each their own...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32198231074391295272008-01-16T17:14:00.000-06:002008-01-16T17:14:00.000-06:00linear programming by V. Chvatal is a really amazi...linear programming by V. Chvatal is a really amazing first book for the topic and easily readable cover to cover.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72706994035455669972008-01-16T17:05:00.000-06:002008-01-16T17:05:00.000-06:00Probabilistic method by Alon and SpencerProbabilistic method by Alon and SpencerAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23532334628896227942008-01-16T16:59:00.000-06:002008-01-16T16:59:00.000-06:00What about Concrete Mathematics from Graham, Knuth...What about Concrete Mathematics from Graham, Knuth, and Patashnik?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34925490639023558062008-01-16T16:53:00.000-06:002008-01-16T16:53:00.000-06:00Suresh - definitely a +1 on B&V and Rockefellar.Ot...Suresh - definitely a +1 on B&V and Rockefellar.<BR/><BR/>Other's I think are real page turners.<BR/><BR/>Nocedal and Wright's Numerical Optimization<BR/>Trefethen and Bau's Numerical Linear Algebra<BR/>Dennis and Schnabel Numerical Methods for Unconstrained optimziationAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49849957561560190152008-01-16T15:00:00.000-06:002008-01-16T15:00:00.000-06:00Grunbaum "Convex Polytopes"Grunbaum "Convex Polytopes"Anonymousnoreply@blogger.com