How to upper-bound the probability of something bad

April 13th, 2018

Scott Alexander has a new post decrying how rarely experts encode their knowledge in the form of detailed guidelines with conditional statements and loops—or what one could also call flowcharts or expert systems—rather than just blanket recommendations.  He gives, as an illustration of what he’s looking for, an algorithm that a psychiatrist might use to figure out which antidepressants or other treatments will work for a specific patient—with the huge proviso that you shouldn’t try his algorithm at home, or (most importantly) sue him if it doesn’t work.

Compared to a psychiatrist, I have the huge advantage that if my professional advice fails, normally no one gets hurt or gets sued for malpractice or commits suicide or anything like that.  OK, but what do I actually know that can be encoded in if-thens?

Well, one of the commonest tasks in the day-to-day life of any theoretical computer scientist, or mathematician of the Erdös flavor, is to upper bound the probability that something bad will happen: for example, that your randomized algorithm or protocol will fail, or that your randomly constructed graph or code or whatever it is won’t have the properties needed for your proof.

So without further ado, here are my secrets revealed, my ten-step plan to probability-bounding and computer-science-theorizing success.

Step 1. “1” is definitely an upper bound on the probability of your bad event happening.  Check whether that upper bound is good enough.  (Sometimes, as when this is an inner step in a larger summation over probabilities, the answer will actually be yes.)

Step 2. Try using Markov’s inequality (a nonnegative random variable exceeds its mean by a factor of k at most a 1/k fraction of the time), combined with its close cousin in indispensable obviousness, the union bound (the probability that any of several bad events will happen, is at most the sum of the probabilities of each bad event individually).  About half the time, you can stop right here.

Step 3. See if the bad event you’re worried about involves a sum of independent random variables exceeding some threshold. If it does, hit that sucker with a Chernoff or Hoeffding bound.

Step 4. If your random variables aren’t independent, see if they at least form a martingale: a fancy word for a sum of terms, each of which has a mean of 0 conditioned on all the earlier terms, even though it might depend on the earlier terms in subtler ways.  If so, Azuma your problem into submission.

Step 5. If you don’t have a martingale, but you still feel like your random variables are only weakly correlated, try calculating the variance of whatever combination of variables you care about, and then using Chebyshev’s inequality: the probability that a random variable differs from its mean by at most k times the standard deviation (i.e., the square root of the variance) is at most 1/k2.  If the variance doesn’t work, you can try calculating some higher moments too—just beware that, around the 6th or 8th moment, you and your notebook paper will likely both be exhausted.

Step 6. OK, umm … see if you can upper-bound the variation distance between your probability distribution and a different distribution for which it’s already known (or is easy to see) that it’s unlikely that anything bad happens. A good example of a tool you can use to upper-bound variation distance is Pinsker’s inequality.

Step 7. Now is the time when you start ransacking Google and Wikipedia for things like the Lovász Local Lemma, and concentration bounds for low-degree polynomials, and Hölder’s inequality, and Talagrand’s inequality, and other isoperimetric-type inequalities, and hypercontractive inequalities, and other stuff that you’ve heard your friends rave about, and have even seen successfully used at least twice, but there’s no way you’d remember off the top of your head under what conditions any of this stuff applies, or whether any of it is good enough for your application. (Just between you and me: you may have already visited Wikipedia to refresh your memory about the earlier items in this list, like the Chernoff bound.) “Try a hypercontractive inequality” is surely the analogue of the psychiatrist’s “try electroconvulsive therapy,” for a patient on whom all milder treatments have failed.

Step 8. So, these bad events … how bad are they, anyway? Any chance you can live with them?  (See also: Step 1.)

Step 9. You can’t live with them? Then back up in your proof search tree, and look for a whole different approach or algorithm, which would make the bad events less likely or even kill them off altogether.

Step 10. Consider the possibility that the statement you’re trying to prove is false—or if true, is far beyond any existing tools.  (This might be the analogue of the psychiatrist’s: consider the possibility that evil conspirators really are out to get your patient.)

Amazing progress on longstanding open problems

April 11th, 2018

For those who haven’t seen it:

  1. Aubrey de Grey, better known to the world as a radical life extension researcher, on Sunday posted a preprint on the arXiv claiming to prove that the chromatic number of the plane is at least 5—the first significant progress on the Hadwiger-Nelson problem since 1950.  If you’re tuning in from home, the Hadwiger-Nelson problem asks: what’s the minimum number of colors that you need to color the Euclidean plane, in order to ensure that every two points at distance exactly 1 from each other are colored differently?  It’s not hard to show that at least 4 colors are necessary, or that 7 colors suffice: try convincing yourself by staring at the figure below.  Until a few days ago, nothing better was known.
    This is a problem that’s intrigued me ever since I learned about it at a math camp in 1996, and that I spent at least a day of my teenagerhood trying to solve.
    De Grey constructs an explicit graph with unit distances—originally with 1567 vertices, now with 1585 vertices after after a bug was fixed—and then verifies by computer search (which takes a few hours) that 5 colors are needed for it.  Update: My good friend Marijn Heule, at UT Austin, has now apparently found a smaller such graph, with “only” 874 vertices.  See here.
    So, can we be confident that the proof will stand—i.e., that there are no further bugs?  See the comments of Gil Kalai’s post for discussion.  Briefly, though, it’s now been independently verified, using different SAT-solvers, that the chromatic number of de Grey’s corrected graph is indeed 5.  Paul Phillips emailed to tell me that he’s now independently verified that the graph is unit distance as well.  So I think it’s time to declare the result correct.
    Question for experts: is there a general principle by which we can show that, if the chromatic number of the plane is at least 6, or is 7, then there exists a finite subgraph that witnesses it?  (This is closely related to asking, what’s the logical complexity of the Hadwiger-Nelson problem: is it Π1?)  Update: As de Grey and a commenter pointed out to me, this is the de Bruijn-Erdös Theorem from 1951.  But the proofs inherently require the Axiom of Choice.  Assuming AC, this also gives you that Hadwiger-Nslson is a Π1 statement, since the coordinates of the points in any finite counterexample can be assumed to be algebraic. However, this also raises the strange possibility that the chromatic number of the plane could be smaller assuming AC than not assuming it.
  2. Last week, Urmila Mahadev, a student (as was I, oh so many years ago) of Umesh Vazirani at Berkeley, posted a preprint on the arXiv giving a protocol for a quantum computer to prove the results of any computation it performs to a classical skeptic—assuming a relatively standard cryptographic assumption, namely the quantum hardness of the Learning With Errors (LWE) problem, and requiring only classical communication between the skeptic and the QC.  I don’t know how many readers remember, but way back in 2006, inspired by a $25,000 prize offered by Stephen Wolfram, I decided to offer a $25 prize to anyone who could solve the problem of proving the results of an arbitrary quantum computation to a classical skeptic, or who could give oracle evidence that a solution was impossible.  I had first learned this fundamental problem from Daniel Gottesman.
    Just a year or two later, independent work of Aharonov, Ben-Or, and Eban, and of Broadbent, Fitzsimons, and Kashefi made a major advance on the problem, by giving protocols that were information-theoretically secure.  The downside was that, in contrast to Mahadev’s new protocol, these earlier protocols required the verifier to be a little bit quantum: in particular, to exchange individual unentangled qubits with the QC.  Or, as shown by later work, the verifier could be completely classical, but only if it could send challenges to two or more quantum computers that were entangled but unable to communicate with each other.  In light of these achievements, I decided to award both groups their own checks for half the prize amount ($12.50), to be split among themselves however they chose.
    Neither with Broadbent et al.’s or Aharonov et al.’s earlier work, nor with Mahadev’s new work, is it immediately clear whether the protocols relativize (that is, whether they work relative to an arbitrary oracle), but it’s plausible that they don’t.
    Anyway, assuming that her breakthrough result stands, I look forward to awarding Urmila the full $25 prize when I see her at the Simons Institute in Berkeley this June.

