## First they came for the Iranians

January 25th, 2017

Action Item: If you’re an American academic, please sign the petition against the Immigration Executive Order. (There are already more than eighteen thousand signatories, including Nobel Laureates, Fields Medalists, you name it, but it could use more!)

I don’t expect this petition to have the slightest effect on the regime, but at least we should demonstrate to the world and to history that American academia didn’t take this silently.

I’m sure there were weeks, in February or March 1933, when the educated, liberal Germans commiserated with each other over the latest outrages of their new Chancellor, but consoled themselves that at least none of it was going to affect them personally.

This time, it’s taken just five days, since the hostile takeover of the US by its worst elements, for edicts from above to have actually hurt my life and (much more directly) the lives of my students, friends, and colleagues.

Today, we learned that Trump is suspending the issuance of US visas to people from seven majority-Islamic countries, including Iran (but strangely not Saudi Arabia, the cradle of Wahhabist terrorism—not that that would be morally justified either).  This suspension might last just 30 days, but might also continue indefinitely—particularly if, as seems likely, the Iranian government thumbs its nose at whatever Trump demands that it do to get the suspension rescinded.

So the upshot is that, until further notice, science departments at American universities can no longer recruit PhD students from Iran—a country that, along with China, India, and a few others, has long been the source of some of our best talent.  This will directly affect this year’s recruiting season, which is just now getting underway.  (If Canada and Australia have any brains, they’ll snatch these students, and make the loss America’s.)

But what about the thousands of Iranian students who are already here?  So far, no one’s rounding them up and deporting them.  But their futures have suddenly been thrown into jeopardy.

Right now, I have an Iranian PhD student who came to MIT on a student visa in 2013.  He started working with me two years ago, on the power of a rudimentary quantum computing model inspired by (1+1)-dimensional integrable quantum field theory.  You can read our paper about it, with Adam Bouland and Greg Kuperberg, here.  It so happens that this week, my student is visiting us in Austin and staying at our home.  He’s spent the whole day pacing around, terrified about his future.  His original plan, to do a postdoc in the US after he finishes his PhD, now seems impossible (since it would require a visa renewal).

Look: in the 11-year history of this blog, there have been only a few occasions when I felt so strongly about something that I stood my ground, even in the face of widespread attacks from people who I otherwise respected.  One, of course, was when I spoke out for shy nerdy males, and for a vision of feminism broad enough to recognize their suffering as a problem.  A second was when I was more blunt about D-Wave, and about its and its supporters’ quantum speedup claims, than some of my colleagues were comfortable with.  But the remaining occasions almost all involved my defending the values of the United States, Israel, Zionism, or “the West,” or condemning Islamic fundamentalism, radical leftism, or the worldviews of such individuals as Noam Chomsky or my “good friend” Mahmoud Ahmadinejad.

Which is simply to say: I don’t think anyone on earth can accuse me of secret sympathies for the Iranian government.

But when it comes to student visas, I can’t see that my feelings about the mullahs have anything to do with the matter.  We’re talking about people who happen to have been born in Iran, who came to the US to do math and science.  Would we rather have these young scientists here, filled with gratitude for the opportunities we’ve given them, or back in Iran filled with justified anger over our having expelled them?

To the Trump regime, I make one request: if you ever decide that it’s the policy of the US government to deport my PhD students, then deport me first.  I’m practically begging you: come to my house, arrest me, revoke my citizenship, and tear up the awards I’ve accepted at the White House and the State Department.  I’d consider that to be the greatest honor of my career.

And to those who cheered Trump’s campaign in the comments of this blog: go ahead, let me hear you defend this.

Update (Jan. 27, 2017): To everyone who’s praised the “courage” that it took me to say this, thank you so much—but to be perfectly honest, it takes orders of magnitude less courage to say this, than to say something that any of your friends or colleagues might actually disagree with! The support has been totally overwhelming, and has reaffirmed my sense that the United States is now effectively two countries, an open and a closed one, locked in a cold Civil War.

Some people have expressed surprise that I’d come out so strongly for Iranian students and researchers, “given that they don’t always agree with my politics,” or given my unapologetic support for the founding principles (if not always the actions) of the United States and of Israel. For my part, I’m surprised that they’re surprised! So let me say something that might be clarifying.

I care about the happiness, freedom, and welfare of all the men and women who are actually working to understand the universe and build the technologies of the future, and of all the bright young people who want to join these quests, whatever their backgrounds and wherever they might be found—whether it’s in Iran or Israel, in India or China or right here in the US.  The system of science is far from perfect, and we often discuss ways to improve it on this blog.  But I have not the slightest interest in tearing down what we have now, or destroying the world’s current pool of scientific talent in some cleansing fire, in order to pursue someone’s mental model of what the scientific community used to look like in Periclean Athens—or for that matter, their fantasy of what it would look like in a post-gender post-racial communist utopia.  I’m interested in the actual human beings doing actual science who I actually meet, or hope to meet.

Understand that, and a large fraction of all the political views that I’ve ever expressed on this blog, even ones that might seem to be in tension with each other, fall out as immediate corollaries.

(Related to that, some readers might be interested in a further explanation of my views about Zionism. See also my thoughts about liberal democracy, in response to numerous comments here by Curtis Yarvin a.k.a. Mencius Moldbug a.k.a. “Boldmug.”)

Update (Jan. 29) Here’s a moving statement from my student Saeed himself, which he asked me to share here.

This is not of my best interest to talk about politics. Not because I am scared but because I know little politics. I am emotionally affected like many other fellow human beings on this planet. But I am still in the US and hopefully I can pursue my degree at MIT. But many other talented friends of mine can’t. Simply because they came back to their hometowns to visit their parents. On this matter, I must say that like many of my friends in Iran I did not have a chance to see my parents in four years, my basic human right, just because I am from a particular nationality; something that I didn’t have any decision on, and that I decided to study in my favorite school, something that I decided when I was 15. When, like many other talented friends of mine, I was teaching myself mathematics and physics hoping to make big impacts in positive ways in the future. And I must say I am proud of my nationality – home is home wherever it is. I came to America to do science in the first place. I still don’t have any other intention, I am a free man, I can do science even in desert, if I have to. If you read history you’ll see scientists even from old ages have always been traveling.

