I agree: The key, maybe nearly all the content, of theoretical computer science is math.
As we design more complex systems in the future, we will need math to know at least about correctness, performance, and economy.
If you are learning the math, then terrific, and you have one heck of an advantage.
While independent study is often crucial, I advise you to have essentially all of an undergraduate major in pure math and a carefully selected Masters in math with also a lot of pure math. Getting all that on your own or while being a 'computer science' student will be tough.
For "sucks", I've just read far too much material by CS profs where they try to use or do math and make a mess. The first symptom is that they don't know how to write math, say, as in Rudin, Birkhoff, Feller, Doob, Coddington, Dieudonne, Bourbaki, etc. The second symptom is that they didn't absorb the standard but rarely explained 'rules' for notation. E.g., there is the disaster NP which by the usual notation just CANNOT be a name and, instead, just MUST be a product of some kind. NP is borrowing from common programming language notation based on, say, limitations of punched cards! Next, there is the problem of failing to understand that, in English speaking communities, math is written in complete English sentences. Then the common practice of using mnemonic variable names as a substitute for English is totally unacceptable and totally missing in good math. Next, beyond writing and notation, when the CS profs start to get into the actual math, they blow it again. E.g., there is a love for saying 'map' and then just stopping, apparently believing something meaningful has been said. It has NOT! Instead, just saying 'map' omits the DEFINITION of the 'map'. Saying 'map' without a definition is meaningless. Such writing and notation is snake oil instead of medicine, cardboard instead of carpentry.
One of the most recent disasters I saw was just screaming out for the 101 level of statistical hypothesis tests but totally missed it. Statistical hypothesis testing was understood in at least some detail by K. Pearson over 100 years ago; the social scientists have had this material cold for over 60 years.
Next, I wrote a paper in computer science. Looking for a journal, I sent copies to several computer science journals, including some of the best ones. From two of the editors in chief, I got back essentially the same: "Neither I nor anyone on my board of editors has the prerequisites to review your paper." For one editor in chief, of one of the best journals, I wrote him tutorials for two weeks before he gave up.
I thought about submitting to a theoretical computer science journal, and the editor wrote me that my paper looked good for his journal. But I submitted to Elsevier's 'Information Sciences' instead to get wider readership for the part of my paper that was for practice. Then came the review process: It was grim. I suspect that in the end the editor in chief walked the paper around his campus; some mathematicians told him my math was okay but they didn't know about the importance for computing, and some CS profs said it was nice for computing but they didn't know about the math.
The way Knuth did and wrote math in 'The Art of Computer Programming' was mostly not very advanced but fine. Since then my impression is suckage.
There's no royal road to math, and it's not a spectator sport. The prerequisites I listed take about six years, and more experience is helpful. Nearly no CS profs have those prerequisites, and it shows.
Net, the dichotomy is clear: Essentially every math prof I ever had or ever read at least knows how to write and do math, especially with definitions, theorems, and proofs. Other than Knuth, essentially every CS prof I ever had or read at best floundered.
You should read more of Chazelle or Tarjan; they both write their maths very clearly.
Thank you for an amazing series of faux-blog posts on this thread. As an undergraduate hoping to enter math research, these have been invaluable to me. I can't upvote you enough times.
Sure, Tarjan is a good mathematician. Maybe CS wants to claim him, but math should keep him for themselves! And the math of operations research -- Cinlar, Nemhauser, Kuhn, etc. -- is good math.
Bear in mind that computer science is quite young -- clarity, unambiguity and formalism in mathematics were not much better in XVII and XVIII centuries. Everything will improve over time, I believe.
I agree. In pretty much all of my theoretical computer science courses, whenever it came to the math there always seemed to be a lot of hand-waving and noise, but not a lot of content. Some were better than others, but when I consider some of the scores I got on tests (much too high!) for basically just puking up random math formulas, I was beginning to suspect that the TAs (and possibly the professors) didn't understand this stuff much better than I did.
I agree: The key, maybe nearly all the content, of theoretical computer science is math.
As we design more complex systems in the future, we will need math to know at least about correctness, performance, and economy.
If you are learning the math, then terrific, and you have one heck of an advantage.
While independent study is often crucial, I advise you to have essentially all of an undergraduate major in pure math and a carefully selected Masters in math with also a lot of pure math. Getting all that on your own or while being a 'computer science' student will be tough.
For "sucks", I've just read far too much material by CS profs where they try to use or do math and make a mess. The first symptom is that they don't know how to write math, say, as in Rudin, Birkhoff, Feller, Doob, Coddington, Dieudonne, Bourbaki, etc. The second symptom is that they didn't absorb the standard but rarely explained 'rules' for notation. E.g., there is the disaster NP which by the usual notation just CANNOT be a name and, instead, just MUST be a product of some kind. NP is borrowing from common programming language notation based on, say, limitations of punched cards! Next, there is the problem of failing to understand that, in English speaking communities, math is written in complete English sentences. Then the common practice of using mnemonic variable names as a substitute for English is totally unacceptable and totally missing in good math. Next, beyond writing and notation, when the CS profs start to get into the actual math, they blow it again. E.g., there is a love for saying 'map' and then just stopping, apparently believing something meaningful has been said. It has NOT! Instead, just saying 'map' omits the DEFINITION of the 'map'. Saying 'map' without a definition is meaningless. Such writing and notation is snake oil instead of medicine, cardboard instead of carpentry.
One of the most recent disasters I saw was just screaming out for the 101 level of statistical hypothesis tests but totally missed it. Statistical hypothesis testing was understood in at least some detail by K. Pearson over 100 years ago; the social scientists have had this material cold for over 60 years.
Next, I wrote a paper in computer science. Looking for a journal, I sent copies to several computer science journals, including some of the best ones. From two of the editors in chief, I got back essentially the same: "Neither I nor anyone on my board of editors has the prerequisites to review your paper." For one editor in chief, of one of the best journals, I wrote him tutorials for two weeks before he gave up.
I thought about submitting to a theoretical computer science journal, and the editor wrote me that my paper looked good for his journal. But I submitted to Elsevier's 'Information Sciences' instead to get wider readership for the part of my paper that was for practice. Then came the review process: It was grim. I suspect that in the end the editor in chief walked the paper around his campus; some mathematicians told him my math was okay but they didn't know about the importance for computing, and some CS profs said it was nice for computing but they didn't know about the math.
The way Knuth did and wrote math in 'The Art of Computer Programming' was mostly not very advanced but fine. Since then my impression is suckage.
There's no royal road to math, and it's not a spectator sport. The prerequisites I listed take about six years, and more experience is helpful. Nearly no CS profs have those prerequisites, and it shows.
Net, the dichotomy is clear: Essentially every math prof I ever had or ever read at least knows how to write and do math, especially with definitions, theorems, and proofs. Other than Knuth, essentially every CS prof I ever had or read at best floundered.