Huge congratulations to Aubrey and Urmila for their achievements!


Update (April 12): My friend Virgi Vassilevska Williams asked me to announce a theoretical computer science women event, which will take during the upcoming STOC in LA.


Another Update: Another friend, Holden Karnofsky of the Open Philanthropy Project, asked me to advertise that OpenPhil is looking to hire a Research Analyst and Senior Research Analyst. See also this Medium piece (“Hiring Analytical Thinkers to Help Give Away Billions”) to learn more about what the job would involve.

Two announcements

April 7th, 2018

Before my next main course comes out of the oven, I bring you two palate-cleansing appetizers:

  1. My childhood best friend Alex Halderman, whose heroic exploits helping to secure the world’s voting systems have often been featured on this blog, now has a beautifully produced video for the New York Times, entitled “I Hacked An Election.  So Can The Russians.”  Here Alex lays out the case for an audited paper trail—i.e., for what the world’s cybersecurity experts have been unanimously flailing their arms about for two decades—in terms so simple and vivid that even Congresspeople should be able to understand them.  Please consider sharing the video if you support this important cause.
  2. Jakob Nordstrom asked me to advertise the 5th Swedish Summer School in Computer Science, to be held August 5-11, 2018, in the beautiful Stockholm archipelago at Djuronaset.  This year the focus is on quantum computing, and the lecturers are two of my favorite people in the entire field: Ronald de Wolf (giving a broad intro to QC) and Oded Regev (lecturing on post-quantum cryptography).  The school is mainly for PhD students, but is also open to masters students, postdocs, and faculty.  If you wanted to spend one week getting up to speed on quantum, it’s hard for me to imagine that you’d find any opportunity more excellent.  The application deadline is April 20, so apply now if you’re interested!

30 of my favorite books

March 28th, 2018

A reader named Shozab writes:

Scott, if you had to make a list of your favourite books, which ones would you include?
And yes, you can put in quantum computing since Democritus!

Since I’ve gotten the same request before, I guess this is as good a time as any.  My ground rules:

  • I’ll only include works because I actually read them and they had a big impact on me at some point in my life—not because I feel abstractly like they’re important or others should read them, or because I want to be seen as the kind of person who recommends them.
  • But not works that impacted me before the age of about 10, since my memory of childhood reading habits is too hazy.
  • To keep things manageable, I’ll include at most one work per author.  My choices will often be idiosyncratic—i.e., not that author’s “best” work.  However, it’s usually fair to assume that if I include something by X, then I’ve also read and enjoyed other works by X, and that I might be including this work partly just as an entry point into X’s oeuvre.
  • In any case where the same author has both “deeper” and more “accessible” works, both of which I loved, I’ll choose the more accessible.  But rest assured that I also read the deeper work. 🙂
  • This shouldn’t need to be said, but since I know it does: listing a work by author X does not imply my agreement with everything X has ever said about every topic.
  • The Bible, the Homeric epics, Plato, and Shakespeare are excluded by fiat.  They’re all pretty important (or so one hears…), and you should probably read them all, but I don’t want the responsibility of picking and choosing from among them.
  • No books about the Holocaust, or other unremittingly depressing works like 1984.  Those are a special category to themselves: I’m glad that I read them, but would never read them twice.
  • The works are in order of publication date, with a single exception (see if you can spot it!).

Without further ado:

Quantum Computing Since Democritus by Scott Aaronson

Dialogue Concerning the Two Chief World Systems by Galileo Galilei

Dialogues Concerning Natural Religion by David Hume

Narrative of the Life of Frederick Douglass by himself

The Adventures of Huckleberry Finn by Mark Twain

The Subjection of Women by John Stuart Mill

The Autobiography of Charles Darwin by himself

Altneuland by Theodor Herzl

The Practice and Theory of Bolshevism by Bertrand Russell

What Is Life?: With Mind and Matter and Autobiographical Sketches by Erwin Schrödinger

Fads and Fallacies in the Name of Science by Martin Gardner

How Children Fail by John Holt

Set Theory and the Continuum Hypothesis by Paul Cohen

The Gods Themselves by Isaac Asimov (specifically, the middle third)

A History of Pi by Petr Beckmann

The Selfish Gene by Richard Dawkins

The Mind-Body Problem by Rebecca Goldstein

Alan Turing: The Enigma by Andrew Hodges

Surely You’re Joking Mr. Feynman by Richard Feynman

The Book of Numbers by John Conway and Richard Guy

The Demon-Haunted World by Carl Sagan

Gems of Theoretical Computer Science by Uwe Schöning and Randall Pruim

Fashionable Nonsense by Alan Sokal and Jean Bricmont

Our Dumb Century by The Onion

Quantum Computation and Quantum Information by Michael Nielsen and Isaac Chuang

The Blank Slate by Steven Pinker