As I said I know little about many things, so I just phrase my own standpoint. You should also talk to the ones who are really affected. A good friend of mine, Ahmad, who studies Mechanical engineering in UC Berkeley, came back to visit his parents in August. He is one of the most talented students I have ever seen in my life. He has been waiting for his student visa since then and now he is ultimately depressed because he cannot finish his degree. The very least the academic society can do is to help students like Ahmad finish their degrees even if it is from abroad. I can’t emphasize enough I know little about many things. But, from a business standpoint, this is a terrible deal for America. Just think about it. All international students in this country have been getting free education untill 22, in the American point of reference, and now they are using their knowledge to build technology in the USA. Just do a simple calculation and see how much money this would amount to. In any case my fellow international students should rethink this deal, and don’t take it unless at the least they are treated with respect. Having said all of this I must say I love the people of America, I have had many great friends here, great advisors specially Scott Aaronson and Aram Harrow, with whom I have been talking about life, religion, freedom and my favorite topic the foundations of the universe. I am grateful for the education I received at MIT and I think I have something I didn’t have before. I don’t even hate Mr Trump. I think he would feel different if we have a cup of coffee sometime.

Update (Feb. 2): If you haven’t been checking the comments on this post, come have a look if you’d like to watch me and others doing our best to defend the foundations of Enlightenment and liberal democracy against a regiment of monarchists and neoreactionaries, including the notorious Mencius Moldbug, as well as a guy named Jim who explicitly advocates abolishing democracy and appointing Trump as “God-Emperor” with his sons to succeed him. (Incidentally, which son? Is Ivanka out of contention?)

I find these people to be simply articulating, more clearly and logically than most, the worldview that put Trump into office and where it inevitably leads. And any of us who are horrified by it had better get over our incredulity, fast, and pick up the case for modernity and Enlightenment where Spinoza and Paine and Mill and all the others left it off—because that’s what’s actually at stake here, and if we don’t understand that then we’ll continue to be blindsided.

## A day to celebrate

January 20th, 2017

Today—January 20, 2017—I have something cheerful, something that I’m celebrating.  It’s Lily’s fourth birthday. Happy birthday Lily!

As part of her birthday festivities, and despite her packed schedule, Lily has graciously agreed to field a few questions from readers of this blog.  You can ask about her parents, favorite toys, recent trip to Disney World, etc.  Just FYI: to the best of my knowledge, Lily doesn’t have any special insight about computational complexity, although she can write the letters ‘N’ and ‘P’ and find them on the keyboard.  Nor has she demonstrated much interest in politics, though she’s aware that many people are upset because a very bad man just became the president.  Anyway, if you ask questions that are appropriate for a real 4-year-old girl, rather than a blog humor construct, there’s a good chance I’ll let them through moderation and pass them on to her!

Meanwhile, here’s a photo I took of UT Austin students protesting Trump’s inauguration beneath the iconic UT tower.

## My 116-page survey article on P vs. NP: better late than never

January 3rd, 2017

For those who just want the survey itself, not the backstory, it’s here. (Note: Partly because of the feedback I’ve gotten on this blog, it’s now expanded to 121 pages!)

Update (Jan. 23) By request, I’ve prepared a Kindle-friendly edition of this P vs. NP survey—a mere 260 pages!

Two years ago, I learned that John Nash—that John Nash—was, together with Michail Rassias, editing a volume about the great open problems in mathematics.  And they wanted me to write the chapter about the P versus NP question—a question that Nash himself had come close to raising, in a prescient handwritten letter that he sent to the National Security Agency in 1955.

On the one hand, I knew I didn’t have time for such an undertaking, and am such a terrible procrastinator that, in both previous cases where I wrote a book chapter, I singlehandedly delayed the entire volume by months.  But on the other hand, John Nash.

So of course I said yes.

What followed was a year in which Michail sent me increasing panicked emails (and then phone calls) informing me that the whole volume was ready for the printer, except for my P vs. NP thing, and is there any chance I’ll have it by the end of the week?  Meanwhile, I’m reading yet more papers about Karchmer-Wigderson games, proof complexity, time/space tradeoffs, elusive functions, and small-depth arithmetic circuits.  P vs. NP, as it turns out, is now a big subject.

And in the middle of it, on May 23, 2015, John Nash and his wife Alicia were tragically killed on the New Jersey Turnpike, on their way back from the airport (Nash had just accepted the Abel Prize in Norway), when their taxi driver slammed into a guardrail.

But while Nash himself sadly wouldn’t be alive to see it, the volume was still going forward.  And now we were effectively honoring Nash’s memory, so I definitely couldn’t pull out.

So finally, last February, after more months of struggle and delay, I sent Michail what I had, and it duly appeared in the volume Open Problems in Mathematics.

But I knew I wasn’t done: there was still sending my chapter out to experts to solicit their comments.  This I did, and massively-helpful feedback started pouring in, creating yet more work for me.  The thorniest section, by far, was the one about Geometric Complexity Theory (GCT): the program, initiated by Ketan Mulmuley and carried forward by a dozen or more mathematicians, that seeks to attack P vs. NP and related problems using a fearsome arsenal from algebraic geometry and representation theory.  The experts told me, in no uncertain terms, that my section on GCT got things badly wrong—but they didn’t agree with each other about how I was wrong.  So I set to work trying to make them happy.

And then I got sidetracked with the move to Austin and with other projects, so I set the whole survey aside: a year of sweat and tears down the toilet.  Soon after that, Bürgisser, Ikenmeyer, and Panova proved a breakthrough “no-go” theorem, substantially changing the outlook for the GCT program, meaning yet more work for me if and when I ever returned to the survey.

Anyway, today, confined to the house with my sprained ankle, I decided that the perfect was the enemy of the good, and that I should just finish the damn survey and put it up on the web, so readers can benefit from it before the march of progress (we can hope!) renders it totally obsolete.

So here it is!  All 116 pages, 268 bibliography entries, and 52,000 words.

For your convenience, here’s the abstract:

