The Blog of Scott Aaronson If you take nothing else from this blog: quantum computers won't solve hard problems instantly by just trying all solutions in parallel.
Also, next pandemic, let's approve the vaccines faster!
A reader named Hernan asked me for my opinion of a well-known rant by Jonathan Katz of Washington University, about why young people shouldn’t go into academic science since there are so few jobs and the jobs that there are stink anyway. I posted my response in the comments section, but since it seems to be of general interest I thought I’d make a proper entry of it.
Katz is correct that opportunities in academic science (at least in the US) are much scarcer than they were during the Cold War; I think government shortsightedness deserves a huge part of the blame for that. On the other hand, countless would-be grad students have already followed the invisible hand and taken Katz’s advice, and are doing quite well in Wall Street, Silicon Valley, etc. So the ones going to grad school are mostly the ones willing to assume the (by now well-known) risks: if they weren’t, they wouldn’t be there.
My fundamental disagreement with Katz is that I think PhD work is increasingly excellent preparation for industry careers. Of course, in some cases (e.g. a quantum computing PhD going to work for an Internet startup), it’s hard to argue that the PhD provides much beyond general skills like analytical thinking, teamwork, project completion, etc., and that those skills couldn’t just as well be obtained elsewhere. But even in those cases, I think a PhD at least won’t hurt your chances in industry these days (notwithstanding Phil Greenspun’s PhD expunging service). So what the PhD does is to give many people an opportunity to spend six years advancing human knowledge and doing something they enjoy, before switching to something that’s actually rewarded by the economy. (One corollary is that, if you’re not enjoying grad school, then you shouldn’t be there. But this is just an instance of a general rule: don’t choose a career option that causes you years of suffering in the hope that the suffering will end later; it probably won’t.)
Furthermore, if there used to be a stigma attached to leaving grad school for industry, I think that’s basically vanished, and that now many PhD programs even see training students for industry as a fundamental part of their mission.
I can’t comment on the rest of Katz’s complaints (the need for conformity, the burden of writing grant proposals, etc.), except to say that so far, my own experience has been more positive. Maybe the worst is ahead!
Incidentally, my comments apply most clearly to computer science PhD programs, which are what I’m most familiar with, but I believe they also apply to physics and other sciences. As for humanities PhD’s … dude, you’re on your own.
Yesterday several people asked my opinion of a preprint claiming to solve the Graph Isomorphism problem in deterministic polynomial time. I responded:
If I read all such papers, then I wouldn’t have time for anything else. It’s an interesting question how you decide whether a given paper crosses the plausibility threshold or not. For me personally, the AKS “PRIMES in P” paper somehow crossed it whereas this one somehow doesn’t.
Of course, I’d welcome an opinion from anyone who’s actually read the paper.
Three commenters wrote in to say the paper looked good. Then the author found a bug and retracted it.
Update (1/5): Laci Babai writes in to tell me that’s not quite what happened. See here for what did happen, and here for an argument that Friedland’s approach would if sound have implied P=NP.
My purpose here is not to heap embarrassment on the author: he’s a serious mathematician who had a well-defined and interesting approach, and who (most importantly) retracted his claim as soon as a bug was discovered. (Would that everyone did the same!) Though the stakes are usually smaller, similar things have happened to most of us, including me.
Instead I want to explore the following metaquestion: suppose someone sends you a complicated solution to a famous decades-old math problem, like P vs. NP. How can you decide, in ten minutes or less, whether the solution is worth reading?
For a blogger like me — whose opinions are both expected immediately and googlable indefinitely — this question actually matters. Err in one direction, and I’ll forever be known as the hidebound reactionary who failed to recognize some 21st-century Ramanujan. Err in the other direction, and I’ll spend my whole life proofreading the work of crackpots.
A few will chime in: “but if everyone wrote out their proofs in computer-checkable form, there’d be no need for this absurd dilemma!” Sure, and if everyone buckled up there’d be fewer serious accidents. Yet here’s the bloodied patient, and here we are in the emergency room.
In deciding whether to spend time on a paper, obviously the identity of the authors plays some role. If Razborov says he proved a superlinear circuit lower bound for SAT, the claim on our attention is different than if Roofus McLoofus says the same thing. But the danger of elitism is obvious here — so in this post, I’ll only be interested in what can be inferred from the text itself.
Inspired by Sean Carroll’s closely-related Alternative-Science Respectability Checklist, without further ado I now offer the Ten Signs a Claimed Mathematical Breakthrough is Wrong.
1. The authors don’t use TeX. This simple test (suggested by Dave Bacon) already catches at least 60% of wrong mathematical breakthroughs. David Deutsch and Lov Grover are among the only known false positives.
2. The authors don’t understand the question. Maybe they mistake NP≠coNP for some claim about psychology or metaphysics. Or maybe they solve the Grover problem in O(1) queries, under some notion of quantum computing lifted from a magazine article. I’ve seen both.
3. The approach seems to yield something much stronger and maybe even false (but the authors never discuss that). They’ve proved 3SAT takes exponential time; their argument would go through just as well for 2SAT.
4. The approach conflicts with a known impossibility result (which the authors never mention). The four months I spent proving the collision lower bound actually saved me some time once or twice, when I was able to reject papers violating the bound without reading them.
5. The authors themselves switch to weasel words by the end. The abstract says “we show the problem is in P,” but the conclusion contains phrases like “seems to work” and “in all cases we have tried.” Personally, I happen to be a big fan of heuristic algorithms, honestly advertised and experimentally analyzed. But when a “proof” has turned into a “plausibility argument” by page 47 — release the hounds!
6. The paper jumps into technicalities without presenting a new idea. If a famous problem could be solved only by manipulating formulas and applying standard reductions, then it’s overwhelmingly likely someone would’ve solved it already. The exceptions to this rule are interesting precisely because they’re rare (and even with the exceptions, a new idea is usually needed to find the right manipulations in the first place).
7. The paper doesn’t build on (or in some cases even refer to) any previous work. Math is cumulative. Even Wiles and Perelman had to stand on the lemma-encrusted shoulders of giants.
8. The paper wastes lots of space on standard material. If you’d really proved P≠NP, then you wouldn’t start your paper by laboriously defining 3SAT, in a manner suggesting your readers might not have heard of it.
9. The paper waxes poetic about “practical consequences,” “deep philosophical implications,” etc. Note that most papers make exactly the opposite mistake: they never get around to explaining why anyone should read them. But when it comes to something like P≠NP, to “motivate” your result is to insult your readers’ intelligence.
10. The techniques just seem too wimpy for the problem at hand. Of all ten tests, this is the slipperiest and hardest to apply — but also the decisive one in many cases. As an analogy, suppose your friend in Boston blindfolded you, drove you around for twenty minutes, then took the blindfold off and claimed you were now in Beijing. Yes, you do see Chinese signs and pagoda roofs, and no, you can’t immediately disprove him — but based on your knowledge of both cars and geography, isn’t it more likely you’re just in Chinatown? I know it’s trite, but this is exactly how I feel when I see (for example) a paper that uses category theory to prove NL≠NP. We start in Boston, we end up in Beijing, and at no point is anything resembling an ocean ever crossed.
Obviously, these are just some heuristics I’ve found successful in the past. (The nice thing about math is that sooner or later the truth comes out, and then you know for sure whether your heuristics succeeded.) If a paper fails one or more tests (particularly tests 6-10), that doesn’t necessarily mean it’s wrong; conversely, if it passes all ten that still doesn’t mean it’s right. At some point, there might be nothing left to do except to roll up your sleeves, brew some coffee, and tell your graduate student to read the paper and report back to you.
When I first saw the headline, I assumed it was from The Onion or (more likely) some local MIT humor publication. But no, it’s from the Associated Press.
My friend Robin Hanson kvetches that scientific contrarians don’t get no respect: even if they ultimately turn out to be right, it’s the more cautious, Johnny-come-lately “conservative radicals” who get the lion’s share of the credit. (Like many of Robin’s posts, this one is written in a purely descriptive mode that nevertheless leaves no doubt where his sympathies lie.) And so, as a firmly-entrenched pillar of the hidebound scientific establishment, I thought I’d tell you our side of the story.
In the US, there are companies whose business it is to patent (or buy patents for) every obvious idea they can think of, then sit around and do nothing with those ideas, wait for some other company to build a successful business around one of them, and sue that company for patent infringement. (The textbook example is NTP’s lawsuit against Research In Motion.)
In science, one occasionally sees the intellectual equivalent of these patent-holding companies: people who publish one flaky idea after another with no data or calculations to back them up; and then if, after years of painstaking research, one of their speculations turns out to be right (or even 10% right), scream “they stole my idea!”
But in my experience — and happily for all concerned — the truth usually lies between this extreme and the opposite extreme described in Robin’s post. To illustrate, let’s consider the example of Robin’s that I know best: that of David Deutsch and quantum computing.
Unlike the patent-holding firms, David Deutsch really was a scientific pioneer, thinking deeply about quantum physics and the Church-Turing Thesis back when basically no one else was. His philosophical insights led him to define the quantum Turing machine model, prove its universality, and realize it might have implications for complexity theory. But his one concrete example of a quantum algorithm — how shall I say? — sucked. In particular, he gave an algorithm to compute the XOR of two bits (and know one has done so) using one quantum query and with success probability 1/2. (Later it was realized that success probability 1 is achievable, but that’s still only a factor-2 speedup compared to classical computers.) If this was all you’d seen of quantum computing, you would rightly file it away with dozens of other promising ideas that hadn’t led anywhere.
Unless, that is, you were Ethan Bernstein and Umesh Vazirani. These “conservative radicals” from Berkeley decided to put quantum computing under the microscope of theoretical computer science. The result of their labor — besides a bounteous harvest of complexity theorems like BPP ⊆ BQP ⊆ P#P — was the first example of a black-box problem for which quantum computers gave a superpolynomial speedup over classical randomized ones. Shortly afterward, another conservative, Dan Simon, set out to prove that the speedup of quantum computing was illusory — and ended up with strong evidence (now called Simon’s algorithm) for exactly the opposite conclusion. A year later, yet another conservative — an expert on combinatorics and discrete geometry by the name of Peter Shor — took a close look at Simon’s algorithm, and realized that if you changed the underlying group from (Z2)n to the cyclic group ZN, then you could efficiently compute the period of a black-box function, and thereby factor integers, and thereby break the RSA cryptosystem, and thereby change the world.
A Hansonian might downplay these later achievements — arguing that, were it not for Shor, some other “mainstream mathematician” (a strange description of him!) would’ve sooner or later discovered the factoring algorithm. But it’s equally true that, were it not for Deutsch, some other “renegade physicist” would have come up with quantum Turing machines (and indeed Feynman and Benioff were close). My own judgment is that Deutsch and Shor both made creative scientific contributions of the highest order, and are both deservedly celebrated for them. Indeed, if anyone gets short-shrifted in the usual popular accounts, I think it’s the people in between — like Bernstein, Vazirani, and Simon.
So yes, let’s remember the first person who struck gold, but also the first to realize it wasn’t fools’ gold and the first to figure out how to mine it. Science is a big place; there’s plenty of room for Deutsches, Shors, and even a Vazirani or two.
"On Computable Numbers, With an Application to the Entscheidungsproblem"
was not accepted to appear in FOCS 1936. The Program Committee received a record 4 submissions this year, many of them of high quality, and scheduling constraints unfortunately made it impossible to accept all of them.
Below please find some reviews on your submission. The reviews are *not* intended as an explanation for why your paper was rejected. This decision depended on many factors, including discussions at the PC meeting and competition from other papers.
The author shows that Hilbert's Entscheidungsproblem (given a mathematical statement, decide whether it admits a formal proof) is unsolvable by any finite means. While this seems like an important result, I have several concerns/criticisms:
1. The author defines a new "Turing machine" model for the specific purpose of proving his result. This model was not defined in any previous papers; thus, the motivation is unclear.
2. I doubt Hilbert's goal of "automating mathematical thought" was ever really taken seriously by anyone (including Hilbert himself). Given this, the negative result comes as no surprise -- a positive result would have been much more interesting.
3. It's hard to find any technical "meat" in this paper. Once the author sets up the problem, the main result follows immediately by a standard diagonalization argument.
4. The whole philosophical discussion in Section 9, about what it means to compute something, is out of place (even slightly embarrassing) and should be deleted entirely.
Summary: While this paper deserves to be published somewhere -- SODA? ICALP? FSTTCS? -- it certainly isn't FOCS caliber.
while i agree with the other reviewers' concerns about triviality, i confess to liking this paper anyway. one reason is that, along the way to the main result, the author proves a lemma stating that there exists a "universal machine" (a machine able to simulate any other machine given a suitable choice of input). the claim that this lemma could have "practical" applications is clearly exaggerated -- but even so, it seems like it could be a useful ingredient for other results.
From Money Magazine, a list of American cities with the highest percentage of residents with graduate degrees. Cambridge, MA (26.3%) narrowly edges out Palo Alto, CA (25.4%) and Berkeley, CA (24.5%) — but beating them both by a long shot is Arlington, VA, the winner at 35.7%. It takes a much more educated crowd to unify Iraq and 9/11 than to unify relativity and quantum mechanics.
[f]or the last four years … has attended graduate physics seminars, used the offices reserved for doctoral and post-doctoral physics students and for all intents and purposes made the Varian Physics Lab her home. The only problem is that Okazaki appears to have no affiliation with Stanford and, according to physics professors and students, no real reason to be there.
The article quotes two people I know: Lenny Susskind (“as far as I can tell, she has a very limited knowledge of physics itself”) and Alessandro Tomasiello (“I feel really bad for her … I don’t want to have a conversation with her that will actually hurt her”). From both the article and the many impassioned comments, it’s clear that opinions in the physics department were mixed. Of course, by now Stanford has predictably reacted by banning Okazaki from campus.
Here’s the thing: while Okazaki is admittedly an extreme case, she reminds me of people I’ve known throughout my academic career. These are the groupies of science: those non-scientists who, for one reason or another, choose to build their whole social lives around science and scientists. When asked about their “research,” such people usually mention some vague interdisciplinary project that never seems to come to fruition.
After long deliberation, I’ve reached the following conclusion: generally speaking, SCIENCE NEEDS MORE GROUPIES, NOT LESS.
And no, not just for the obvious reason. At their best, groupies perform a vital role in the socially-impoverished scientific ecosystem, by serving as the conveyors of gossip, the organizers of parties, the dispensers of advice, and the matchmakers of lonely nerds with eligible humanists.
Furthermore, science needs a freewheeling culture to function, a point that seems lost on many of the Stanford Daily commenters. There we find enraged alumni wondering how anyone could possibly get away with this, and declaring that they certainly won’t be sending their kids to any school that tolerates such inanity. We find bigots comparing Okazaki to the Virginia Tech shooter Cho Seung-Hui (the common thread being, apparently, that both of them are Asian). And we find people asking rhetorically whether any corporation or government agency would tolerate a freeloader hanging around its offices for years. (My answer: probably not, and that’s one reason why I’m happy not to work at such places!)
On the other hand, we also find commenters denouncing the spoiled bourgeoisie capitalists at Stanford, who would deny a poor homeless woman the right to sleep in their physics building. Unless the critics are Mother Teresas themselves, that doesn’t seem fair to me either.
I have no desire to pass judgment on someone I’ve never met; any decision on Okazaki ought to rest with the people who actually work in Varian and know the specifics of her case. But I’d like to offer a general suggestion to any department that finds itself in a similar situation in the future: unless the groupie is insane or incompetent, find her some low-paying job as a lab assistant or “social programming director” or something like that. When we discover a stowaway on the great Ship of Science, why throw her overboard when we could make her swab the decks?
Update (6/6): Peter Woit now has his own post on this affair, with several entertaining comments. I’m skeptical of the idea that Okazaki had no real interest in science or scientists and only wanted free digs. Even in the insane housing market of Palo Alto, surely there must be ways to get a roof over your head that don’t require sitting in on theoretical physics seminars?
I also found the following comment priceless:
I think Scott Aaronson’s opinion is quite shallow … Scott wants groupies, and he wants to hire them to “swab the decks”. Only someone who thinks he is so special he should have serfs to serve him would think that way. College Professors already have a bunch of poorly paid workers(graduate students) who write papers for them. Do these aristocrats need an additional class of poorly paid servants
It always amuses me when those looking for an “elite” to rail against pick people who strive for a decade against staggering odds to have ideas that no one in the history of the world ever had before, in order that they might possibly qualify for a stressful, ~90-hour-a-week job offering the same money, power, and prestige that would accrue automatically to a mid-level insurance salesman.
Follow