Field Notes from a Catastrophe by Elizabeth Kolbert

Infidel by Ayaan Hirsi Ali

Logicomix by Apostolos Doxiadis and Christos Papadimitriou

The Beginning of Infinity by David Deutsch

You’re welcome to argue with me in the comments, e.g., by presenting evidence that I didn’t actually like these books. 🙂  More seriously: list your own favorites, discuss your reactions to these books, be a “human recommendation engine” by listing books that “those who liked the above would also enjoy,” whatever.

Addendum: Here’s another bonus twenty books, as I remember more and as commenters remind me of more that I liked quite as much as the thirty above.

The Man Who Knew Infinity by Robert Kanigel

A Mathematician’s Apology by G. H. Hardy

A Confederacy of Dunces by John Kennedy Toole

The First Three Minutes by Steven Weinberg

Breaking the Code by Hugh Whitemore

Arcadia by Tom Stoppard

Adventures of a Mathematician by Stanislaw Ulam

The Man Who Loved Only Numbers by Paul Hoffman

Mathematical Writing by Donald Knuth, Tracy Larabee, and Paul Roberts

A Beautiful Mind by Sylvia Nasar

An Introduction to Computational Learning Theory by Michael Kearns and Umesh Vazirani

The Road to Reality by Roger Penrose

The Nili Spies by Anita Engle (about the real-life heroic exploits of the Aaronsohn family)

Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig

The Princeton Companion to Mathematics edited by Timothy Gowers

The Making of the Atomic Bomb by Richard Rhodes

Fear No Evil by Natan Sharansky

The Mind’s I by Douglas Hofstadter and Daniel Dennett

Disturbing the Universe by Freeman Dyson

Unsong by Scott Alexander

Review of Steven Pinker’s Enlightenment Now

March 22nd, 2018

It’s not every day that I check my office mailbox and, amid the junk brochures, find 500 pages on the biggest questions facing civilization—all of them, basically—by possibly the single person on earth most qualified to tackle those questions.  That’s what happened when, on a trip back to Austin from my sabbatical, I found a review copy of Steven Pinker’s Enlightenment Now: The Case for Reason, Science, Humanism, and Progress.

I met with Steve while he was writing this book, and fielded his probing questions about the relationships among the concepts of information, entropy, randomness, Kolmogorov complexity, and coarse graining, in a way that might have affected a few paragraphs in Chapter 2.  I’m proud to be thanked in the preface—well, as “Scott Aronson.”  I have a lot of praise for the book, but let’s start with this: the omission of the second “a” from my surname was the worst factual error that I found.

If you’ve read anything else by Pinker, then you more-or-less know what to expect: an intellectual buffet that’s pure joy to devour, even if many of the dishes are ones you’ve tasted before.  For me, the writing alone is worth the admission price: Pinker is, among many other distinctions, the English language’s master of the comma-separated list.  I can see why Bill Gates recently called Enlightenment Now his “new favorite book of all time“—displacing his previous favorite, Pinker’s earlier book The Better Angels of Our Nature.  If you’ve read Better Angels, to which Enlightenment Now functions as a sort of sequel, then you know even more specifically what to expect: a saturation bombing of line graphs showing you how, despite the headlines, the world has been getting better in almost every imaginable way—graphs so thorough that they’ll eventually drag the most dedicated pessimist, kicking and screaming, into sharing Pinker’s sunny disposition, at least temporarily (but more about that later).

The other book to which Enlightenment Now bears comparison is David Deutsch’s The Beginning of Infinity.  The book opens with one of Deutsch’s maxims—“Everything that is not forbidden by laws of nature is achievable, given the right knowledge”—and Deutsch’s influence can be seen throughout Pinker’s new work, as when Pinker repeats the Deutschian mantra that “problems are solvable.”  Certainly Deutsch and Pinker have a huge amount in common: classical liberalism, admiration for the Enlightenment as perhaps the best thing that ever happened to the human species, and barely-perturbable optimism.

Pinker’s stated aim is to make an updated case for the Enlightenment—and specifically, for the historically unprecedented “ratchet of progress” that humankind has been on for the last few hundred years—using the language and concepts of the 21st century.  Some of his chapter titles give a sense of the scope of the undertaking:

  • Life
  • Health
  • Wealth
  • Inequality
  • The Environment
  • Peace
  • Safety
  • Terrorism
  • Equal Rights
  • Knowledge
  • Happiness
  • Reason
  • Science

When I read these chapter titles aloud to my wife, she laughed, as if to say: how could anyone have the audacity to write a book on just one of these enormities, let alone all of them?  But you can almost hear the gears turning in Pinker’s head as he decided to do it: well, someone ought to take stock in a single volume of where the human race is and where it’s going.  And if, with the rise of thuggish autocrats all over the world, the principles of modernity laid down by Locke, Spinoza, Kant, Jefferson, Hamilton, and Mill are under attack, then someone ought to rise to those principles’ unironic defense.  And if no one else will do it, it might as well be me!  If that’s how Pinker thought, then I agree: it might as well have been him.

I also think Pinker is correct that Enlightenment values are not so anodyne that they don’t need a defense.  Indeed, nothing demonstrates the case for Pinker’s book, the non-obviousness of his thesis, more clearly than the vitriolic reviews the book has been getting in literary venues.  Take this, for example, from John Gray in The New Statesman: “Steven Pinker’s embarrassing new book is a feeble sermon for rattled liberals.”

Pinker is an ardent enthusiast for free-market capitalism, which he believes produced most of the advance in living standards over the past few centuries. Unlike [Herbert Spencer, the founder of Social Darwinism], he seems ready to accept that some provision should be made for those who have been left behind. Why he makes this concession is unclear. Nothing is said about human kindness, or fairness, in his formula. Indeed, the logic of his dictum points the other way.

Many early-20th-century Enlightenment thinkers supported eugenic policies because they believed “improving the quality of the population” – weeding out human beings they deemed unproductive or undesirable – would accelerate the course of human evolution…

Exponents of scientism in the past have used it to promote Fabian socialism, Marxism-Leninism, Nazism and more interventionist varieties of liberalism. In doing so, they were invoking the authority of science to legitimise the values of their time and place. Deploying his cod-scientific formula to bolster market liberalism, Pinker does the same.