In 1955, John Nash sent a remarkable letter to the National Security Agency, in which—seeking to build theoretical foundations for cryptography—he all but formulated what today we call the P=?NP problem, considered one of the great open problems of science.  Here I survey the status of this problem in 2017, for a broad audience of mathematicians, scientists, and engineers.  I offer a personal perspective on what it’s about, why it’s important, why it’s reasonable to conjecture that P≠NP is both true and provable, why proving it is so hard, the landscape of related problems, and crucially, what progress has been made in the last half-century toward solving those problems.  The discussion of progress includes diagonalization and circuit lower bounds; the relativization, algebrization, and natural proofs barriers; and the recent works of Ryan Williams and Ketan Mulmuley, which (in different ways) hint at a duality between impossibility proofs and algorithms.

Thanks so much to everyone whose feedback helped improve the survey.  If you have additional feedback, feel free to share in the comments section!  My plan is to incorporate the next round of feedback by the year 2100, if not earlier.

Update (Jan. 4) Bill Gasarch writes to tell me that Lazslo Babai has posted an announcement scaling back his famous “Graph Isomorphism in Quasipolynomial Time” claim. Specifically, Babai says that, due to an error discovered by Harald Helfgott, his graph isomorphism algorithm actually runs in about 22^O(√log(n)) time, rather than the originally claimed npolylog(n). This still beats the best previously-known running time for graph isomorphism (namely, 2O(√(n log n))), and by a large margin, but not quite as large as before.

Babai pointedly writes:

I apologize to those who were drawn to my lectures on this subject solely because of the quasipolynomial claim, prematurely magnified on the internet in spite of my disclaimers.

Alas, my own experience has taught me the hard way that, on the Internet, it is do or do not. There is no disclaim.

In any case, I’ve already updated my P vs. NP survey to reflect this new development.

Another Update (Jan. 10) For those who missed it, Babai has another update saying that he’s fixed the problem, and the running time of his graph isomorphism algorithm is back to being quasipolynomial.

Update (Jan. 19): This moment—the twilight of the Enlightenment, the eve of the return of the human species back to the rule of thugs—seems like as good a time as any to declare my P vs. NP survey officially done. I.e., thanks so much to everyone who sent me suggestions for additions and improvements, I’ve implemented pretty much all of them, and I’m not seeking additional suggestions!

## State

January 1st, 2017

Happy New Year, everyone!  I tripped over a well-concealed hole and sprained my ankle while carrying my daughter across the grass at Austin’s New Years festival, so am now ringing in 2017 lying in bed immobilized, which somehow seems appropriate.  At least Lily is fine, and at least being bedridden gives me ample opportunity to blog.

Another year, another annual Edge question, with its opportunity for hundreds of scientists and intellectuals (including yours truly) to pontificate, often about why their own field of study is the source of the most important insights and challenges facing humanity.  This year’s question was:

What scientific term or concept ought to be more widely known?

With the example given of Richard Dawkins’s “meme,” which jumped into the general vernacular, becoming a meme itself.

My entry, about the notion of “state” (yeah, I tried to focus on the basics), is here.

This year’s question presented a particular challenge, which scientists writing for a broad audience might not have faced for generations.  Namely: to what extent, if any, should your writing acknowledge the dark shadow of recent events?  Does the Putinization of the United States render your little pet debates and hobbyhorses irrelevant?  Or is the most defiant thing you can do to ignore the unfolding catastrophe, to continue building your intellectual sandcastle even as the tidal wave of populist hatred nears?

In any case, the instructions from Edge were clear: ignore politics.  Focus on the eternal.  But people interpreted that injunction differently.

One of my first ideas was to write about the Second Law of Thermodynamics, and to muse about how one of humanity’s tragic flaws is to take for granted the gargantuan effort needed to create and maintain even little temporary pockets of order.  Again and again, people imagine that, if their local pocket of order isn’t working how they want, then they should smash it to pieces, since while admittedly that might make things even worse, there’s also at least 50/50 odds that they’ll magically improve.  In reasoning thus, people fail to appreciate just how exponentially more numerous are the paths downhill, into barbarism and chaos, than are the few paths further up.  So thrashing about randomly, with no knowledge or understanding, is statistically certain to make things worse: on this point thermodynamics, common sense, and human history are all in total agreement.  The implications of these musings for the present would be left as exercises for the reader.

Anyway, I was then pleased when, in a case of convergent evolution, my friend and hero Steven Pinker wrote exactly that essay, so I didn’t need to.

There are many other essays that are worth a read, some of which allude to recent events but the majority of which don’t.  Let me mention a few.

Let me now discuss some disagreements I had with a few of the essays.

