> In particular, the level of math in academic computer science research made some progress with Knuth and since then has, in a word, sucked.
Could you elaborate on this? As someone currently pursuing a PhD in theoretical computer science, I often simply tell (nontechnical/nonacademic) people that I study mathematics rather than computer science, so this offhand remark is somewhat at odds with my personal experience.
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 believe you mean Max-Cut can be 2 approximated with the trivial random algorithm. Min cut can be solved exactly, and that algorithm would give an expected n^2 approx factor (for min cut).
"Perhaps more important was that the subject, who was none other than Marshall himself, failed to develop an ulcer. Note also that the disease resolved without treatment."
This story suggest that he didn't get an ulcer (but he did get all the first symptoms) and that he didn't treat it with (antibiotics) which he did and which eventually cured his own symptoms (and nearly cost him his marriage as his wife left him shortly after doing this).
"As with many tales of dedicated discoverers, you marvel at the tolerance of the family. When Marshall conducted his experiment on himself, he and his wife Ariadne, a psychologist, had four children aged between 10 and 3. He didn't inform Ariadne, or any of his colleagues, about what he was doing, mainly because he knew they'd object.
“I'm a selfish so-and-so”
“A few days after taking the bacteria I began to feel this heavy fullness after eating, and then on day five the vomiting started. One of the reasons I didn't tell my wife about it was that she had whiplash from a car accident. There was a lot of chaos in the family and in the middle of this each morning I would wake before dawn and run to the toilet to vomit. I had bad breath and I looked terrible. You have to admit I'm a selfish so-and-so to even go ahead with the experiment.”
Ten days after drinking the bacteria, Marshall had an endoscopy and other tests to show that his previously bug-free stomach was thoroughly infected and that he was showing the same signs as his patients.
“At that point I couldn't restrain myself; I had to tell the wife. She was speechless.” He laughs. “But it's easier to ask for forgiveness than permission.” She insisted that he took antibiotics to clear up the infection straight away, though Marshall wanted to continue until he had a full-blown ulcer."
Also gastronome enteritis and related diseases was responsible for over 5k deaths (globally) -- a week -- during the period it was known but not accepted 1983 - 1997.
"Marshall swallowed a culture of the bacterium. A week later, he began suffering acute symptoms of gastritis, and biopsies revealed that he had developed both infection with H. pylori and severe acute gastritis. Fortunately, the sequel was a successful case of "Physician, heal thyself"!
further:
"At this stage, bismuth subcitrate was commonly used to treat ulcers, although it was uncertain how the drug worked. Marshall surmised that it might kill the H. pylori bacteria, and he subsequently discovered that a combination of bismuth with antibiotics completely eradicated the bacteria. He then set out to test the hypothesis that elimination of H. pylori could result in a permanent cure of gastric ulcer."
"From 1985 to 1987, Warren and Marshall studied the use of antibiotics as treatment for ulcer. Their finding that 80% of patients were permanently cured of their ulcer if H. pylori were eradicated, proved a landmark in clinical gastroenterology practice. It resulted in a complete reassessment of ulcer treatment, and this therapy is now accepted as an essential part of the management of ulcer disease."
stupid has the one hell of a hangover.
Either he's trying to make the style mirror the content intentionally, or he just doesn't care much for standard English. I disagree either way.