You see, when Pinker says he supports Enlightenment norms of reason and humanism, he really means to say that he supports unbridled capitalism and possibly even eugenics.  As I read this sort of critique, the hair stands on my neck, because the basic technique of hostile mistranslation is so familiar to me.  It’s the technique that once took a comment in which I pled for shy nerdy males and feminist women to try to understand each other’s suffering, as both navigate a mating market unlike anything in previous human experience—and somehow managed to come away with the take-home message, “so this entitled techbro wants to return to a past when society would just grant him a female sex slave.”

I’ve noticed that everything Pinker writes bears the scars of the hostile mistranslation tactic.  Scarcely does he say anything before he turns around and says, “and here’s what I’m not saying”—and then proceeds to ward off five different misreadings so wild they wouldn’t have occurred to me, but then if you read Leon Wieseltier or John Gray or his other critics, there the misreadings are, trotted out triumphantly; it doesn’t even matter how much time Pinker spent trying to prevent them.


OK, but what of the truth or falsehood of Pinker’s central claims?

I share Pinker’s sense that the Enlightenment may be the best thing that ever happened in our species’ sorry history.  I agree with his facts, and with his interpretations of the facts.  We rarely pause to consider just how astounding it is—how astounding it would be to anyone who lived before modernity—that child mortality, hunger, and disease have plunged as far as they have, and we show colossal ingratitude toward the scientists and inventors and reformers who made it possible.  (Pinker lists the following medical researchers and public health crusaders as having saved more than 100 million lives each: Karl Landsteiner, Abel Wolman, Linn Enslow, William Foege, Maurice Hilleman, John Enders.  How many of them had you heard of?  I’d heard of none.)  This is, just as Pinker says, “the greatest story seldom told.”

Beyond the facts, I almost always share Pinker’s moral intuitions and policy preferences.  He’s right that, whether we’re discussing nuclear power, terrorism, or GMOs, going on gut feelings like disgust and anger, or on vivid and memorable incidents, is a terrible way to run a civilization.  Instead we constantly need to count: how many would be helped by this course of action, how many would be harmed?  As Pinker points out, that doesn’t mean we need to become thoroughgoing utilitarians, and start fretting about whether the microscopic proto-suffering of a bacterium, multiplied by the 1031 bacteria that there are, outweighs every human concern.  It just means that we should heed the utilitarian impulse to quantify way more than is normally done—at the least, in every case where we’ve already implicitly accepted the underlying values, but might be off by orders of magnitude in guessing what they imply about our choices.

The one aspect of Pinker’s worldview that I don’t share—and it’s a central one—is his optimism.  My philosophical temperament, you might say, is closer to that of Rebecca Newberger Goldstein, the brilliant novelist and philosopher (and Pinker’s wife), who titled a lecture given shortly after Trump’s election “Plato’s Despair.”

Somehow, I look at the world from more-or-less the same vantage point as Pinker, yet am terrified rather than hopeful.  I’m depressed that Enlightenment values have made it so far, and yet there’s an excellent chance (it seems to me) that it will be for naught, as civilization slides back into authoritarianism, and climate change and deforestation and ocean acidification make the one known planet fit for human habitation increasingly unlivable.

I’m even depressed that Pinker’s book has gotten such hostile reviews.  I’m depressed, more broadly, that for centuries, the Enlightenment has been met by its beneficiaries with such colossal incomprehension and ingratitude.  Save 300 million people from smallpox, and you can expect in return a lecture about your naïve and arrogant scientistic reductionism.  Or, electronically connect billions of people to each other and to the world’s knowledge, in a way beyond the imaginings of science fiction half a century ago, and people will use the new medium to rail against the gross, basement-dwelling nerdbros who made it possible, then upvote and Like each other for their moral courage in doing so.

I’m depressed by the questions: how can a human race that reacts in that way to the gifts of modernity possibly be trusted to use those gifts responsibly?  Does it even “deserve” the gifts?

As I read Pinker, I sometimes imagined a book published in 1923 about the astonishing improvements in the condition of Europe’s Jews following their emancipation.  Such a book might argue: look, obviously past results don’t guarantee future returns; all this progress could be wiped out by some freak future event.  But for that to happen, an insane number of things would need to go wrong simultaneously: not just one European country but pretty much all of them would need to be taken over by antisemitic lunatics who were somehow also hyper-competent, and who wouldn’t just harass a few Jews here and there until the lunatics lost power, but would systematically hunt down and exterminate all of them with an efficiency the world had never before seen.  Also, for some reason the Jews would need to be unable to escape to Palestine or the US or anywhere else.  So the sane, sober prediction is that things will just continue to improve, of course with occasional hiccups (but problems are solvable).

Or I thought back to just a few years ago, to the wise people who explained that, sure, for the United States to fall under the control of a racist megalomaniac like Trump would be a catastrophe beyond imagining.  Were such a comic-book absurdity realized, there’d be no point even discussing “how to get democracy back on track”; it would already have suffered its extinction-level event.  But the good news is that it will never happen, because the voters won’t allow it: a white nationalist authoritarian could never even get nominated, and if he did, he’d lose in a landslide.  What did Pat Buchanan get, less than 1% of the vote?

I don’t believe in a traditional God, but if I did, the God who I’d believe in is one who’s constantly tipping the scales of fate toward horribleness—a God who regularly causes catastrophes to happen, even when all the rational signs point toward their not happening—basically, the God who I blogged about here.  The one positive thing to be said about my God is that, unlike the just and merciful kind, I find that mine rarely lets me down.

Pinker is not blind.  Again and again, he acknowledges the depths of human evil and idiocy, the forces that even now look to many of us like they’re leaping up at Pinker’s exponential improvement curves with bared fangs.  It’s just that each time, he recommends putting an optimistic spin on the situation, because what’s the alternative?  Just to get all, like, depressed?  That would be unproductive!  As Deutsch says, problems will always arise, but problems are solvable, so let’s focus on what it would take to solve them, and on the hopeful signs that they’re already being solved.

With climate change, Pinker gives an eloquent account of the enormity of the crisis, echoing the mainstream scientific consensus in almost every particular.  But he cautions that, if we tell people this is plausibly the end of civilization, they’ll just get fatalistic and paralyzed, so it’s better to talk about solutions.  He recommends an aggressive program of carbon pricing, carbon capture and storage, nuclear power, research into new technologies, and possibly geoengineering, guided by strong international cooperation—all things I’d recommend as well.  OK, but what are the indications that anything even close to what’s needed will get done?  The right time to get started, it seems to me, was over 40 years ago.  Since then, the political forces that now control the world’s largest economy have spiralled into ever more vitriolic denial, the more urgent the crisis has gotten and the more irrefutable the evidence.  Pinker writes:

“We cannot be complacently optimistic about climate change, but we can be conditionally optimistic.  We have some practicable ways to prevent the harms and we have the means to learn more.  Problems are solvable.  That does not mean that they will solve themselves, but it does mean that we can solve them if we sustain the benevolent forces of modernity that have allowed us to solve problems so far…” (p. 154-155)

I have no doubt that conditional optimism is a useful stance to adopt, in this case as in many others.  The trouble, for me, is the gap between the usefulness of a view and its probable truth—a gap that Pinker would be quick to remind me about in other contexts.  Even if a placebo works for those who believe in it, how do you make yourself believe in what you understand to be a placebo?  Even if all it would take, for the inmates to escape a prison, is simultaneous optimism that they’ll succeed if they work together—still, how can an individual inmate be optimistic, if he sees that the others aren’t, and rationally concludes that dying in prison is his probable fate?  For me, the very thought of the earth gone desolate—its remaining land barely habitable, its oceans a sewer, its radio beacons to other worlds fallen silent—all for want of ability to coordinate a game-theoretic equilibrium, just depresses me even more.

Likewise with thermonuclear war: Pinker knows, of course, that even if there were “only” an 0.5% chance of one per year, multiplied across the decades of the nuclear era that’s enormously, catastrophically too high, and there have already been too many close calls.  But look on the bright side: the US and Russia have already reduced their arsenals dramatically from their Cold War highs.  There’d be every reason for optimism about continued progress, if we weren’t in this freak branch of the wavefunction where the US and Russia (not to mention North Korea and other nuclear states) were now controlled by authoritarian strongmen.

With Trump—for how could anyone avoid him in a book like this?—Pinker spends several pages reviewing the damage he’s inflicted on democratic norms, the international order, the environment, and the ideal of truth itself:

“Trump’s barefaced assertion of canards that can instantly be debunked … shows that he sees public discourse not as a means of finding common ground based on objective reality but as a weapon with which to project dominance and humiliate rivals” (p. 336).

Pinker then writes a sentence that made me smile ruefully: “Not even a congenital optimist can see a pony in this Christmas stocking” (p. 337).  Again, though, Pinker looks at poll data suggesting that Trump and the world’s other resurgent quasi-fascists are not the wave of the future, but the desperate rearguard actions of a dwindling and aging minority that feels itself increasingly marginalized by the modern world (and accurately so).  The trouble is, Nazism could also be seen as “just” a desperate, failed attempt to turn back the ratchet of cosmopolitanism and moral progress, by people who viscerally understood that time and history were against them.  Yet even though Nazism ultimately lost (which was far from inevitable, I think), the damage it inflicted on its way out was enough, you might say, to vindicate the shrillest pessimist of the 1930s.

Then there’s the matter of takeover by superintelligent AI.  I’ve now spent years hanging around communities where it’s widely accepted that “AI value alignment” is the most pressing problem facing humanity.  I strongly disagree with this view—but on reflection, not because I don’t think AI could be a threat; only because I think other, more prosaic things are much more imminent threats!  I feel the urge to invent a new, 21st-century Yiddish-style proverb: “oy, that we should only survive so long to see the AI-bots become our worst problem!”

Pinker’s view is different: he’s dismissive of the fear (even putting it in the context of the Y2K bug, and people marching around sidewalks with sandwich boards that say “REPENT”), and thinks the AI-risk folks are simply making elementary mistakes about the nature of intelligence.  Pinker’s arguments are as follows: first, intelligence is not some magic, all-purpose pixie dust, which humans have more of than animals, and which a hypothetical future AI would have more of than humans.  Instead, the brain is a bundle of special-purpose modules that evolved for particular reasons, so “the concept [of artificial general intelligence] is barely coherent” (p. 298).  Second, it’s only humans’ specific history that causes them to think immediately about conquering and taking over, as goals to which superintelligence would be applied.  An AI could have different motivations entirely—and it will, if its programmers have any sense.  Third, any AI would be constrained by the resource limits of the physical world.  For example, just because an AI hatched a brilliant plan to recursively improve itself, doesn’t mean it could execute that plan without (say) building a new microchip fab, acquiring the necessary raw materials, and procuring the cooperation of humans.  Fourth, it’s absurd to imagine a superintelligence converting the universe into paperclips because of some simple programming flaw or overliteral interpretation of human commands, since understanding nuances is what intelligence is all about:

“The ability to choose an action that best satisfies conflicting goals is not an add-on to intelligence that engineers might slap themselves in the forehead for forgetting to install; it is intelligence.  So is the ability to interpret the intentions of a language user in context” (p. 300).

I’ll leave it to those who’ve spent more time thinking about these issues to examine these arguments in detail (in the comments of this post, if they like).  But let me indicate briefly why I don’t think they fare too well under scrutiny.

For one thing, notice that the fourth argument is in fundamental tension with the first and second.  If intelligence is not an all-purpose elixir but a bundle of special-purpose tools, and if those tools can be wholly uncoupled from motivation, then why couldn’t we easily get vast intelligence expended toward goals that looked insane from our perspective?  Have humans never been known to put great intelligence in the service of ends that strike many of us as base, evil, simpleminded, or bizarre?  Consider the phrase often applied to men: “thinking with their dicks.”  Is there any sub-Einsteinian upper bound on the intelligence of the men who’ve been guilty of that?

Second, while it seems clear that there are many special-purpose mental modules—the hunting instincts of a cat, the mating calls of a bird, the pincer-grasping or language-acquisition skills of a human—it seems equally clear that there is some such thing as “general problem-solving ability,” which Newton had more of than Roofus McDoofus, and which even Roofus has more of than a chicken.  But whatever we take that ability to consist of, and whether we measure it by a scalar or a vector, it’s hard to imagine that Newton was anywhere near whatever limits on it are imposed by physics.  His brain was subject to all sorts of archaic evolutionary constraints, from the width of the birth canal to the amount of food available in the ancestral environment, and possibly also to diminishing returns on intelligence in humans’ social environment (Newton did, after all, die a virgin).  But if so, then given the impact that Newton, and others near the ceiling of known human problem-solving ability, managed to achieve even with their biology-constrained brains, how could we possibly see the prospect of removing those constraints as just a narrow technological matter, like building a faster calculator or a more precise clock?