• Donald Hoffman on the holographic principle.  For the point he wanted to make, about the mismatch between our intuitions and the physical world, it seems to me that Hoffman could’ve picked pretty much anything in physics, from Galileo and Newton onward.  What’s new about holography?
• Jerry Coyne on determinism.  Coyne, who’s written many things I admire, here offers his version of an old argument that I tear my hair out every time I read.  There’s no free will, Coyne says, and therefore we should treat criminals more lightly, e.g. by eschewing harsh punishments in favor of rehabilitation.  Following tradition, Coyne never engages the obvious reply, which is: “sorry, to whom were you addressing that argument?  To me, the jailer?  To the judge?  The jury?  Voters?  Were you addressing us as moral agents, for whom the concept of ‘should’ is relevant?  Then why shouldn’t we address the criminals the same way?”
• Michael Gazzaniga on “The Schnitt.”  Yes, it’s possible that things like the hard problem of consciousness, or the measurement problem in quantum mechanics, will never have a satisfactory resolution.  But even if so, building a complicated verbal edifice whose sole purpose is to tell people not even to look for a solution, to be satisfied with two “non-overlapping magisteria” and a lack of any explanation for how to reconcile them, never struck me as a substantive contribution to knowledge.  It wasn’t when Niels Bohr did it, and it’s not when someone today does it either.
• I had a related quibble with Amanda Gefter’s piece on “enactivism”: the view she takes as her starting point, that “physics proves there’s no third-person view of the world,” is controversial to put it mildly among those who know the relevant physics.  (And even if we granted that view, surely a third-person perspective exists for the quasi-Newtonian world in which we evolved, and that’s relevant for the cognitive science questions Gefter then discusses.)
• Thomas Bass on information pathology.  Bass obliquely discusses the propaganda, conspiracy theories, social-media echo chambers, and unchallenged lies that helped fuel Trump’s rise.  He then locates the source of the problem in Shannon’s information theory (!), which told us how to quantify information, but failed to address questions about the information’s meaning or relevance.  To me, this is almost exactly like blaming arithmetic because it only tells you how to add numbers, without caring whether they’re numbers of rescued orphans or numbers of bombs.  Arithmetic is fine; the problem is with us.
• In his piece on “number sense,” Keith Devlin argues that the teaching of “rigid, rule-based” math has been rendered obsolete by computers, leaving only the need to teach high-level conceptual understanding.  I partly agree and partly disagree, with the disagreement coming from firsthand knowledge of just how badly that lofty idea gets beaten to mush once it filters down to the grade-school level.  I would say that the basic function of math education is to teach clarity of thought: does this statement hold for all positive integers, or not?  Not how do you feel about it, but does it hold?  If it holds, can you prove it?  What other statements would it follow from?  If it doesn’t hold, can you give a counterexample?  (Incidentally, there are plenty of questions of this type for which humans still outperform the best available software!)  Admittedly, pencil-and-paper arithmetic is both boring and useless—but if you never mastered anything like it, then you certainly wouldn’t be ready for the concept of an algorithm, or for asking higher-level questions about algorithms.
• Daniel Hook on PT-symmetric quantum mechanics.  As far as I understand, PT-symmetric Hamiltonians are equivalent to ordinary Hermitian ones under similarity transformations.  So this is a mathematical trick, perhaps a useful one—but it’s extremely misleading to talk about it as if it were a new physical theory that differed from quantum mechanics.
• Jared Diamond extols the virtues of common sense, of which there are indeed many—but alas, his example is that if a mathematical proof leads to a conclusion that your common sense tells you is wrong, then you shouldn’t waste time looking for the exact mistake.  Sometimes that’s good advice, but it’s pretty terrible applied to Goodstein’s Theorem, the muddy children puzzle, the strategy-stealing argument for Go, or anything else that genuinely is shocking until your common sense expands to accommodate it.  Math, like science in general, is a constant dialogue between formal methods and common sense, where sometimes it’s one that needs to get with the program and sometimes it’s the other.
• Hans Halvorson on matter.  I take issue with Halvorson’s claim that quantum mechanics had to be discarded in favor of quantum field theory, because QM was inconsistent with special relativity.  It seems much better to say: the thing that conflicts with special relativity, and that quantum field theory superseded, was a particular application of quantum mechanics, involving wavefunctions of N particles moving around in a non-relativistic space.  The general principles of QM—unit vectors in complex Hilbert space, unitary evolution, the Born rule, etc.—survived the transition to QFT without the slightest change.

## “THE TALK”: My quantum computing cartoon with Zach Weinersmith

December 14th, 2016

OK, here’s the big entrée that I promised you yesterday:

“THE TALK”: My joint cartoon about quantum comgputing with Zach Weinersmith of SMBC Comics.

In case you’re wondering how this came about: after our mutual friend Sean Carroll introduced me and Zach for a different reason, the idea of a joint quantum computing comic just seemed too good to pass up.  The basic premise—“The Talk”—was all Zach.  I dutifully drafted some dialogue for him, which he then improved and illustrated.  I.e., he did almost all the work (despite having a newborn competing for his attention!).  Still, it was an honor for me to collaborate with one of the great visual artists of our time, and I hope you like the result.  Beyond that, I’ll let the work speak for itself.

## The teaser

December 13th, 2016

Tomorrow, I’ll have something big to announce here.  So, just to whet your appetites, and to get myself back into the habit of blogging, I figured I’d offer you an appetizer course: some more miscellaneous non-Trump-related news.

(1) My former student Leonid Grinberg points me to an astonishing art form, which I somehow hadn’t known about: namely, music videos generated by executable files that fit in only 4K of memory.  Some of these videos have to be seen to be believed.  (See also this one.)  Much like, let’s say, a small Turing machine whose behavior is independent of set theory, these videos represent exercises in applied (or, OK, recreational) Kolmogorov complexity: how far out do you need to go in the space of all computer programs before you find beauty and humor and adaptability and surprise?

Admittedly, Leonid explains to me that the rules allow these programs to call DirectX and Visual Studio libraries to handle things like the 3D rendering (with the libraries not counted toward the 4K program size).  This makes the programs’ existence merely extremely impressive, rather than a sign of alien superintelligence.

In some sense, all the programming enthusiasts over the decades who’ve burned their free time and processor cycles on Conway’s Game of Life and the Mandelbrot set and so forth were captivated by the same eerie beauty showcased by the videos: that of data compression, of the vast unfolding of a simple deterministic rule.  But I also feel like the videos add a bit extra: the 3D rendering, the music, the panning across natural or manmade-looking dreamscapes.  What we have here is a wonderful resource for either an acid trip or an undergrad computability and complexity course.

(2) A week ago Igor Oliveira, together with my longtime friend Rahul Santhanam, released a striking paper entitled Pseudodeterministic Constructions in Subexponential Time.  To understand what this paper does, let’s start with Terry Tao’s 2009 polymath challenge: namely, to find a fast, deterministic method that provably generates large prime numbers.  Tao’s challenge still stands today: one of the most basic, simplest-to-state unsolved problems in algorithms and number theory.

To be clear, we already have a fast deterministic method to decide whether a given number is prime: that was the 2002 breakthrough by Agrawal, Kayal, and Saxena.  We also have a fast probabilistic method to generate large primes: namely, just keep picking n-digit numbers at random, test each one, and stop when you find one that’s prime!  And those methods can be made deterministic assuming far-reaching conjectures in number theory, such as Cramer’s Conjecture (though note that even the Riemann Hypothesis wouldn’t lead to a polynomial-time algorithm, but “merely” a faster exponential-time one).

But, OK, what if you want a 5000-digit prime number, and you want it now: provably, deterministically, and fast?  That was Tao’s challenge.  The new paper by Oliveira and Santhanam doesn’t quite solve it, but it makes some exciting progress.  Specifically, it gives a deterministic algorithm to generate n-digit prime numbers, with merely the following four caveats:

• The algorithm isn’t polynomial time, but subexponential (2n^o(1)) time.
• The algorithm isn’t deterministic, but pseudodeterministic (a concept introduced by Gat and Goldwasser).  That is, the algorithm uses randomness, but it almost always succeeds, and it outputs the same n-digit prime number in every case where it succeeds.
• The algorithm might not work for all input lengths n, but merely for infinitely many of them.
• Finally, the authors can’t quite say what the algorithm is—they merely prove that it exists!  If there’s a huge complexity collapse, such as ZPP=PSPACE, then the algorithm is one thing, while if not then the algorithm is something else.

Strikingly, Oliveira and Santhanam’s advance on the polymath problem is pure complexity theory: hitting sets and pseudorandom generators and win-win arguments and stuff like that.  Their paper uses absolutely nothing specific to the prime numbers, except the facts that (a) there are lots of them (the Prime Number Theorem), and (b) we can efficiently decide whether a given number is prime (the AKS algorithm).  It seems almost certain that one could do better by exploiting more about primes.

(3) I’m in Lyon, France right now, to give three quantum computing and complexity theory talks.  I arrived here today from London, where I gave another two lectures.  So far, the trip has been phenomenal, my hosts gracious, the audiences bristling with interesting questions.

But getting from London to Lyon also taught me an important life lesson that I wanted to share: never fly EasyJet.  Or at least, if you fly one of the European “discount” airlines, realize that you get what you pay for (I’m told that Ryanair is even worse).  These airlines have a fundamentally dishonest business model, based on selling impossibly cheap tickets, but then forcing passengers to check even tiny bags and charging exorbitant fees for it, counting on snagging enough travelers who just naïvely clicked “yes” to whatever would get them from point A to point B at a certain time, assuming that all airlines followed more-or-less similar rules.  Which might not be so bad—it’s only money—if the minuscule, overworked staff of these quasi-airlines didn’t also treat the passengers like beef cattle, barking orders and berating people for failing to obey rules that one could log hundreds of thousands of miles on normal airlines without ever once encountering.  Anyway, if the airlines won’t warn you, then Shtetl-Optimized will.

## Quantum computing news (98% Trump-free)

November 24th, 2016

(1) Apparently Microsoft has decided to make a major investment in building topological quantum computers, which will include hiring Charles Marcus and Matthias Troyer among others.  See here for their blog post, and here for the New York Times piece.  In the race to implement QC among the established corporate labs, Microsoft thus joins the Martinis group at Google, as well as the IBM group at T. J. Watson—though both Google and IBM are focused on superconducting qubits, rather than the more exotic nonabelian anyon approach that Microsoft has long favored and is now doubling down on.  I don’t really know more about this new initiative beyond what’s in the articles, but I know many of the people involved, they’re some of the most serious in the business, and Microsoft intensifying its commitment to QC can only be good for the field.  I wish the new effort every success, despite being personally agnostic between superconducting qubits, trapped ions, photonics, nonabelian anyons, and other QC hardware proposals—whichever one gets there first is fine with me!

(2) For me, though, perhaps the most exciting QC development of the last month was a new preprint by my longtime friend Dorit Aharonov and her colleague Yosi Atia, entitled Fast-Forwarding of Hamiltonians and Exponentially Precise Measurements.  In this work, Dorit and Yosi wield the clarifying sword of computational complexity at one of the most historically confusing issues in quantum mechanics: namely, the so-called “time-energy uncertainty principle” (TEUP).

The TEUP says that, just as position and momentum are conjugate in quantum mechanics, so too are energy and time—with greater precision in energy corresponding to lesser precision in time and vice versa.  The trouble is, it was never 100% clear what the TEUP even meant—after all, time isn’t even an observable in quantum mechanics, just an external parameter—and, to whatever extent the TEUP did have a definite meaning, it wasn’t clear that it was true.  Indeed, as Dorit and Yosi’s paper discusses in detail, in 1961 Dorit’s uncle Yakir Aharonov, together with David Bohm, gave a counterexample to a natural interpretation of the TEUP.  But, despite this and other counterexamples, the general feeling among physicists—who, after all, are physicists!—seems to have been that some corrected version of the TEUP should hold “in all reasonable circumstances.”

But, OK, what do we mean by a “reasonable circumstance”?  This is where Dorit and Yosi come in.   In the new work, they present a compelling case that the TEUP should really be formulated as a tradeoff between the precision of energy measurements and circuit complexity (that is, the minimum number of gates needed to implement the energy measurement)—and in that amended form, the TEUP holds for exactly those Hamiltonians H that can’t be “computationally fast-forwarded.”  In other words, it holds whenever applying the unitary transformation e-iHt requires close to t computation steps, when there’s no magical shortcut that lets you simulate t steps of time evolution with only (say) log(t) steps.  And, just as the physicists handwavingly thought, that should indeed hold for “generic” Hamiltonians H (assuming BQP≠PSPACE), although it’s possible to use Shor’s algorithm, for finding the order of an element in a multiplicative group, to devise a counterexample to it.

Anyway, there’s lots of other stuff in the paper, including a connection to the stuff Lenny Susskind and I have been doing about the “generic” growth of circuit complexity, in the CFT dual of an expanding wormhole (where we also needed to assume BQP≠PSPACE and closely related complexity separations, for much the same reasons).  Congratulations to Dorit and Yosi for once again illustrating the long reach of computational complexity in physics, and for giving me a reason to be happy this month!

(3) As many of you will have seen, my former MIT colleagues, Lior Eldar and Peter Shor, recently posted an arXiv preprint claiming a bombshell result: namely, a polynomial-time quantum algorithm to solve a variant of the Closest Vector Problem in lattices.  Their claimed algorithm wouldn’t yet break lattice-based cryptography, but if the approximation factors could be improved, it would be well on the way to doing so.  This has been one of the most tempting targets for quantum algorithms research for more than twenty years—ever since Shor’s “original” algorithm laid waste to RSA, Diffie-Hellman, elliptic-curve cryptography, and more in a world with scalable quantum computers, leaving lattice-based cryptography as one of the few public-key crypto proposals still standing.

Unfortunately, Lior tells me that Oded Regev has discovered a flaw in the algorithm, which he and Peter don’t currently know how to fix.  So for now, they’re withdrawing the paper (because of the Thanksgiving holiday, the withdrawal won’t take effect on the arXiv until Monday).  It’s still a worthy attempt on a great problem—here’s hoping that they or someone else manage to, as Lior put it to me, “make the algorithm great again.”

## A paper trail that’s never checked might as well not exist