Third, the argument about intelligence being constrained by physical limits would seem to work equally well for a mammoth or cheetah scoping out the early hominids.  The mammoth might say: yes, these funny new hairless apes are smarter than me, but intelligence is just one factor among many, and often not the decisive one.  I’m much bigger and stronger, and the cheetah is faster.  (If the mammoth did say that, it would be an unusually smart mammoth as well, but never mind.)  Of course we know what happened: from wild animals’ perspective, the arrival of humans really was a catastrophic singularity, comparable to the Chicxulub asteroid (and far from over), albeit one that took between 104 and 106 years depending on when we start the clock.  Over the short term, the optimistic mammoths would be right: pure, disembodied intelligence can’t just magically transform itself into spears and poisoned arrows that render you extinct.  Over the long term, the most paranoid mammoth on the tundra couldn’t imagine the half of what the new “superintelligence” would do.

Finally, any argument that relies on human programmers choosing not to build an AI with destructive potential, has to contend with the fact that humans did invent, among other things, nuclear weapons—and moreover, for what seemed like morally impeccable reasons at the time.  And a dangerous AI would be a lot harder to keep from proliferating, since it would consist of copyable code.  And it would only take one.  You could, of course, imagine building a good AI to neutralize the bad AIs, but by that point there’s not much daylight left between you and the AI-risk people.


As you’ve probably gathered, I’m a worrywart by temperament (and, I like to think, experience), and I’ve now spent a good deal of space on my disagreements with Pinker that flow from that.  But the funny part is, even though I consistently see clouds where he sees sunshine, we’re otherwise looking at much the same scene, and our shared view also makes us want the same things for the world.  I find myself in overwhelming, nontrivial agreement with Pinker about the value of science, reason, humanism, and Enlightenment; about who and what deserves credit for the stunning progress humans have made; about which tendencies of civilization to nurture and which to recoil in horror from; about how to think and write about any of those questions; and about a huge number of more specific issues.

So my advice is this: buy Pinker’s book and read it.  Then work for a future where the book’s optimism is justified.

Hawking

March 16th, 2018

A long post is brewing (breaking my month-long silence), but as I was working on it, the sad news arrived that Stephen Hawking passed away. There’s little I can add to the tributes that poured in from around the world: like chocolate or pizza, Hawking was beloved everywhere and actually deserved to be. Like, probably, millions of other nerds of my generation, I read A Brief History of Time as a kid and was inspired by it (though I remember being confused back then about the operational meaning of imaginary time, and am still confused about it almost 30 years later).  In terms of a scientist capturing the public imagination, through a combination of genuine conceptual breakthroughs, an enthralling personal story, an instantly recognizable countenance, and oracular pronouncements on issues of the day, the only one in the same league was Einstein. I didn’t agree with all of Hawking’s pronouncements, but the quibbles paled beside the enormous areas of agreement.  Hawking was a force for good in the world, and for the values of science, reason, and Enlightenment (to anticipate the subject of my next post).

I’m sorry that I never really met Hawking, though I did participate in two conferences that he also attended, and got to watch him slowly form sentences on his computer. At one conference in 2011, he attended my talk—this one—and I was told by mutual acquaintances that he liked it.  That meant more to me than it probably should have: who cares if some random commenters on YouTube dissed your talk, if the Hawk-Man himself approved?

As for Hawking’s talks—well, there’s a reason why they filled giant auditoriums all over the world.  Any of us in the business of science popularization would do well to study them and take lessons.

If you want a real obituary of Hawking, by someone who knew him well—one that, moreover, actually explains his main scientific contributions (including the singularity theorems, Hawking radiation, and the no-boundary proposal)—you won’t do any better than this by Roger Penrose. Also don’t miss this remembrance in Time by Hawking’s friend and betting partner, and friend-of-the-blog, John Preskill. (Added: and this by Sean Carroll.)

Review of Vivek Wadhwa’s Washington Post column on quantum computing

February 13th, 2018

Various people pointed me to a Washington Post piece by Vivek Wadhwa, entitled “Quantum computers may be more of an immiment threat than AI.”  I know I’m late to the party, but in the spirit of Pete Wells’ famous New York Times “review” of Guy Fieri’s now-closed Times Square restaurant, I have a few questions that have been gnawing at me:

Mr. Wadhwa, when you decided to use the Traveling Salesman Problem as your go-to example of a problem that quantum computers can solve quickly, did the thought ever cross your mind that maybe you should look this stuff up first—let’s say, on Wikipedia?  Or that you should email one person—just one, anywhere on the planet—who works in quantum algorithms?

When you wrote of the Traveling Salesman Problem that “[i]t would take a laptop computer 1,000 years to compute the most efficient route between 22 cities”—how confident are you about that?  Willing to bet your house?  Your car?  How much would it blow your mind if I told you that a standard laptop, running a halfway decent algorithm, could handle 22 cities in a fraction of a second?

When you explained that quantum computing is “equivalent to opening a combination lock by trying every possible number and sequence simultaneously,” where did this knowledge come from?  Did it come from the same source you consulted before you pronounced the death of Bitcoin … in January 2016?

Had you wanted to consult someone who knew the first thing about quantum computing, the subject of your column, would you have been able to use a search engine to find one?  Or would you have simply found another “expert,” in the consulting or think-tank worlds, who “knew” the same things about quantum computing that you do?

Incidentally, when you wrote that quantum computing “could pose a greater burden on businesses than the Y2K computer bug did toward the end of the ’90s,” were you trying to communicate how large the burden might be?

And when you wrote that

[T]here is substantial progress in the development of algorithms that are “quantum safe.” One promising field is matrix multiplication, which takes advantage of the techniques that allow quantum computers to be able to analyze so much information.

—were you generating random text using one of those Markov chain programs?  If not, then what were you referring to?

Would you agree that the Washington Post has been a leader in investigative journalism exposing Trump’s malfeasance?  Do you, like me, consider them one of the most important venues on earth for people to be able to trust right now?  How does it happen that the Washington Post publishes a quantum computing piece filled with errors that would embarrass a high-school student doing a term project (and we won’t even count the reference to Stephen “Hawkings”—that’s a freebie)?