November 23rd, 2016

Update and Action Item: Just since late this afternoon, the Jill Stein campaign has already raised more than $1 million toward requesting hand recounts in Pennsylvania, Michigan, and Wisconsin. Their target is$6-7 million.  I just donated what I could; if you agree with this post, then please do the same.  It doesn’t matter at this point if you disagree with Stein, or even (like me) think she shouldn’t have run: the goal is just to get a recount to happen before the deadline expires.

Another Update (11/24): In an amazing demonstration of the power of online fundraising, the Stein campaign has already, in less than 24 hours, raised the \$2.5 million needed to fund a recount in Wisconsin.  Now they’re working on Pennsylvania and Michigan.  Amusing that Stein seems finally to have found a winning cause: Hillary!  (“Fighting for Hillary even when Hillary won’t fight for herself.”)  Again: please donate here.

Third Update (11/25):  The recount is on is Wisconsin!  The Stein campaign hasn’t yet filed in Pennsylvania or Michigan, but will do so next.  So, all the commenters who came here to explain to me that this was a scam, no judge would it allow it to go forward, etc.: please update your priors.  And next time, if you won’t listen to me, at least listen to Alex Halderman…

This will probably be my last election-related post.  After this (assuming, of course, that the effort I’m writing about fails…), I plan to encase myself in a bubble, stop reading news, and go back to thinking about quantum lower bounds, as if we still lived in a world where it made sense to do so.  But this is important.

As many of you have probably seen, several of the US’s top computer security experts, including my former MIT colleague Ron Rivest and my childhood friend Alex Halderman, have publicly urged that an audit of the US election take place.  But time is quickly running out.  If, for example, the Clinton campaign were to request a hand recount, the deadlines would be this Friday in Wisconsin, Monday in Pennsylvania, and next Wednesday in Michigan.  So far, alas, the Clinton campaign seems to have shown little interest, which would leave it to one of the third-party candidates to request a recount (they have the legal right too, if they can come up with the money for it).  In the meantime, I urge everyone to sign a petition demanding an audit.

For me, the key point is this: given the proven insecurity of electronic voting machines, an audit of paper ballots ought to be completely routine, even if there weren’t the slightest grounds for suspicion.  In this particular case, of course, we know for a fact (!!) that Russian intelligence was engaging in cyber-warfare to influence the US election.  We also know that Russia has both the will and the technological ability to tamper with foreign elections using vote-stealing malware—indeed, it nearly succeeded in doing so in Ukraine’s 2014 election.  Finally, we know that Trump, despite losing the popular vote, surprised just about everyone by outperforming his polls in three crucial swing states—and that within those states, Trump did systematically better in counties that relied on electronic voting machines than in counties that used scanners and paper ballots.

Nate Silver has tweeted that he sees no evidence of foul play, since the discrepancy disappears once you control for the education level of the counties (for more, see this FiveThirtyEight article).

But that’s the thing.  In a sane world, skeptics wouldn’t need to present statistical proof of foul play in order to trigger a hand count.  For if enemy actors know that, in practice, hand counts are never going to happen, then they’re free to be completely brazen in tampering with the childishly-insecure electronic voting machines themselves.  If no one ever looks at them, then the paper records might as well not exist.

Would anyone in the 1950s or 60s have believed that, a half-century hence, Russia actually would acquire the terrifying power over the US that the right-wing Cold Warriors once hyperventilated about—sometimes choosing to exercise that power, sometimes not—and that 2016’s conservatives would either shrug or welcome the development, while the only people who wanted to take reasonable precautions were a few rabble-rousing professors and activists?

Fate has decided that we should live in a branch of the wavefunction where the worst triumph by flaunting their terribleness and where nothing makes sense.  But however infinitesimal the chances anyone will listen, we should still insist that the sensible things be done—if nothing else, then simply as a way to maintain our own mental connection to the world of sense.

Happy Thanksgiving.

## Never, never, never normalize this

November 11th, 2016

It’s become depressingly clear the last few days that even many American liberals don’t understand the magnitude of what’s happened.  Maybe those well-meaning liberals simply have more faith than I do in our nation’s institutions, despite the recent overwhelming evidence to the contrary (if the institutions couldn’t stop a Trump presidency, then what can they stop?).  Maybe they think all Republicans are as bad as Trump, or even that Trump is preferable to a generic Republican.  Or maybe my liberal friends are so obsessed by the comparatively petty rivalries between the far left and the center left—between Sanders and Clinton, or between social-justice types and Silicon Valley nerds—that they’ve lost sight of the only part of this story that anyone will care about a hundred years from now: namely, the delivering of the United States into the hands of a vengeful lunatic and his sycophants.

I was sickened to read Hillary’s concession speech—a speech that can only possibly mean she never meant what she said before, about how “a man you can bait with a tweet must never be trusted with nuclear weapons”—and then to watch President Obama holding a lovey-dovey press conference with Trump in the White House.  President Obama is a wiser man than I am, and I’m sure he had excellent utilitarian reasons to do what he did (like trying to salvage parts of the Affordable Care Act).  But still, I couldn’t help but imagine the speech I would’ve given, had I been in Obama’s shoes:

Trump, and the movement he represents, never accepted me as a legitimate president, even though I won two elections by a much greater margin than he did.  Now, like the petulant child he is, he demands that we accept him as a legitimate president.  To which I say: very well.  I urge my supporters to obey the law, and to eschew violence.  But for God’s sake: protest this puny autocrat in the streets, refuse any cooperation with his administration, block his judicial appointments, and try every legal avenue to get him impeached.  Demonstrate to the rest of the world and to history that there’s a large part of the United States that remained loyal to the nation’s founding principles, and that never accepted this vindictive charlatan.  You can have the White House, Mr. Trump, but you will never have the sanction or support of the Union—only of the Confederacy.

Given the refusal of so many people I respect to say anything like the above, it came as a relief to read a brilliant New York Review of Books piece by Masha Gessen, a Russian journalist who I’d previously known for her fine biography of Grisha Perelman (the recluse who proved the Poincaré Conjecture), and who’s repeatedly risked her life to criticize Vladimir Putin.  Gessen takes Clinton and Obama to task for their (no doubt well-intentioned) appeasement of a monstrous thug.  She then clearly explains why the United States is now headed for the kind of society Russians are intimately familiar with, and she shares the following rules for surviving an autocracy:

1. Believe the autocrat.
2. Do not be taken in by small signs of normality.
3. Institutions will not save you.
4. Be outraged.
5. Don’t make compromises.
6. Remember the future.

Her important essay is well worth reading in full.

In the comments of my last post, an international student posted a heartbreaking question:

As I said before, I have no doubt that many talented students will respond to America’s self-inflicted catastrophe by choosing to study in Canada, the EU, or elsewhere.  I wish they wouldn’t, but I don’t blame them.  At the same time, even in the darkest hour, human affairs are never completely exempt from the laws of supply and demand.  So for example, if Trump caused enough other foreign researchers to leave the US, then it’s possible that a spot at Harvard, Princeton, or MIT could become yours for the taking.

I can’t tell you what to do, but as you ponder your decision, please remember that slightly more than half of Americans—including the overwhelming majority of residents of the major cities and college towns—despise Trump, will always despise Trump, and will try to continue to build a society that upholds the values of the Enlightenment, one that welcomes people of every background.  Granted, the Union side of America has problems of its own, and I know some of those problems as well as anyone.  But at least it’s not the Confederacy, and it’s what you’d mostly be dealing with if you came here.

Finally, I wanted to share some Facebook postings about the election by my friend (and recent interviewer) Julia Galef.  In these posts, Julia sets out some of the same thoughts that I’ve had, but with an eloquence that I haven’t been able to muster.  It’s important to understand that these posts by Julia—whose day job is to run rationality seminars—are far and away the most emotional things I’ve ever seen her write, but they’re also less emotional than anything I could write at this time!

Naturally, my sharing of Julia’s posts shouldn’t be taken to imply that she agrees with everything I’ve said on this blog about the election, or conversely, that I agree with everything she says.  I simply wanted to give her an additional platform to speak for herself.

The rest of this post is Julia:

I’m seeing some well-intentioned posts insisting “See, this is proof we need to be listening to and empathizing with Trump supporters, not just calling them stupid.”

Generally I’m a fan of that kind of thing, but now… Jesus fucking Christ, we TRIED that. Did you not see how many journalists went to small towns and respectfully listened to people say stupid shit like “I can’t vote for Hillary because she’s the antichrist,” and then tried to figure out how that stupid shit was actually, maybe a reasonable argument about trade policy?

Sometimes the answer is not “People are astutely seeing things that I, inside my bubble, have missed.” Sometimes the answer is just “People are fucking morons whose brains are not built to see through bullshit.”

(To be clear, I think this applies to people in general, including Hillary voters. We just happen to have been a bit less moronic in this particular context.)

And fine, if you want to argue that it’s strategically *wise* for us to understand what makes Trump fans tick, so that we can prevent this from happening again — assuming we get the chance — then fine.

But if you keep insisting that we “just don’t understand” that Trump voters aren’t stupid, then I’m going to take a break from the blank look of horror I’ll be wearing all day, and flash you a look of withering incredulity. Maybe Trump voters aren’t stupid in other contexts, but this sure was a fucking stupid, destructive thing they did.

~~~~
EDIT: Predictably, some people are interpreting my point as: Trump supporters are stupid and/or evil, Clinton supporters are not.

That’s not my point. My point is that humans IN GENERAL are bad at reasoning and seeing through bullshit, which caused particularly bad consequences this time via Trump fans, who made a choice that (if the human brain were better at reasoning) they would have realized was net bad for their overall goals, which presumably include avoiding nuclear war.

~~~~~~~~~~~~~~~~~~~~~

I realized it’s not clear to many people exactly why I’m so upset about Trump winning, so let me elaborate.

What upsets me the most about Trump’s victory is not his policies (to the extent that he has coherent policy positions). It’s not even his racism or sexism, though those do upset me. It’s what his victory reveals about the fragility of our democracy.

Trump incites violence at rallies. He spreads lies and conspiracy theories (birtherism, rigged elections) that damage the long-term credibility of the political process, just for his own short-sighted gain. He’s ruined [EDIT: tried to ruin] journalists’ careers for criticizing him, and bragged about it. He’s talked explicitly about his intent to pursue “revenge” on people who crossed him, once he becomes president. He said he would try to jail Hillary. He clearly has little knowledge of, or respect for, the Constitution or international treaties.

And half of our country looked at all that, and either said “Awesome!” or simply shrugged.

Maybe you assume Congress or the courts won’t let Trump get away with anything undemocratic. But did you see the way the Republican leadership swallowed their objections to Trump once he became the nominee, in the name of party unity? Why should we expect them to stand up to him once he’s actually the most powerful man in the world, if they didn’t before (and see earlier points about his love of revenge)?

I really do hope the Trump presidency turns out, somehow, to be not as bad as it seems. But even if that’s the case… we’ve already learned that America cares so little about democratic norms and institutions that it’s happy to elect someone like Trump.

How can you NOT be worried and depressed by that?

~~~~~~~~~~~~~~~~~~~~

OK, first off, this is a pretty sneering article for someone who’s condemning sneering.

Secondly… this is the kind of article I was responding to, in my angry post a couple of days ago.

(The point of that post got misinterpreted by a lot of people — which is understandable, because I was simultaneously trying to convey #1: a nuanced point AND #2: a lot of strong emotion at the same time. I still endorse both the point and the emotion, it’s just tricky to do both well at once. This post is an attempt to just focus on #1.)

What I was trying to say is that I think electing Trump was a very destructive and stupid thing to do. And that I reject the implication, from people like this columnist, that we have to pretend that Trump voters had sensible, well-thought out reasons for their choice, because I do not think that is the case.

I ALSO think that most voters in general, not just Trump voters, do not have sensible, well-thought out reasons for their voting choices, and there is plenty of evidence to back that up. I think humans simply aren’t the kinds of creatures who are good at making sensible choices about complicated, ideologically-charged topics.

None of this means that we should give up on democracy, just that there are some serious risks that come with democracy. And I disagree with this columnist’s scorn for Andrew Sullivan’s suggestion that we should think about ways to mitigate those risks. Plenty of people over the centuries, including the Founders of the USA, have worried about the tyranny of the majority. That worry isn’t just an invention of the modern-day snotty liberal elites, as this columnist seems to think.

Finally, I just want to ask this guy: is there ANY candidate about whom he would allow us to say “Shit, the American voters really screwed this one up”, or is that not possible by definition?

~~~~~~~~~~~~~~~~~~~~~~

Yesterday I argued that the worst thing about Trump was the harm he does to democratic norms and institutions.

From some of the responses, I don’t think I successfully conveyed why that kind of harm is *uniquely* bad — some people seem to think “harms democratic institutions” is just one item in the overall pro-con list, and it just gets tallied up with the other pros and cons, on equal footing.

Let me try to explain why I think that’s the wrong way to look at it.

There’s this scene in the movie 300, where the Spartan king, Leonidas, feels insulted by the demands relayed by the Persian messenger, so he draws a sword on the man.

MESSENGER (shocked): “This is blasphemy, this is madness! No man threatens a messenger!”
… and he shoves the messenger off a cliff.

I think Leonidas is meant to come off as some kind of heroic, rule-breaking badass. But I watched that and thought, “Jesus, what a shitty thing to do.”

Not just because murder is shitty in general, or because murder is a disproportionate punishment for a perceived slight.

No, it’s because the “don’t harm a messenger” norm is what makes it possible for armies to send messengers to negotiate with each other, to avert or end wars. Defecting on that norm is so much worse than harming a particular person, or army, or country. It’s harming our *ability to limit harm to each other* — a meta-harm.

Our species has worked SO. DAMN. HARD. to build up enough collective trust to be able to have working institutions like constitutions, and treaties, and elections, and a free press, and peaceful transitions. And basically everything good in our lives depends on us collectively agreeing to treat those institutions seriously. I don’t care what party you’re in, or what policies you support — that should all come second to warding off meta-harms that undermine our ability to cooperate with each other enough to have a working society.

I’m not going to claim that politicians were perfect at respecting norms before Trump came along. But Trump is unprecedented. Partly in how blatant he is about his lack of respect for norms in general.

But also in how *discrete* his defections are — he’s not just incrementally bending norms that lots of other people before him have already bent.

We used to be able to say “In America, presidents don’t threaten to jail their political rivals.” Now we can’t.

We used to be able to say, “In America, presidents don’t sow doubts about the legitimacy of elections.” Now we can’t.

We used to be able to say, “In America, presidents don’t encourage violence against protesters.” Now we can’t.

Even joking about those norms, from someone in a position of power, undermines them. If Trump was actually joking about jailing Hillary, I suppose that’s better than if he was serious, but it still deals a blow to the norm. The health of the norm depends on us showing each other that we understand it’s important.

And I just feel despairing that so many Americans don’t seem to feel the same. Like, I don’t expect everyone to have thought through the game theory, but I just assumed people at least had an intuitive sense of these norms being sacred.

… And most of all, I’m worried that those of us who *do* feel shock at those norms being violated will gradually lose our sense of shock, as the post-Trump era wears on.

Update (Nov. 12) Since I apparently wasn’t, let me be perfectly clear. The fact that Trump’s voters unleashed a monster on the world does not make them evil or idiots. It “merely” makes them catastrophically mistaken. Just as I did (and took a lot flak for doing!) before the election, I will continue to oppose any efforts to harass individual Trump supporters, get them fired from their jobs, punish other people for associating with them, etc. To do that, while also militantly refusing to normalize Trump’s autocratic rule over the US, is admittedly to walk an incredibly narrow tightrope—and yet I don’t see anything on either side of the tightrope that’s consistent with my beliefs.

Some readers might also be interested in my reflections on being on the “same side” as Amanda Marcotte.

## What is there to say?

November 9th, 2016

Update (Nov. 10): In the wake of the US’s authoritarian takeover, I will sadly understand if foreign students and postdocs no longer wish to study in the US, or if foreign researchers no longer wish to enter the US even for conferences and visits. After all, I wouldn’t feel safe in Erdogan’s Turkey or the Mullahs’ Iran. In any case, I predict that the US’s scientific influence will now start to wane, as top researchers from elsewhere find ways to route around us.

I make just one request: if you do come to the US (as I selfishly hope you will), please don’t avoid places like Austin just because they look on the map like they’re in a sea of red. To understand what’s going on, you need to look at the detailed county-by-county results, which show that even in “red” states, most cities went overwhelmingly for Clinton, while even in “blue” states like New York, most rural areas went for Trump. Here’s Texas, for example (Austin was 66% Clinton, 27% Trump).

I’m ashamed of my country and terrified about the future.  When Bush took power in 2000, I was depressed for weeks, but I didn’t feel like I do now, like a fourth-generation refugee in the United States—like someone who happens to have been born here and will presumably continue to live here, unless and until it starts to become unsafe for academics, or Jews, or people who publicly criticize Trump, at which time I guess we’ll pack up and go somewhere else (assuming there still is a somewhere else).

If I ever missed the danger and excitement that so many European scientists and mathematicians felt in the 1930s, that sense of trying to pursue the truth even in the shadow of an aggressive and unironic evil—OK, I can cross that off the list.  Since I was seven years old or so, I’ve been obsessed by the realization that there are no guardrails that prevent human beings from choosing the worst, that all the adults who soothingly reassure you that “everything always works out okay in the end” are full of it.  Now I get to live through it instead of just reading about it in history books and having nightmares.

If James Comey hadn’t cast what turned out to be utterly unfounded suspicion over Hillary during the height of early voting, maybe the outcome would’ve been different.  If young and poor and minority voters in Wisconsin and North Carolina and elsewhere hadn’t been effectively disenfranchised through huge lines and strategic voter ID laws and closures of polling places, maybe the outcome would’ve been different.  If Russia and WikiLeaks hadn’t interfered by hacking one side and not the other, maybe the outcome would’ve been different.  For that matter, if Russia or some other power hacked the trivially-hackable electronic voting machines that lack paper trails—machines that something like a third of American voters still used this election—there’s an excellent chance we’d never find out.

But in some sense, all of that is beside the point.  For take all of it away, and Trump still would’ve at least come within a few terrifying points of winning—and as Scott Alexander rightly stresses, whatever horrible things are true about the American electorate today, would still have been true had Hillary eked out a narrow win.  It’s just that now we all get to enjoy the consequences of ½±ε of the country’s horrible values.