Were the fact-checkers home with the flu?  Did they give your column a pass simply because it was “perspective” rather than news?  Or did they trust you as a widely-published technology expert?  How does one become such an expert, anyway?

Thanks!


Update (Feb. 21): For casual readers, Vivek Wadhwa quickly came into the comments section to try to defend himself—before leaving in a huff as a chorus of commenters tried to explain why he was wrong. As far as I know, he has not posted any corrections to his Washington Post piece. Wadhwa’s central defense was that he was simply repeating what Michelle Simmons, a noted quantum computing experimentalist in Australia, said in various talks in YouTube—which turns out to be largely true (though Wadhwa said explicitly that quantum computers could efficiently solve TSP, while Simmons mostly left this as an unstated implication). As a result, while Wadhwa should obviously have followed the journalistic practice of checking incredible-sounding claims—on Wikipedia if nowhere else!—before repeating them in the Washington Post, I now feel that Simmons shares in the responsibility for this. As John Preskill tweeted, an excellent lesson to draw from this affair is that everyone in our field needs to be careful to say things that are true when speaking to the public.

Three updates

February 5th, 2018
  1. I was extremely sorry to learn about the loss of Joe Polchinski, a few days ago, to brain cancer.  Joe was a leading string theorist, one of the four co-discoverers of the AMPS firewall paradox, and one of the major figures in the Simons It from Qubit collaboration that I’ve been happy to be part of since its inception.  I regret that I didn’t get to know Joe as well as I should have, but he was kind to me in all of our interactions.  He’ll be missed by all who knew him.
  2. Edge has posted what will apparently be its final Annual Edge Question: “What is the last question?”  They asked people to submit just a single, one sentence question “for which they’ll be remembered,” with no further explanation or elaboration.  You can read mine, which not surprisingly is alphabetically the first.  I tried to devise a single question that gestured toward the P vs. NP problem, and the ultimate physical limits of computation, and the prospects for superintelligent AI, and the enormity of what could be Platonically lying in wait for us within finite but exponentially search spaces, and the eternal nerd’s conundrum, of the ability to get the right answers to clearly-stated questions being so ineffectual in the actual world.  I’m not thrilled with the result, but reading through the other questions makes it clear just how challenging it is to ask something that doesn’t boil down to: “When will the rest of the world recognize the importance of my research topic?”
  3. I’m now reaping the fruits of my decision to take a year-long sabbatical from talking to journalists.  Ariel Bleicher, a writer for Quanta magazine, asked to interview me for an article she was writing about the difficulty of establishing quantum supremacy.  I demurred, mentioning my sabbatical, and pointed her to others she could ask instead.  Well, last week the article came out, and while much of it is quite good, it opens with an extended presentation of a forehead-bangingly wrong claim by Cristian Calude: namely, that the Deutsch-Jozsa problem (i.e. computing the parity of two bits) can be solved with one query even by a classical algorithm, so that (in effect) one of the central examples used in introductory quantum computing courses is a lie.  This claim is based on a 2006 paper wherein, with all the benefits of theft over honest toil, Calude changes the query model so that you can evaluate not just the original oracle function f, but an extension of f to the complex numbers (!).  Apparently Calude justifies this by saying that Deutsch also changed the problem, by allowing it to be solved with a quantum computer, so he gets to change the problem as well.  The difference, of course, is that the quantum query complexity model is justified by its relevance for quantum algorithms, and (ultimately) by quantum mechanics being true of our world.  Calude’s model, by contrast, is (as far as I can tell) pulled out of thin air and justified by nothing.  Anyway, I regard this incident as entirely, 100% my fault, and 0% Ariel’s.  How was she to know that, while there are hundreds of knowledgeable quantum computing experts to interview, almost all of them are nice and polite?  Anyway, this has led me to a revised policy: while I’ll still decline interviews, news organizations should feel free to run completed quantum computing pieces by me for quick fact checks.

Interpretive cards (MWI, Bohm, Copenhagen: collect ’em all)

February 3rd, 2018

I’ve been way too distracted by actual research lately from my primary career as a nerd blogger—that’s what happens when you’re on sabbatical.  But now I’m sick, and in no condition to be thinking about research.  And this morning, in a thread that had turned to my views on the interpretation of quantum mechanics called “QBism,” regular commenter Atreat asked me the following pointed question:

Scott, what is your preferred interpretation of QM? I don’t think I’ve ever seen you put your cards on the table and lay out clearly what interpretation(s) you think are closest to the truth. I don’t think your ghost paper qualifies as an answer, BTW. I’ve heard you say you have deep skepticism about objective collapse theories and yet these would seemingly be right up your philosophical alley so to speak. If you had to bet on which interpretation was closest to the truth, which one would you go with?

Many people have asked me some variant of the same thing.  As it happens, I’d been toying since the summer with a huge post about my views on each major interpretation, but I never quite got it into a form I wanted.  By contrast, it took me only an hour to write out a reply to Atreat, and in the age of social media and attention spans measured in attoseconds, many readers will probably prefer that short reply to the huge post anyway.  So then I figured, why not promote it to a full post and be done with it?  So without further ado:


Dear Atreat,

It’s no coincidence that you haven’t seen me put my cards on the table with a favored interpretation of QM!

There are interpretations (like the “transactional interpretation”) that make no sense whatsoever to me.

There are “interpretations” like dynamical collapse that aren’t interpretations at all, but proposals for new physical theories.  By all means, let’s test QM on larger and larger systems, among other reasons because it could tell us that some such theory is true or—vastly more likely, I think—place new limits on it! (People are trying.)

Then there’s the deBroglie-Bohm theory, which does lay its cards on the table in a very interesting way, by proposing a specific evolution rule for hidden variables (chosen to match the predictions of QM), but which thereby opens itself up to the charge of non-uniqueness: why that rule, as opposed to a thousand other rules that someone could write down?  And if they all lead to the same predictions, then how could anyone ever know which rule was right?

And then there are dozens of interpretations that seem to differ from one of the “main” interpretations (Many-Worlds, Copenhagen, Bohm) mostly just in the verbal patter.

As for Copenhagen, I’ve described it as “shut-up and calculate except without ever shutting up about it”!  I regard Bohr’s writings on the subject as barely comprehensible, and Copenhagen as less of an interpretation than a self-conscious anti-interpretation: a studied refusal to offer any account of the actual constituents of the world, and—most of all—an insistence that if you insist on such an account, then that just proves that you cling naïvely to a classical worldview, and haven’t grasped the enormity of the quantum revolution.

But the basic split between Many-Worlds and Copenhagen (or better: between Many-Worlds and “shut-up-and-calculate” / “QM needs no interpretation” / etc.), I regard as coming from two fundamentally different conceptions of what a scientific theory is supposed to do for you.  Is it supposed to posit an objective state for the universe, or be only a tool that you use to organize your experiences?

Also, are the ultimate equations that govern the universe “real,” while tables and chairs are “unreal” (in the sense of being no more than fuzzy approximate descriptions of certain solutions to the equations)?  Or are the tables and chairs “real,” while the equations are “unreal” (in the sense of being tools invented by humans to predict the behavior of tables and chairs and whatever else, while extraterrestrials might use other tools)?  Which level of reality do you care about / want to load with positive affect, and which level do you want to denigrate?

This is not like picking a race horse, in the sense that there might be no future discovery or event that will tell us who was closer to the truth.  I regard it as conceivable that superintelligent AIs will still argue about the interpretation of QM … or maybe that God and the angels argue about it now.

Indeed, about the only thing I can think of that might definitively settle the debate, would be the discovery of an even deeper level of description than QM—but such a discovery would “settle” the debate only by completely changing the terms of it.

I will say this, however, in favor of Many-Worlds: it’s clearly and unequivocally the best interpretation of QM, as long as we leave ourselves out of the picture!  I.e., as long as we say that the goal of physics is to give the simplest, cleanest possible mathematical description of the world that somewhere contains something that seems to correspond to observation, and we’re willing to shunt as much metaphysical weirdness as needed to those who worry themselves about details like “wait, so are we postulating the physical existence of a continuum of slightly different variants of me, or just an astronomically large finite number?” (Incidentally, Max Tegmark’s “mathematical multiverse” does even better than MWI by this standard.  Tegmark is the one waiting for you all the way at the bottom of the slippery slope of always preferring Occam’s Razor over trying to account for the specificity of the observed world.)  It’s no coincidence, I don’t think, that MWI is so popular among those who are also eliminativists about consciousness.

When I taught my undergrad Intro to Quantum Information course last spring—for which lecture notes are coming soon, by the way!—it was striking how often I needed to resort to an MWI-like way of speaking when students got confused about measurement and decoherence. (“So then we apply this unitary transformation U that entangles the system and environment, and we compute a partial trace over the environment qubits, and we see that it’s as if the system has been measured, though of course we could in principle reverse this by applying U-1 … oh shoot, have I just conceded MWI?”)

On the other hand, when (at the TAs’ insistence) we put an optional ungraded question on the final exam that asked students their favorite interpretation of QM, we found that there was no correlation whatsoever between interpretation and final exam score—except that students who said they didn’t believe any interpretation at all, or that the question was meaningless or didn’t matter, scored noticeably higher than everyone else.

Anyway, as I said, MWI is the best interpretation if we leave ourselves out of the picture.  But you object: “OK, and what if we don’t leave ourselves out of the picture?  If we dig deep enough on the interpretation of QM, aren’t we ultimately also asking about the ‘hard problem of consciousness,’ much as some people try to deny that? So for example, what would it be like to be maintained in a coherent superposition of thinking two different thoughts A and B, and then to get measured in the |A⟩+|B⟩, |A⟩-|B⟩ basis?  Would it even be like anything?  Or is there something about our consciousness that depends on decoherence, irreversibility, full participation in the arrow of the time, not living in an enclosed little unitary box like AdS/CFT—something that we’d necessarily destroy if we tried to set up a large-scale interference experiment on our own brains, or any other conscious entities?  If so, then wouldn’t that point to a strange sort of reconciliation of Many-Worlds with Copenhagen—where as soon as we had a superposition involving different subjective experiences, for that very reason its being a superposition would be forevermore devoid of empirical consequences, and we could treat it as just a classical probability distribution?”

I’m not sure, but The Ghost in the Quantum Turing Machine will probably have to stand as my last word (or rather, last many words) on those questions for the time being.

Practicing the modus ponens of Twitter

January 29th, 2018

I saw today that Ryan Lackey generously praised my and Zach Weinersmith’s quantum computing SMBC comic on Twitter:

Somehow this SMBC comic is the best explanation of quantum computing for non-professionals that I’ve ever found

To which the venture capitalist Matthew Ocko replied, in another tweet:

Except Scott Aaronson is a surly little troll who has literally never built anything at all of meaning. He’s a professional critic of braver people.  So, no, this is not a good explanation – anymore than Jeremy Rifkin on CRISPR would be… 🙄

Now, I don’t mind if Ocko hates me, and also hates my and Zach’s comic.  What’s been bothering me is just the logic of his tweet.  Like: what did he have in his head when he wrote the word “So”?  Let’s suppose for the sake of argument that I’m a “surly little troll,” and an ax murderer besides.  How does it follow that my explanation of quantum computing wasn’t good?  To reach that stop in proposition-space, wouldn’t one still need to point to something wrong with the explanation?

But I’m certain that my inability to understand this is just another of my many failings.  In a world where Trump is president, bitcoin is valued at $11,000 when I last checked, and the attack-tweet has fully replaced the argument, it’s obvious that those of us who see a word like “so” or “because,” and start looking for the inferential step, are merely insufficiently brave.  For godsakes, I’m not even on Twitter!  I’m a sclerotic dinosaur who needs to get with the times.

But maybe I, too, could learn the art of the naked ad-hominem.  Let me try: from a Google search, we learn that Ocko is an enthusiastic investor in D-Wave.  Is it possible he’s simply upset that there’s so much excitement right now in experimental quantum computing—including “things of meaning” being built by brave people, at Google and IBM and Rigetti and IonQ and elsewhere—but that virtually none of this involves D-Wave, whose devices remain interesting from various physics and engineering standpoints, but still fail to achieve any clear quantum speedups, just as the professional critics predicted?  Is he upset that the brave system-builders who are racing finally to achieve quantum computational supremacy over the next year, are the ones who actually interacted with academic researchers (sorry: surly little trolls), and listened to what they said?  Who understood, for example, why scaling up to 50+ qubits only made a lot of sense once you had one or two qubits that at least behaved well enough in isolation—which, after years of heroic effort, many of these system-builders now do?

How’d I do?  Was there still too much argument there for the world of 2018?