Customers who liked this quantum recommendation engine might also like its dequantization

July 12th, 2018

I’m in Boulder, CO right now for the wonderful Boulder summer school on quantum information, where I’ll be lecturing today and tomorrow on introductory quantum algorithms.  But I now face the happy obligation of taking a break from all the lecture-preparing and schmoozing, to blog about a striking new result by a student of mine—a result that will probably make an appearance in my lectures as well.

Yesterday, Ewin Tang—an 18-year-old who just finished a bachelor’s at UT Austin, and who will be starting a PhD in CS at the University of Washington in the fall—posted a preprint entitled A quantum-inspired classical algorithm for recommendation systems. Ewin’s new algorithm solves the following problem, very loosely stated: given m users and n products, and incomplete data about which users like which products, organized into a convenient binary tree data structure; and given also the assumption that the full m×n preference matrix is low-rank (i.e., that there are not too many ways the users vary in their preferences), sample some products that a given user is likely to want to buy.  This is an abstraction of the problem that’s famously faced by Amazon and Netflix, every time they tell you which books or movies you “might enjoy.”  What’s striking about Ewin’s algorithm is that it uses only polylogarithmic time: that is, time polynomial in log(m), log(n), the matrix rank, and the inverses of the relevant error parameters.  Admittedly, the polynomial involves exponents of 33 and 24: so, not exactly “practical”!  But it seems likely to me that the algorithm will run much, much faster in practice than it can be guaranteed to run in theory.  Indeed, if any readers would like to implement the thing and test it out, please let us know in the comments section!

As the title suggests, Ewin’s algorithm was directly inspired by a quantum algorithm for the same problem, which Kerenidis and Prakash (henceforth KP) gave in 2016, and whose claim to fame was that it, too, ran in polylog(m,n) time.  Prior to Ewin’s result, the KP algorithm was arguably the strongest candidate there was for an exponential quantum speedup for a real-world machine learning problem.  The new result thus, I think, significantly changes the landscape of quantum machine learning, by killing off one of its flagship applications.  (Note that whether KP gives a real exponential speedup was one of the main open problems mentioned in John Preskill’s survey on the applications of near-term quantum computers.)  At the same time, Ewin’s result yields a new algorithm that can be run on today’s computers, that could conceivably be useful to those who need to recommend products to customers, and that was only discovered by exploiting intuition that came from quantum computing. So I’d consider this both a defeat and a victory for quantum algorithms research.

This result was the outcome of Ewin’s undergraduate thesis project (!), which I supervised. A year and a half ago, Ewin took my intro quantum information class, whereupon it quickly became clear that I should offer this person an independent project.  So I gave Ewin the problem of proving a poly(m,n) lower bound on the number of queries that any classical randomized algorithm would need to make to the user preference data, in order to generate product recommendations for a given user, in exactly the same setting that KP had studied.  This seemed obvious to me: in their algorithm, KP made essential use of quantum phase estimation, the same primitive used in Shor’s factoring algorithm.  Without phase estimation, you seemed to be stuck doing linear algebra on the full m×n matrix, which of course would take poly(m,n) time.  But KP had left the problem open, I didn’t know how to solve it either, and nailing it down seemed like an obvious challenge, if we wanted to establish the reality of quantum speedups for at least one practical machine learning problem.  (For the difficulties in finding such speedups, see my essay for Nature Physics, much of which is still relevant even though it was written prior to KP.)

Anyway, for a year, Ewin tried and failed to rule out a superfast classical algorithm for the KP problem—eventually, of course, discovering the unexpected reason for the failure!  Throughout this journey, I served as Ewin’s occasional sounding board, but can take no further credit for the result.  Indeed, I admit that I was initially skeptical when Ewin told me that phase estimation did not look essential after all for generating superfast recommendations—that a classical algorithm could get a similar effect by randomly sampling a tiny submatrix of the user preference matrix, and then carefully exploiting a variant of a 2004 result by Frieze, Kannan, and Vempala.  So when I was in Berkeley a few weeks ago for the Simons quantum computing program, I had the idea of flying Ewin over to explain the new result to the experts, including Kerenidis and Prakash themselves.  After four hours of lectures and Q&A, a consensus emerged that the thing looked solid.  Only after that gauntlet did I advise Ewin to put the preprint online.

So what’s next?  Well, one obvious challenge is to bring down the running time of Ewin’s algorithm, and (as I mentioned before) to investigate whether or not it could give a practical benefit today.  A different challenge is to find some other example of a quantum algorithm that solves a real-world machine learning problem with only a polylogarithmic number of queries … one for which the exponential quantum speedup will hopefully be Ewin-proof, ideally even provably so!  The field is now wide open.  It’s possible that my Forrelation problem, which Raz and Tal recently used for their breakthrough oracle separation between BQP and PH, could be an ingredient in such a separation.

Anyway, there’s much more to say about Ewin’s achievement, but I now need to run to lecture about quantum algorithms like Simon’s and Shor’s, which do achieve provable exponential speedups in query complexity!  Please join me in offering hearty congratulations, see Ewin’s nicely-written paper for details, and if you have any questions for me or (better yet) Ewin, feel free to ask in the comments.

Update: On the Hacker News thread, some commenters are lamenting that such a brilliant mind as Ewin’s would spend its time figuring out how to entice consumers to buy even more products that they don’t need. I confess that that’s an angle that hadn’t even occurred to me: I simply thought that it was a beautiful question whether you actually need a quantum computer to sample the rows of a partially-specified low-rank matrix in polylogarithmic time, and if the application to recommendation systems helped to motivate that question, then so much the better. Now, though, I feel compelled to point out that, in addition to the potentially lucrative application to Amazon and Netflix, research on low-rank matrix sampling algorithms might someday find many other, more economically worthless applications as well.

Another Update: For those who are interested, streaming video of my quantum algorithms lectures in Boulder are now available:

You can also see all the other lectures here.

My Y Combinator podcast

June 29th, 2018

Here it is, recorded last week at Y Combinator’s office in San Francisco.  For regular readers of this blog, there will be a few things that are new—research projects I’ve been working on this year—and many things that are old.  Hope you enjoy it!  Thanks so much to Craig Cannon of Y Combinator for inviting me.

Associated with the podcast, Hacker News will be doing an AMA with me later today.  I’ll post a link to that when it’s available.  Update: here it is.

I’m at STOC’2018 TheoryFest in Los Angeles right now, where theoretical computer scientists celebrated the 50th anniversary of the conference that in some sense was the birthplace of the P vs. NP problem.  (Two participants in the very first STOC in 1969, Richard Karp and Allan Borodin, were on a panel to share their memories, along with Ronitt Rubinfeld and Avrim Blum, who joined the action in the 1980s.)  There’s been a great program this year—if you’d like to ask me about it, maybe do so in the comments of this post rather than in the AMA.

Ask me anything: moral judgments edition

June 17th, 2018

Reader Lewikee asked when I’d do another “Ask Me Anything.”  So fine, let’s do one now (and for the next 24 hours or so, or until I get too fatigued).  The rules:

• This time around, only questions that ask me to render a moral judgment on some issue, which could be personal, political, or both (I answer plenty of quantum and complexity questions in the comments sections of other posts…)
• One question per person total; no multipart questions or questions that require me to watch a video or read a linked document
• Anything nasty, sneering, or non-genuine will be left in the moderation queue at my discretion

Let me get things started with the following judgment:

It is morally wrong to lie to parents that you’re taking their children away from them for 20 minutes to give them a bath, but then instead separate the children from their parents indefinitely, imprison the parents, and confine the children in giant holding facilities where they can no longer be contacted, as United States border agents are apparently now doing.  And yes, I know that people sometimes make such proclamations not out of genuine moral concern, but simply to virtue-signal for their chosen tribe and attack a rival tribe.  However, as someone who’s angered and offended nearly every tribe on his blog, I hope I might be taken at face value if I simply say: this is wrong.

Update (June 18): OK, thanks to everyone who participated! I’ll circle back to the few questions I haven’t yet gotten to, but no new questions please.

Five announcements

June 12th, 2018
1. For the next two weeks, I’m in Berkeley for the Simons program “Challenges in Quantum Computation” (awesome program, by the way).  If you’re in the Bay Area and wanted to meet, feel free to shoot me an email (easiest for me if you come to Berkeley, though I do have a couple planned trips to SF).  If enough people wanted, we could even do a first-ever dedicated Shtetl-Optimized meetup.
2. More broadly: I’m finally finished my yearlong sabbatical in Israel.  At some point I’ll do a post with my reflections on the experience.  I’ll now be traveling around North America all summer, then returning to UT Austin in the fall.
3. Longtime friend-of-the-blog Boaz Barak, from a university in Cambridge, MA known as Harvard, asks me to invite readers to check out his new free draft textbook Introduction to Theoretical Computer Science, and to post comments about “typos, bugs, confusing explanations and such” in the book’s GitHub repository.  It looks great!
4. This is already almost a month old, but if you enjoy the quantum computing content on this blog and wish to see related content from our carefully selected partners, check out John Preskill’s Y Combinator interview.
5. Here’s the text of Senator Kamala Harris’s bill, currently working its way through the Senate, to create a US Quantum Computing Research Consortium.  Apparently there’s now also a second, competing quantum computing bill (!)—has anyone seen the text of that one?

Update (June 16): Even though I said there wouldn’t be a meetup, enough people eventually emailed wanting to have coffee that we did do the first-ever dedicated Shtetl-Optimized meetup after all—appropriately, given the title of the blog, at Saul’s Delicatessen in Berkeley. It was awesome. I met people working on fascinating and important things, from cheap nuclear energy to data analytics for downballot Democrats, and who I felt very proud to count as readers. Thanks so much to everyone who came; we’ll have to do another one sometime!

Quantum computing for policymakers and philosopher-novelists

June 6th, 2018

Last week Rebecca Newberger Goldstein, the great philosopher and novelist who I’m privileged to call a friend, wrote to ask me whether I “see any particular political and security problems that are raised by quantum computing,” to help her prepare for a conference she’d be attending in which that question would be discussed.  So I sent her the response below, and then decided that it might be of broader interest.

Shtetl-Optimized regulars and QC aficionados will find absolutely nothing new here—move right along, you’ve been warned.  But I decided to post my (slightly edited) response to Rebecca anyway, for two reasons.  First, so I have something to send anyone who asks me the same question in the future—something that, moreover, as Feynman said about the Feynman Lectures on Physics, contains views “not far from my own.”  And second, because, while of course I’ve written many other popular-level quantum computing essays, with basically all of them, my goal was to get the reader to hear the music, so to speak.  On reflection, though, I think there might also be some value in a piece for business and policy people (not to mention humanist intellectuals) that sets aside the harmony of the interfering amplitudes, and just tries to convey some of the words to the song without egregious howlers—which is what Rebecca’s question about “political and security problems” forced me to do.  This being quantum computing, of course, much of what one finds in the press doesn’t even get the lyrics right!  So without further ado:

Dear Rebecca,

If you want something serious and thoughtful about your question, you probably won’t do much better than the recent essay “The Potential Impact of Quantum Computers on Society,” by my longtime friend and colleague Ronald de Wolf.

To elaborate my own thoughts, though: I feel like the political and security problems raised by quantum computing are mostly the usual ones raised by any new technology (national prestige competitions, haves vs have-nots, etc)—but with one added twist, coming from quantum computers’ famous ability to break our current methods for public-key cryptography.

As Ronald writes, you should think of a quantum computer as a specialized device, which is unlikely to improve all or even most of what we do with today’s computers, but which could give dramatic speedups for a few specific problems.  There are three most important types of applications that we know about today:

(1) Simulation of quantum physics and chemistry. This was Richard Feynman’s original application when he proposed quantum computing in 1981, and I think it’s still the most important one economically.  Having a fast, general-purpose quantum simulator could help a lot in designing new drugs, materials, solar cells, high-temperature superconductors, chemical reactions for making fertilizer, etc.  Obviously, these are not applications like web browsing or email that will directly affect the everyday computer user.  But they’re areas where you’d only need a few high-profile successes to generate billions of dollars of value.

(2) Breaking existing public-key cryptography.  This is the most direct political and security implication.  Every time you visit a website that begins with “https,” the authentication and encryption—including, e.g., protecting your credit card number—happen using a cryptosystem based on factoring integers or discrete logarithms or a few other related problems in number theory.  A full, universal quantum computer, if built, is known to be able to break all of this.

Having said that, we all know today that hackers, and intelligence agencies, can compromise people’s data in hundreds of more prosaic ways than by building a quantum computer!  Usually they don’t even bother trying to break the encryption, relying instead on poor implementations and human error.

And it’s also important to understand that a quantum computer wouldn’t mean the end of online security.  There are public-key cryptosystems currently under development—most notably, those based on lattices—that are believed to resist attack even by quantum computers; NIST is planning to establish standards for these systems over the next few years.  Switching to these “post-quantum” systems would be a significant burden, much like fixing the Y2K bug (and they’re also somewhat slower than our current systems), but hopefully it would only need to happen once.

As you might imagine, there’s some interest in switching to post-quantum cryptosystems even now—for example, if you wanted to encrypt messages today with some confidence they won’t be decrypted even 30 years from now.  Google did a trial of a post-quantum cryptosystem two years ago.  On the other hand, given that a large fraction of web servers still use 512-bit “export grade” cryptography that was already breakable in the 1990s (good news: commenter Viktor Dukhovni tells me that this has now been mostly fixed, since security experts, including my childhood friend Alex Halderman, raised a stink about it a few years ago), it’s a safe bet that getting everyone to upgrade would take quite a long time, even if the experts agreed (which they don’t yet) which of the various post-quantum cryptosystems should become the new standard.  And since, as I said, most attacks target mistakes in implementation rather than the underlying cryptography, we should expect any switch to post-quantum cryptography to make security worse rather than better in the short run.

As a radical alternative to post-quantum crypto, there’s also (ironically enough) quantum cryptography, which doesn’t work over the existing Internet—it requires setting up new communications infrastructure—but which has already been deployed in a tiny number of places, and which promises security based only on quantum physics (and, of course, on the proper construction of the hardware), as opposed to mathematical problems that a quantum computer or any other kind of computer could potentially solve.  According to a long-running joke (or not-quite-joke) in our field, one of the central applications of quantum computing will be to create demand for quantum cryptography!

Finally, there’s private-key cryptography—i.e., the traditional kind, where the sender and recipient meet in secret to agree on a key in advance—which is hardly threatened by quantum computing at all: you can achieve the same level of security as before, we think, by simply doubling the key lengths.  If there’s no constraint on key length, then the ultimate here is the one-time pad, which when used correctly, is theoretically unbreakable by anything short of actual physical access to the sender or recipient (e.g., hacking their computers, or beating down their doors with an ax).  But while private-key crypto might be fine for spy agencies, it’s impractical for widespread deployment on the Internet, unless we also have a secure way to distribute the keys.  This is precisely where public-key crypto typically gets used today, and where quantum crypto could in principle be used in the future: to exchange private keys that are then used to encrypt and decrypt the actual data.

I should also mention that, because it breaks elliptic-curve-based signature schemes, a quantum computer might let a thief steal billions of dollars’ worth of Bitcoin.  Again, this could in principle be fixed by migrating Bitcoin (and other cryptocurrencies) to quantum-resistant cryptographic problems, but that hasn’t been done yet.

(3) Optimization and machine learning.  These are obviously huge application areas for industry, defense, and pretty much anything else.  The main issue is just that we don’t know how to get as large a speedup from a quantum computer as we’d like for these applications.  A quantum computer, we think, will often be able to solve optimization and machine learning problems in something like the square root of the number of steps that would be needed classically, using variants of what’s called Grover’s algorithm.  So, that’s significant, but it’s not the exponential speedup and complete game-changer that we’d have for quantum simulation or for breaking public-key cryptography.  Most likely, a quantum computer will be able to achieve exponential speedups for these sorts of problems only in special cases, and no one knows yet how important those special cases will be in practice.  This is a still-developing research area—there might be further theoretical breakthroughs (in inventing new quantum algorithms, analyzing old algorithms, matching the performance of the quantum algorithms by classical algorithms, etc.), but it’s also possible that we won’t really understand the potential of quantum computers for these sorts of problems until we have the actual devices and can test them out.

As for how far away all this is: given the spectacular progress by Google and others over the last few years, my guess is that we’re at most a decade away from some small, special-purpose quantum computers (with ~50-200 qubits) that could be useful for quantum simulation.  These are what the physicist John Preskill called “Noisy Intermediate Scale Quantum” (NISQ) computers in his excellent recent essay.

However, my guess is also that it will take longer than that to get the full, error-corrected, universal quantum computers that would be needed for optimization and (most relevant to your question) for breaking public-key cryptography.  Currently, the engineering requirements for a “full, universal” quantum computer look downright scary—so we’re waiting either for further breakthroughs that would cut the costs by a few more orders of magnitude (which, by their very nature, can’t be predicted), or for some modern-day General Groves and Oppenheimer who’d be licensed to spend however many hundreds of billions of dollars it would take to make it happen sooner.

The race to build “NISQ” devices has been heating up, with a shift from pure academic research to venture capitalists and industrial efforts just within the last 4-5 years, noticeably changing the character of our field.

In this particular race, I think that the US is the clear world leader right now—specifically, Google, IBM, Intel, Microsoft, University of Maryland / NIST, and various startups—followed by Europe (with serious experimental efforts in the Netherlands, Austria, and the UK among other places).  Here I should mention that the EU has a new 1-billion-Euro initiative in quantum information.  Other countries that have made or are now making significant investments include Canada, Australia, China, and Israel.  Surprisingly, there’s been very little investment in Russia in this area, and less than I would’ve expected in Japan.

China is a very interesting case.  They’ve chosen to focus less on quantum computing than on the related areas of quantum communication and cryptography, where they’ve become the world leader.  Last summer, in a big upset, China launched the first satellite (“Micius”) specifically for quantum communications, and were able to use it to do quantum cryptography and to distribute entanglement over thousands of miles (from one end of China to the other), the previous record being maybe 100 miles.  If the US has anything comparable to this, it isn’t publicly known (my guess is that we don’t).

This past year, there were hearings in Congress about the need for the US to invest more in quantum information, for example to keep up with China, and it looks likely to happen.  As indifferent or hostile as the current administration has been toward science more generally, the government and defense people I’ve met are very much on board with quantum information—often more so than I am!  I’ve even heard China’s Micius satellite referred to as the “quantum Sputnik,” the thing that will spur the US and others to spend much more to keep up.

As you’d imagine, part of me is delighted that something so abstruse, and interesting for fundamental science, and close to my heart, is now getting attention and funding at this level.  But part of me is worried by how much of the current boom I know to be fueled by misconceptions, among policymakers and journalists and the general public, about what quantum computers will be able to do for us once we have them.  Basically, people think they’ll be magic oracles that will solve all problems faster, rather than just special classes of problems like the ones I enumerated above—and that they’ll simply allow the continuation of the Moore’s Law that we know and love, rather than being something fundamentally different.  I’ve been trying to correct these misconceptions, on my blog and elsewhere, to anyone who will listen, for all the good that’s done!  In any case, the history of AI reminds us that a crash could easily follow the current boom-time, if the results of quantum computing research don’t live up to people’s expectations.

I guess there’s one final thing I’ll say.  Quantum computers are sometimes analogized to nuclear weapons, as a disruptive technology with implications for global security that scientists theorized about decades before it became technically feasible.  But there are some fundamental differences.  Most obviously: the deterrent value of a nuclear weapon comes if everyone knows you have it but you never need to use it, whereas the intelligence value of a quantum computer comes if you use it but no one knows you have it.

(Which is related to how the Manhattan Project entered the world’s consciousness in August 1945, whereas Bletchley Park—which was much more important to the actual winning of WWII—remained secret until the 1970s.)

As I said before, once your adversaries realized that you had a universal quantum computer, or might have one soon, they could switch to quantum-resistant forms of encryption, at least for their most sensitive secrets—in which case, as far as encryption was concerned, everyone would be more-or-less back where they started.  Such a switch would be onerous, cost billions of dollars, and (in practice) probably open up its own security holes unrelated to quantum computing.  But we think we already basically understand how to do it.

This is one reason why, even in a hypothetical future where hostile powers got access to quantum computers (and despite the past two years, I still don’t think of the US as a “hostile power”—I mean, like, North Korea or ISIS or something…!)—even in that future, I’d still be much less concerned about the hostile powers having this brand-new technology, than I’d be about their having the generations-old technology of fission and fusion bombs.

Best,
Scott

Unrelated Update (June 8): Ian Tierney asked me to advertise a Kickstarter for a short film that he’s planning to make about Richard Feynman, and a letter that he wrote to his first wife Arlene after she died.

The relativized BQP vs. PH problem (1993-2018)

June 3rd, 2018

Update (June 4): OK, I think the blog formatting issues are fixed now—thanks so much to Jesse Kipp for his help!

True story.  A couple nights ago, I was sitting in the Knesset, Israel’s parliament building, watching Gilles Brassard and Charles Bennett receive the Wolf Prize in Physics for their foundational contributions to quantum computing and information.  (The other laureates included, among others, Beilinson and Drinfeld in mathematics; the American honeybee researcher Gene Robinson; and Sir Paul McCartney, who did not show up for the ceremony.)

Along with the BB84 quantum cryptography scheme, the discovery of quantum teleportation, and much else, Bennett and Brassard’s seminal work included some of the first quantum oracle results, such as the BBBV Theorem (Bennett, Bernstein, Brassard, Vazirani), which proved the optimality of Grover’s search algorithm, and thus the inability of quantum computers to solve NP-complete problems in polynomial time in the black-box setting.  It thereby set the stage for much of my own career.  Of course, the early giants were nice enough to bequeath to us a few problems they weren’t able to solve, such as: is there an oracle relative to which quantum computers can solve some problem outside the entire polynomial hierarchy (PH)?  That particular problem, in fact, had been open from 1993 all the way to the present, resisting sporadic attacks by me and others.

As I sat through the Wolf Prize ceremony — the speeches in Hebrew that I only 20% understood (though with these sorts of speeches, you can sort of fill in the inspirational sayings for yourself); the applause as one laureate after another announced that they were donating their winnings to charity; the ironic spectacle of far-right, ultranationalist Israeli politicians having to sit through a beautiful (and uncensored) choral rendition of John Lennon’s “Imagine” — I got an email from my friend and colleague Avishay Tal.  Avishay wrote that he and Ran Raz had just posted a paper online giving an oracle separation between BQP and PH, thereby putting to rest that quarter-century-old problem.  So I was faced with a dilemma: do I look up, at the distinguished people from the US, Canada, Japan, and elsewhere winning medals in Israel, or down at my phone, at the bombshell paper by two Israelis now living in the US?

For those tuning in from home, BQP, or Bounded-Error Quantum Polynomial Time, is the class of decision problems efficiently solvable by a quantum computer.  PH, or the Polynomial Hierarchy, is a generalization of NP to allow multiple quantifiers (e.g., does there exist a setting of these variables such that for every setting of those variables, this Boolean formula is satisfied?).  These are two of the most fundamental complexity classes, which is all the motivation one should need for wondering whether the former is contained in the latter.  If additional motivation is needed, though, we’re effectively asking: could quantum computers still solve problems that were classically hard, even in a hypothetical world where P=NP (and hence P=PH also)?  If so, the problems in question could not be any of the famous ones like factoring or discrete logarithms; they’d need to be stranger problems, for which a classical computer couldn’t even recognize a solution efficiently, let alone finding it.

And just so we’re on the same page: if BQP ⊆ PH, then one could hope for a straight-up proof of the containment, but if BQP ⊄ PH, then there’s no way to prove such a thing unconditionally, without also proving (at a minimum) that P ≠ PSPACE.  In the latter case, the best we can hope is to provide evidence for a non-containment—for example, by showing that BQP ⊄ PH relative to a suitable oracle.  What’s noteworthy here is that even the latter, limited goal remained elusive for decades.

In 1993, Bernstein and Vazirani defined an oracle problem called Recursive Fourier Sampling (RFS), and proved it was in BQP but not in BPP (Bounded-Error Probabilistic Polynomial-Time).  One can also show without too much trouble that RFS is not in NP or MA, though one gets stuck trying to put it outside AM.  Bernstein and Vazirani conjectured—at least verbally, I don’t think in writing—that RFS wasn’t even in the polynomial hierarchy.  In 2003, I did some work on Recursive Fourier Sampling, but was unable to find a version that I could prove was outside PH.

Maybe this is a good place to explain that, by a fundamental connection made in the 1980s, proving that oracle problems are outside the polynomial hierarchy is equivalent to proving lower bounds on the sizes of AC0 circuits—or more precisely, constant-depth Boolean circuits with unbounded fan-in and a quasipolynomial number of AND, OR, and NOT gates.  And proving lower bounds on the sizes of AC0 circuits is (just) within complexity theory’s existing abilities—that’s how, for example, Furst-Saxe-Sipser, Ajtai, and Yao managed to show that PH ≠ PSPACE relative to a suitable oracle (indeed, even a random oracle with probability 1).  Alas, from a lower bounds standpoint, Recursive Fourier Sampling is a horrendously complicated problem, and none of the existing techniques seemed to work for it.  And that wasn’t even the only problem: even if one somehow succeeded, the separation that one could hope for from RFS was only quasipolynomial (n versus nlog n), rather than exponential.

Ten years ago, as I floated in a swimming pool in Cambridge, MA, it occurred to me that RFS was probably the wrong way to go.  If you just wanted an oracle separation between BQP and PH, you should focus on a different kind of problem—something like what I’d later call Forrelation.  The Forrelation problem asks: given black-box access to two Boolean functions f,g:{0,1}n→{0,1}, are f and g random and independent, or are they random individually but with each one close to the Boolean Fourier transform of the other one?  It’s easy to give a quantum algorithm to solve Forrelation, even with only 1 query.  But the quantum algorithm really seems to require querying all the f- and g-inputs in superposition, to produce an amplitude that’s a global sum of f(x)g(y) terms with massive cancellations in it.  It’s not clear how we’d reproduce this behavior even with the full power of the polynomial hierarchy.  To be clear: to answer the question, it would suffice to show that no AC0 circuit with exp(poly(n)) gates could distinguish a “Forrelated” distribution over (f,g) pairs from the uniform distribution.

Using a related problem, I managed to show that, relative to a suitable oracle—in fact, even a random oracle—the relational version of BQP (that is, the version where we allow problems with many valid outputs) is not contained in the relational version of PH.  I also showed that a lower bound for Forrelation itself, and hence an oracle separation between the “original,” decision versions of BQP and PH, would follow from something that I called the “Generalized Linial-Nisan Conjecture.”  This conjecture talked about the inability of AC0 circuits to distinguish the uniform distribution from distributions that “looked close to uniform locally.”  My banging the drum about this, I’m happy to say, initiated a sequence of events that culminated in Mark Braverman’s breakthrough proof of the original Linial-Nisan Conjecture.  But alas, I later discovered that my generalized version is false.  This meant that different circuit lower bound techniques, ones more tailored to problems like Forrelation, would be needed to go the distance.

I never reached the promised land.  But my consolation prize is that Avishay and Ran have now done so, by taking Forrelation as their jumping-off point but then going in directions that I’d never considered.

As a first step, Avishay and Ran modify the Forrelation problem so that, in the “yes” case, the correlation between f and the Fourier transform of g is much weaker (though still detectable using a quantum algorithm that makes nO(1) queries to f and g).  This seems like an inconsequential change—sure, you can do that, but what does it buy you?—but it turns out to be crucial for their analysis.  Ultimately, this change lets them show that, when we write down a polynomial that expresses an AC0 circuit’s bias in detecting the forrelation between f and g, all the “higher-order contributions”—those involving a product of k terms of the form f(x) or g(y), for some k>2—get exponentially damped as a function of k, so that only the k=2 contributions still matter.

There are a few additional ideas that Raz and Tal need to finish the job.  First, they relax the Boolean functions f and g to real-valued, Gaussian-distributed functions—very similar to what Andris Ambainis and I did when we proved a nearly-tight randomized lower bound for Forrelation, except that they also need to truncate f and g so they take values in [-1,1]; they then prove that a multilinear polynomial has no way to distinguish their real-valued functions from the original Boolean ones.  Second, they exploit recent results of Tal about the Fourier spectra of AC0 functions.  Third, they exploit recent work of Chattopadhyay et al. on pseudorandom generators from random walks (Chattopadhyay, incidentally, recently finished his PhD at UT Austin).  A crucial idea turns out to be to think of the values of f(x) and g(y), in a real-valued Forrelation instance, as sums of huge numbers of independent random contributions.  Formally, this changes nothing: you end up with exactly the same Gaussian distributions that you had before.  Conceptually, though, you can look at how each tiny contribution changes the distinguishing bias, conditioned on the sum of all the previous contributions; and this leads to the suppression of higher-order terms that we talked about before, with the higher-order terms going to zero as the step size does.

Stepping back from the details, though, let me talk about a central conceptual barrier—one that I know from an email exchange with Avishay was on his and Ran’s minds, even though they never discuss it explicitly in their paper.  In my 2009 paper, I identified what I argued was the main reason why no existing technique was able to prove an oracle separation between BQP and PH.  The reason was this: the existing techniques, based on the Switching Lemma and so forth, involved arguing (often implicitly) that

1. any AC0 circuit can be approximated by a low-degree real polynomial, but
2. the function that we’re trying to compute can’t be approximated by a low-degree real polynomial.

Linial, Mansour, and Nisan made this fully explicit in the context of their learning algorithm for AC0.  And this is all well and good if, for example, we’re trying to prove the n-bit PARITY function is not in AC0, since PARITY is famously inapproximable by any polynomial of sublinear degree.  But what if we’re trying to separate BQP from PH?  In that case, we need to deal with the fundamental observation of Beals et al. 1998: that any function with a fast quantum algorithm, by virtue of having a fast quantum algorithm, is approximable by a low-degree real polynomial!  Approximability by low-degree polynomials giveth with the one hand and taketh away with the other.

To be sure, I pointed out that this barrier wasn’t necessarily insuperable.  For the precise meaning of “approximable by low-degree polynomials” that follows from a function’s being in BQP, might be different from the meaning that’s used to put the function outside of PH.  As one illustration, Razborov and Smolensky’s AC0 lower bound method relates having a small constant-depth circuit to being approximable by low-degree polynomials over finite fields, which is different from being approximable by low-degree polynomials over the reals.  But this didn’t mean I knew an actual way around the barrier: I had no idea how to prove that Forrelation wasn’t approximable by low-degree polynomials over finite fields either.

So then how do Raz and Tal get around the barrier?  Apparently, by exploiting the fact that Tal’s recent results imply much more than just that AC0 functions are approximable by low-degree real polynomials.  Rather, they imply approximability by low-degree real polynomials with bounded L1 norms (i.e., sums of absolute values) of their coefficients.  And crucially, these norm bounds even apply to the degree-2 part of a polynomial—showing that, even all the way down there, the polynomial can’t be “spread around,” with equal weight on all its coefficients.  But being “spread around” is exactly how the true polynomial for Forrelation—the one that you derive from the quantum algorithm—works.  The polynomial looks like this:

$$p(f,g) = \frac{1}{2^{3n/2}} \sum_{x,y \in \left\{0,1\right\}^n} (-1)^{x \cdot y} f(x) g(y).$$

This still isn’t enough for Raz and Tal to conclude that Forrelation itself is not in AC0: after all, the higher-degree terms in the polynomial might somehow compensate for the failures of the lower-degree terms.  But this difference between the two different kinds of low-degree polynomial—the “thin” kind that you get from AC0 circuits, and the “thick” kind that you get from quantum algorithms—gives them an opening that they’re able to combine with the other ideas mentioned above, at least for their noisier version of the Forrelation problem.

This difference between “thin” and “thick” polynomials is closely related to, though not identical with, a second difference, which is that any AC0 circuit needs to compute some total Boolean function, whereas a quantum algorithm is allowed to be indecisive on many inputs, accepting them with a probability that’s close neither to 0 nor to 1.  Tal used the fact that an AC0 circuit computes a total Boolean function, in his argument showing that it gives rise to a “thin” low-degree polynomial.  His argument also implies that no low-degree polynomial that’s “thick,” like the above quantum-algorithm-derived polynomial for Forrelation, can possibly represent a total Boolean function: it must be indecisive on many inputs.

The boundedness of the L1 norm of the coefficients is related to a different condition on low-degree polynomials, which I called the “low-fat condition” in my Counterexample to the Generalized Linial-Nisan Conjecture paper.  However, the whole point of that paper was that the low-fat condition turns out not to work, in the sense that there exist depth-three AC0 circuits that are not approximable by any low-degree polynomials satisfying the condition.  Raz and Tal’s L1 boundedness condition, besides being simpler, also has the considerable advantage that it works.

As Lance Fortnow writes, in his blog post about this achievment, an obvious next step would be to give an oracle relative to which P=NP but P≠BQP.  I expect that this can be done.  Another task is to show that my original Forrelation problem is not in PH—or more generally, to broaden the class of problems that can be handled using Raz and Tal’s methods.  And then there’s one of my personal favorite problems, which seems closely related to BQP vs. PH even though it’s formally incomparable: give an oracle relative to which a quantum computer can’t always prove its answer to a completely classical skeptic via an interactive protocol.

Since (despite my journalist moratorium) a journalist already emailed to ask me about the practical implications of the BQP vs. PH breakthrough—for example, for the ~70-qubit quantum computers that Google and others hope to build in the near future—let me take the opportunity to say that, as far as I can see, there aren’t any.  This is partly because Forrelation is an oracle problem, one that we don’t really know how to instantiate explicitly (in the sense, for example, that factoring and discrete logarithm instantiate Shor’s period-finding algorithm).  And it’s partly because, even if you did want to run the quantum algorithm for Forrelation (or for Raz and Tal’s noisy Forrelation) on a near-term quantum computer, you could easily do that sans the knowledge that the problem sits outside the polynomial hierarchy.

Still, as Avi Wigderson never tires of reminding people, theoretical computer science is richly interconnected, and things can turn up in surprising places.  To take a relevant example: Forrelation, which I introduced for the purely theoretical purpose of separating BQP from PH (and which Andris Ambainis and I later used for another purely theoretical purpose, to prove a maximal separation between randomized and quantum query complexities), now furnishes one of the main separating examples in the field of quantum machine learning algorithms.  So it’s early to say what implications Avishay and Ran’s achievement might ultimately have.  In any case, huge congratulations to them.

PDQP/qpoly = ALL

May 19th, 2018

I’ve put up a new paper.  Unusually for me these days, it’s a very short and simple one (8 pages)—I should do more like this!  Here’s the abstract:

We show that combining two different hypothetical enhancements to quantum computation—namely, quantum advice and non-collapsing measurements—would let a quantum computer solve any decision problem whatsoever in polynomial time, even though neither enhancement yields extravagant power by itself. This complements a related result due to Raz. The proof uses locally decodable codes.

I welcome discussion in the comments.  The real purpose of this post is simply to fulfill a request by James Gallagher, in the comments of my Robin Hanson post:

The probably last chance for humanity involves science progressing, can you apply your efforts to quantum computers, which is your expertise, and stop wasting many hours of you [sic] time with this [expletive deleted]

Indeed, I just returned to Tel Aviv, for the very tail end of my sabbatical, from a weeklong visit to Google’s quantum computing group in LA.  While we mourned tragedies—multiple members of the quantum computing community lost loved ones in recent weeks—it was great to be among so many friends, and great to talk and think for once about actual progress that’s happening in the world, as opposed to people saying mean things on Twitter.  Skipping over its plans to build a 49-qubit chip, Google is now going straight for 72 qubits.  And we now have some viable things that one can do, or try to do, with such a chip, beyond simply proving quantum supremacy—I’ll say more about that in subsequent posts.

Anyway, besides discussing this progress, the other highlight of my trip was going from LA to Santa Barbara on the back of Google physicist Sergio Boixo’s motorcycle—weaving in and out of rush-hour traffic, the tightness of my grip the only thing preventing me from flying out onto the freeway.  I’m glad to have tried it once, and probably won’t be repeating it.

Update: I posted a new version of the PDQP/qpoly=ALL paper, which includes an observation about communication complexity, and which—inspired by the comments section—clarifies that when I say “all languages,” I really do mean “all languages” (even the halting problem).

The stupidest story I ever wrote (it was a long flight)

May 18th, 2018

All the legal maneuvers, the decades of recriminations, came down in the end to two ambiguous syllables.  No one knew why old man Memeson had named his two kids “Laurel” and “Yanny,” or why his late wife had gone along with it.  Not Laura, not Lauren, but Laurel—like, the leaves that the complacent rest on?  Poor girl.  And yet she lucked out compared to her younger brother. “Yanny”? Rhymes with fanny, seriously?  If you got picked on in school half as much as Yanny did, you too might grow up angry enough to spend half your life locked in an inheritance fight.

But people mostly tolerated the old man’s eccentricities, because he clearly knew something. All through the 1930s, Memeson Audio was building the highest-end radios and record players that money could buy.  And long after he’d outdone the competition, Memeson continued to outdo himself. At the 1939 New York World’s Fair, he proudly unveiled a prototype of his finest record player yet, the one he’d been tinkering with in his personal workshop for a decade: the Unmistakable.  Interviewed about it later, people who attended the demo swore that you couldn’t mishear a single syllable that came out of the thing if you were 99% deaf. No one had ever heard a machine like it—or would, perhaps, until the advent of digital audio.  On Internet forums, audiophiles still debate how exactly Memeson managed to do it with the technology of the time.  Alas, just like the other Memeson debate—about which more shortly—this one might continue indefinitely, since only one Unmistakable was ever built, and that World’s Fair was the last time anyone heard it.

The day after the triumphant demonstration, a crowd cheered as Memeson boarded a train in Grand Central Station to return to his factory near Chicago, there to supervise the mass production of Unmistakables. Meanwhile Laurel and Yanny, now both in their thirties and helping to run the family firm, stood on the platform and beamed. It hadn’t been easy to grow up with such a singleminded father, one who seemed to love his radios a million times more than them, but at a moment like this, it almost felt worth it.  When Laurel and Yanny returned to the Fair to continue overseeing the Memeson Audio exhibition, they’d be the highest-ranking representatives of the company, and would bask in their old man’s reflected glory.

In biographies, Memeson is described as a pathological recluse, who’d hole himself up in his workshop for days at a time, with strict orders not to be disturbed by anyone.  But on this one occasion—as it turned out, the last time he’d ever be seen in public—Memeson was as hammy as could be.  As the train pulled out of Grand Central, he leaned out of an open window in his private car and grinned for the cameras, waving with one arm and holding up the Unmistakable with the other.

Every schoolchild knows what happened next: the train derailed an hour later.  Along with twenty other passengers, Memeson was killed, while all that remained of his Unmistakable was a mess of wires and splintered wood.

Famously, there was one last exchange. As the train began moving, a journalist waved his hat at Memeson and called out “safe travels, sir!”

Memeson smiled and tipped his hat.

Then, noticing Laurel and Yanny on the platform, the journalist yelled to Memeson, in jest (or so he thought): “if something happens, which of these two is next in line to run the business?”

The old man had never been known for his sense of humor, and seemed from his facial expression (or so witnesses would later say) to treat the question with utmost seriousness. As the train receded into the distance, he shouted—well, everyone agrees that it was two syllables. But which? With no written will to consult—one of Memeson’s many idiosyncrasies was his defiance of legal advice—it all came down to what people heard, or believed, or believed they heard.

On the one hand, it would of course be extremely unusual back then for a woman to lead a major technology firm. And Memeson had never shown the slightest interest in social causes: not women’s suffrage, not the New Deal, nothing. In court, Yanny’s lawyers would press these points, arguing that the old man couldn’t possibly have intended to pass on his empire to a daughter.

On the other hand, Laurel was his first-born child.  And some people said that, if Memeson had ever had a human connection with anyone, it was with her.  There were even employees who swore that, once in a while, Laurel was seen entering and leaving her dad’s workshop—a privilege the old man never extended to Yanny or anyone else. Years later, Laurel would go so far as to claim that, during these visits, she’d contributed crucial ideas to the design of the Unmistakable. Most commentators dismiss this claim as bluster: why would she wait to drop such a bombshell until she and Yanny had severed their last ties, until both siblings’ only passion in life was to destroy the other, to make the world unable to hear the other’s name?

At any rate, neither Laurel nor anyone else was ever able to build another Unmistakable, or to give a comprehensible account of how it worked.  But Laurel certainly has die-hard defenders to this day—and while I’ve tried to be evenhanded in this account, I confess to being one of them.

In the end, who people believed about this affair seemed to come down to where they stood—literally. Among the passengers in the train cars adjoining Memeson’s, the ones who heard him are generally adamant that they heard “Laurel”; while most who stood on the platform are equally insistent about “Yanny.”  Today, some Memeson scholars theorize that this discrepancy is due to a Doppler effect.  People on the platform would’ve heard a lower pitch than people comoving with Memeson, and modern reconstructions raise the possibility, however farfetched, that this alone could “morph” one name to the other.  If we accept this, then it suggests that Memeson himself would have intended “Laurel”—but pitch changing a word?  Really?

Today, Laurel and Yanny are both gone, like their father and his company, but their dispute is carried on by their children and grandchildren, with several claims still winding their way through the courts.

Are there any recordings from the platform?  There is one, which was lost for generations before it unexpectedly turned up again. Alas, any hopes that this recording would definitively resolve the matter were … well, just listen to the thing.  Maybe the audio quality isn’t good enough.  Maybe an Unmistakable recording, had it existed, would’ve revealed the observer-independent truth, given us a unique map from the sensory world to the world of meaning.

The Zeroth Commandment

May 6th, 2018

“I call heaven and earth to witness against you this day, that I have set before thee life and death, the blessing and the curse: therefore choose life, that thou mayest live, thou and thy seed.” –Deuteronomy 30:19

“Remember your humanity, and forget the rest.” –Bertrand Russell and Albert Einstein, 1955

I first met Robin Hanson, professor of economics at George Mason University, in 2005, after he and I had exchanged emails about Aumann’s agreement theorem.  I’d previously read Robin’s paper about that theorem with Tyler Cowen, which is called Are Disagreements Honest?, and which stands today as one of the most worldview-destabilizing documents I’ve ever read.  In it, Robin and Tyler develop the argument that you can’t (for example) assert that

1. you believe that extraterrestrial life probably exists,
2. your best friend believes it probably doesn’t, and
3. you and your friend are both honest, rational people who understand Bayes’ Theorem; you just have a reasonable difference of opinion about the alien question, presumably rooted in differing life experiences or temperaments.

For if, to borrow a phrase from Carl Sagan, you “wish to pursue the question courageously,” then you need to consider “indexical hypotheticals”: possible worlds where you and your friend swapped identities.  As far as the Bayesian math is concerned, the fact that you’re you, and your friend is your friend, is just one more contingent fact to conditionalize on: something that might affect what private knowledge you have, but that has no bearing on whether extraterrestrial life exists or doesn’t.  Once you grasp this point, so the argument goes, you should be just as troubled by the fact that your friend disagrees with you, as you would be were the disagreement between two different aspects of your self.  To put it differently: there might be a billion flavors of irrationality, but insofar as people can talk to each other and are honest and rational, they should converge on exactly the same conclusions about every matter of fact, even ones as remote-sounding as the existence of extraterrestrial life.

When I read this, my first reaction was that it was absurdly wrong and laughable.  I confess that I was even angry, to see something so counter to everything I knew asserted with such blithe professorial confidence.  Yet, in a theme that will surely be familiar with anyone who’s engaged with Robin or his writing, I struggled to articulate exactly why the argument was wrong.  My first guess was that, just like typical straitjacketed economists, Robin and Tyler had simply forgotten that real humans lack unlimited time to think and converse with each other.  Putting those obvious limitations back into the theory, I felt, would surely reinstate the verdict of common sense, that of course two people can agree to disagree without violating any dictates of rationality.

Now, if only I’d had the benefit of a modern education on Twitter and Facebook, I would’ve known that I could’ve stopped right there, with the first counterargument that popped into my head.  I could’ve posted something like the following on all my social media accounts:

“Hanson and Cowen, typical narrow-minded economists, ludicrously claim that rational agents with common priors can’t agree to disagree. They stupidly ignore the immense communication and computation that reaching agreement would take.  Why are these clowns allowed to teach?  SAD!”

Alas, back in 2003, I hadn’t yet been exposed to the epistemological revolution wrought by the 280-character smackdown, so I got the idea into my head that I actually needed to prove my objection was as devastating as I thought.  So I sat down with pen and paper for some hours—and discovered, to my astonishment, that my objection didn’t work at all.  According to my complexity-theoretic refinement of Aumann’s agreement theorem, which I later published in STOC’2005, two Bayesian agents with a common prior can ensure that they agree to within ±ε about the value of a [0,1]-valued random variable, with probability at least 1-δ over their shared prior, by exchanging only O(1/(δε2)) bits of information—completely independent of how much knowledge the agents have.  My conclusion was that, if Aumann’s Nobel-prizewinning theorem fails to demonstrate the irrationality of real-life disagreements, then it’s not for reasons of computational or communication efficiency; it has to be for other reasons instead.  (See also my talk on this at the SPARC summer camp.)

In my and Robin’s conversations—first about Aumann’s theorem, then later about the foundations of quantum mechanics and AI and politics and everything else you can imagine—Robin was unbelievably generous with his time and insights, willing to spend days with me, then a totally unknown postdoc, to get to the bottom of whatever was the dispute at hand.  When I visited Robin at George Mason, I got to meet his wife and kids, and see for myself the almost comical contrast between the conventional nature of his family life and the destabilizing radicalism (some would say near-insanity) of his thinking.  But I’ll say this for Robin: I’ve met many eccentric intellectuals in my life, but I have yet to meet anyone whose curiosity is more genuine than Robin’s, or whose doggedness in following a chain of reasoning is more untouched by considerations of what all the cool people will say about him at the other end.

So if you believe that the life of the mind benefits from a true diversity of opinions, from thinkers who defend positions that actually differ in novel and interesting ways from what everyone else is saying—then no matter how vehemently you disagree with any of his views, Robin seems like the prototype of what you want more of in academia.  To anyone who claims that Robin’s apparent incomprehension of moral taboos, his puzzlement about social norms, are mere affectations masking some sinister Koch-brothers agenda, I reply: I’ve known Robin for years, and while I might be ignorant of many things, on this I know you’re mistaken.  Call him wrongheaded, naïve, tone-deaf, insensitive, even an asshole, but don’t ever accuse him of insincerity or hidden agendas.  Are his open, stated agendas not wild enough for you??

In my view, any assessment of Robin’s abrasive, tone-deaf, and sometimes even offensive intellectual style has to grapple with the fact that, over his career, Robin has originated not one but several hugely important ideas—and his ability to do so strikes me as clearly related to his style, not easily detachable from it.  Most famously, Robin is one of the major developers of prediction markets, and also the inventor of futarchy—a proposed system of government that would harness prediction markets to get well-calibrated assessments of the effects of various policies.  Robin also first articulated the concept of the Great Filter in the evolution of life in our universe.  It’s Great Filter reasoning that tells us, for example, that if we ever discover fossil microbial life on Mars (or worse yet, simple plants and animals on extrasolar planets), then we should be terrified, because it would mean that several solutions to the Fermi paradox that don’t involve civilizations like ours killing themselves off would have been eliminated.  Sure, once you say it, it sounds pretty obvious … but did you think of it?

Earlier this year, Robin published a book together with Kevin Simler, entitled The Elephant In The Brain: Hidden Motives In Everyday Life.  I was happy to provide feedback on the manuscript and then to offer a jacket blurb (though the publisher cut nearly everything I wrote, leaving only that I considered the book “a masterpiece”).  The book’s basic thesis is that a huge fraction of human behavior, possibly the majority of it, is less about its ostensible purpose than about signalling what kind of people we are—and that this has implications for healthcare and education spending, among many other topics.  (Thus, the book covers some of the same ground as The Case Against Education, by Robin’s GMU colleague Bryan Caplan, which I reviewed here.)

I view The Elephant In The Brain as Robin’s finest work so far, though a huge part of the credit surely goes to Kevin Simler.  Robin’s writing style tends to be … spare.  telegraphic.  He gives you the skeleton of an argument, but leaves it to you to add the flesh, the historical context and real-world examples and caveats.  And he never holds your hand by saying anything like: “I know this is going to sound weird, but…”  Robin doesn’t care how weird it sounds.  With EITB, you get the best of both worlds: Robin’s unique-on-this-planet trains of logic, and Kevin’s considerable gifts at engaging prose.  It’s a powerful combination.

I’m by no means an unqualified Hanson fan.  If you’ve ever felt completely infuriated by Robin—if you’ve ever thought, fine, maybe this guy turned out to be unpopularly right some other times, but this time he’s really just being willfully and even dangerously obtuse—then know that I’ve shared that feeling more than most over the past decade.  I recall in particular a lecture that Robin gave years ago in which he argued—and I apologize to Robin if I mangle a detail, but this was definitely the essence—that even if you grant that anthropogenic climate change will destroy human civilization and most complex ecosystems hundreds of years from now, that’s not necessarily something you should worry about, because if you apply the standard exponential time-discounting that economists apply to everything else, along with reasonable estimates for the monetary value of everything on earth, you discover that all life on earth centuries from now just isn’t worth very much in today’s dollars.

On hearing this, the familiar Hanson-emotions filled me: White-hot, righteous rage.  Zeal to cut Robin down, put him in his place, for the sake of all that’s decent in humanity.  And then … confusion about where exactly his argument fails.

For whatever it’s worth, I’d probably say today that Robin is wrong on this, because economists’ exponential discounting implicitly assumes that civilization’s remarkable progress of the last few centuries will continue unabated, which is the very point that the premise of the exercise denies.  But notice what I can’t say: “shut up Robin, we’ve all heard this right-wing libertarian nonsense before.”  Even when Robin spouts nonsense, it’s often nonsense that no one has heard before, brought back from intellectual continents that wouldn’t be on the map had Robin not existed.

So why am I writing about Robin now?  If you haven’t been living in a non-wifi-equipped cave, you probably know the answer.

A week ago, alas, Robin blogged his confusion about why the people most concerned about inequalities of wealth, never seem to be concerned about inequalities of romantic and sexual fulfillment—even though, in other contexts, those same people would probably affirm that relationships are much more important to their personal happiness than wealth is.  As a predictable result of his prodding this angriest hornet’s-nest on the planet, Robin has now been pilloried all over the Internet, in terms that make the attacks on me three years ago over the comment-171 affair look tender and kind by comparison.  The attacks included a Slate hit-piece entitled “Is Robin Hanson America’s Creepiest Economist?” (though see also this in-depth followup interview), a Wonkette post entitled “This Week In Garbage Men: Incels Sympathizers [sic] Make Case for Redistribution of Vaginas,” and much more.  Particularly on Twitter, Robin’s attackers have tended to use floridly profane language, and to target his physical appearance and assumed sexual proclivities and frustrations; some call for his firing or death.  I won’t link to the stuff; you can find it.

Interestingly, many of the Twitter attacks assume that Robin himself must be an angry “incel” (short for “involuntary celibate”), since who else could treat that particular form of human suffering as worthy of reply?  Few seem to have done the 10-second research to learn that, in reality, Robin is a happily married father of two.

I noticed the same strange phenomenon during the comment-171 affair: commentators on both left and right wanted to make me the poster child for “incels,” with a few offering me advice, many swearing they would’ve guessed it immediately from my photograph.  People apparently didn’t read just a few paragraphs into my story—to the part where, once I finally acquired some of the norms that mainstream culture refuses to tell people, I enjoyed a normal or even good dating life, eventually marrying a brilliant fellow theoretical computer scientist, with whom I started raising a rambunctious daughter (who’s now 5, and who’s been joined by our 1-year-old son).  If not for this happy ending, I too might have entertained my critics’ elaborate theories about my refusal to accept my biological inferiority, my simply having lost the genetic lottery (ability to do quantum computing research notwithstanding).  But what can one do faced with the facts?

For the record: I think that Robin should never, ever have made this comparison, and I wish he’d apologize for it now.  Had he asked my advice, I would’ve screamed “DON’T DO IT” at the top of my lungs.  I once contemplated such a comparison myself—and even though it was many years ago, in the depths of a terrifying relapse of the suicidal depression that had characterized much of my life, I still count it among my greatest regrets.  I hereby renounce and disown the comparison forever.  And I beg forgiveness from anyone who was hurt or offended by it—or for that matter, by anything else I ever said, on this blog or elsewhere.

Indeed, let me go further: if you were ever hurt or offended by anything I said, and if I can make partial restitution to you by taking some time to field your questions about quantum computing and information, or math, CS, and physics more generally, or academic career advice, or anything else where I’m said to know something, please shoot me an email.  I’m also open to donating to your favorite charity.

My view is this: the world in which a comparison between the sufferings of the romantically and the monetarily impoverished could increase normal people’s understanding of the former, is so different from our world as to be nearly unrecognizable.  To say that this comparison is outside the Overton window is a comic understatement: it’s outside the Overton galaxy.  Trying to have the conversation that Robin wanted to have on social media, is a little like trying to have a conversation about microaggressions in 1830s Alabama.  At first, your listeners will simply be confused—but their confusion will be highly unstable, like a Higgs boson, and will decay in about 10-22 seconds into righteous rage.

For experience shows that, if you even breathe a phrase like “the inequality of romantic and sexual fulfillment,” no one who isn’t weird in certain ways common in the hard sciences (e.g., being on the autism spectrum) will be able to parse you as saying anything other than that sex ought to be “redistributed” by the government in the same way that money is redistributed, which in turn suggests a dystopian horror scenario where women are treated like property, married against their will, and raped.  And it won’t help if you shout from the rooftops that you want nothing of this kind, oppose it as vehemently as your listeners do.  For, not knowing what else you could mean, the average person will continue to impose the nightmare scenario on anything you say, and will add evasiveness and dishonesty to the already severe charges against you.

Before going any further in this post, let me now say that any male who wants to call himself my ideological ally ought to agree to the following statement.

I hold the bodily autonomy of women—the principle that women are freely-willed agents rather than the chattel they were treated as for too much of human history; that they, not their fathers or husbands or anyone else, are the sole rulers of their bodies; and that they must never under any circumstances be touched without their consent—to be my Zeroth Commandment, the foundation-stone of my moral worldview, the starting point of every action I take and every thought I think.  This principle of female bodily autonomy, for me, deserves to be chiseled onto tablets of sapphire, placed in a golden ark adorned with winged cherubim sitting atop a pedestal inside the Holy of Holies in a temple on Mount Moriah.

This, or something close to it, is really what I believe.  And I advise any lonely young male nerd who might be reading this blog to commit to the Zeroth Commandment as well, and to the precepts of feminism more broadly.

To such a nerd, I say: yes, throughout your life you’ll encounter many men and women who will despise you for being different, in ways that you’re either powerless to change, or could change only at the cost of renouncing everything you are.  Yet, far from excusing any moral lapses on your part, this hatred simply means that you need to adhere to a higher moral standard than most people.  For whenever you stray even slightly from the path of righteousness, the people who detest nerds will leap excitedly, seeing irrefutable proof of all their prejudices.  Do not grant them that victory.  Do not create a Shanda fur die Normies.

I wish I believed in a God who could grant you some kind of eternal salvation, in return for adhering to a higher moral standard throughout your life, and getting in return at best grudging toleration, as well as lectures about your feminist failings by guys who’ve obeyed the Zeroth Commandment about a thousandth as scrupulously as you have.  As an atheist, though, the most I can offer you is that you can probably understand the proof of Cantor’s theorem, while most of those who despise you probably can’t.  And also: as impossible as it might seem right now, there are ways that even you can pursue the ordinary, non-intellectual kinds of happiness in life, and there will be many individuals along the way ready to help you: the ones who remember their humanity and forget their ideology.  I wish you the best.

Amid the many vitriolic responses to Robin—fanned, it must be admitted, by Robin’s own refusal to cede any ground to his critics, or to modulate his style or tone in the slightest—the one striking outlier was a New York Times essay by Ross Douthat.  This essay, which has itself now been widely panned, uses Robin as an example of how, in Douthat’s words, “[s]ometimes the extremists and radicals and weirdos see the world more clearly than the respectable and moderate and sane.  Douthat draws an interesting parallel between Robin and the leftist feminist philosopher Amia Srinivasan, who recently published a beautifully-written essay in the London Review of Books entitled Does anyone have the right to sex?  In analyzing that question, Srinivasan begins by discussing male “incels,” but then shifts her attention to far more sympathetic cases: women and men suffering severe physical or mental disabilities (and who, in some countries, can already hire sexual surrogates with government support); who were disfigured by accidents; who are treated as undesirable for racist reasons.  Let me quote from her conclusion:

The question, then, is how to dwell in the ambivalent place where we acknowledge that no one is obligated to desire anyone else, that no one has a right to be desired, but also that who is desired and who isn’t is a political question, a question usually answered by more general patterns of domination and exclusion … the radical self-love movements among black, fat and disabled women do ask us to treat our sexual preferences as less than perfectly fixed. ‘Black is beautiful’ and ‘Big is beautiful’ are not just slogans of empowerment, but proposals for a revaluation of our values … The question posed by radical self-love movements is not whether there is a right to sex (there isn’t), but whether there is a duty to transfigure, as best we can, our desires.

All over social media, there are howls of outrage that Douthat would dare to mention Srinivasan’s essay, which is wise and nuanced and humane, in the same breath as the gross, creepy, entitled rantings of Robin Hanson.  I would say: grant that Srinivasan and Hanson express themselves extremely differently, and also that Srinivasan is a trillion times better than Hanson at anticipating and managing her readers’ reactions.  Still, on the merits, is there any relevant difference between the two cases beyond: “undesirability” of the disabled, fat, and trans should be critically examined and interrogated, because those people are objects of progressive sympathy; whereas “undesirability” of nerdy white and Asian males should be taken as a brute fact or even celebrated, because those people are objects of progressive contempt?

To be fair, a Google search also turns up progressives who, dissenting from the above consensus, excoriate Srinivasan for her foray, however thoughtful, into taboo territory.  As best I can tell, the dissenters’ argument runs like so: as much as it might pain us, we must not show any compassion to women and men who are suicidally lonely and celibate by virtue of being severely disabled, disfigured, trans, or victims of racism.  For if we did, then consistency might eventually force us to show compassion to white male nerds as well.

Here’s the central point that I think Robin failed to understand: society, today, is not on board even with the minimal claim that the suicidal suffering of men left behind by the sexual revolution really exists—or, if it does, that it matters in the slightest or deserves any sympathy or acknowledgment whatsoever.  Indeed, the men in question pretty much need to be demonized as entitled losers and creeps, because if they weren’t, then sympathy for them—at least, for those among them who are friends, coworkers, children, siblings—might become hard to prevent.  In any event, it seems to me that until we as a society resolve the preliminary question, of whether to recognize a certain category of suffering as real, there’s no point even discussing how policy or culture might help to address the suffering, consistently with the Zeroth Commandment.

Seen in this light, Robin is a bit like the people who email me every week imagining they can prove P≠NP, yet who can’t even prove astronomically easier statements, even ones that are already known.  When trying to scale an intellectual Everest, you might as well start with the weakest statement that’s already unproven or non-obvious or controversial.

So where are we today?  Within the current Overton window, a perfectly appropriate response to suicidal loneliness and depression among the “privileged” (i.e., straight, able-bodied, well-educated white or Asian men) seems to be: “just kill yourselves already, you worthless cishet scum, and remove your garbage DNA from the gene pool.”  If you think I’m exaggerating, I beseech you to check for yourself on Twitter.  I predict you’ll find that and much worse, wildly upvoted, by people who probably go to sleep every night congratulating themselves for their progressivism, their egalitarianism, and—of course—their burning hatred for anything that smacks of eugenics.

A few days ago, Ellen Pao, the influential former CEO of Reddit, tweeted:

CEOs of big tech companies: You almost certainly have incels as employees. What are you going to do about it?

Thankfully, even many leftists reacted with horror to Pao’s profoundly illiberal question.  They wondered about the logistics she had in mind: does she want tech companies to spy on their (straight, male) employees’ sex lives, or lack thereof?  If any are discovered who are (1) celibate and (2) bitter at the universe about it, then will it be an adequate defense against firing if they’re also feminists, who condemn misogyny and violence and affirm the Zeroth Commandment?  Is it not enough that these men were permanently denied the third level of Maslow’s hierarchy of needs (the one right above physical safety); must they also be denied careers as a result?  And is this supposed to prevent their radicalization?

For me, the scariest part of Pao’s proposal is that, whatever in this field is on the leftmost fringe of the Overton window today, experience suggests we’ll find it smack in the center a decade from now.  So picture a future wherein, if you don’t support rounding up and firing your company’s romantically frustrated—i.e., the policy of “if you don’t get laid, you don’t get paid”—then that itself is a shockingly reactionary attitude, and grounds for your own dismissal.

Some people might defend Pao by pointing out that she was only asking a question, not proposing a specific policy.  But then, the same is true of Robin Hanson.

Why is it so politically difficult even to show empathy toward socially awkward, romantically challenged men—to say to them, “look, I don’t know what if anything can be done about your problem, but yeah, the sheer cosmic arbitrariness of it kind of sucks, and I sympathize with you”?  Why do enlightened progressives, if they do offer such words of comfort to their “incel” friends, seem to feel about it the same way Huck Finn did, at the pivotal moment in Western literature when he decides to help his friend Jim escape from slavery—i.e., not beaming with pride over his own moral courage, but ashamed of himself, and resigned that he’ll burn in hell for the sake of a mere personal friendship?

This is a puzzle, but I think I might know the answer.  We begin with the observation that virtually every news article, every thinkpiece, every blog post about “incels,” fronts contemptible mass murderers like Elliot Rodger and Alek Minassian, who sought bloody revenge on a world that failed to provide them the women to whom they felt entitled; as well as various Internet forums (many recently shut down) where this subhuman scum was celebrated by other scum.

The question is: why don’t people look at the broader picture, as they’ve learned to do in so many other cases?  In other words, why don’t they say:

• There really do exist extremist Muslims, who bomb schools and buses, or cheer and pass out candies when that happens, and who wish to put the entire world under Sharia on point of the sword.  Fortunately, the extremists are outnumbered by hundreds of millions of reasonable Muslims, with whom anyone, even a Zionist Jew like me, can have a friendly conversation in which we discuss our respective cultures’ grievances and how they might be addressed in a win-win manner.  (My conversations with Iranian friends sometimes end with us musing that, if only they made them Ayatollah and me Israeli Prime Minister, we could sign a peace accord next week, then go out for kebabs and babaganoush.)
• There really are extremist leftists—Marxist-Leninist-Maoist-whateverists—who smash store windows, kill people (or did, in the 60s), and won’t be satisfied by anything short of the total abolition of private property and the heads of the capitalists lining the streets on pikes.  But they’re vastly outnumbered by the moderate progressives, like me, who are less about proletarian revolution than they are about universal healthcare, federal investment in science and technology, a carbon tax, separation of church and state, and stronger protection of national parks.
• In exactly the same way, there are “incel extremists,” like Rodger or Minassian, spiteful losers who go on killing sprees because society didn’t give them the sex they were “owed.”  But they’re outnumbered by tens of millions of decent, peaceful people who could reasonably be called “incels”—those who desperately want romantic relationships but are unable to achieve them, because of extreme shyness, poor social skills, tics, autism-spectrum traits, lack of conventional attractiveness, bullying, childhood traumas, etc.—yet who’d never hurt a fly.  These moderates need not be “losers” in all aspects of life: many have fulfilling careers and volunteer and give to charity and love their nieces and nephews, some are world-renowned scientists and writers.  For many of the moderates, it might be true that recent cultural shifts exacerbated their problems; that an unlucky genetic dice-roll “optimized” them for a world that no longer exists.  These people deserve the sympathy and support of the more fortunate among us; they constitute a political bloc entitled to advocate for its interests, as other blocs do; and all decent people should care about how we might help them, consistently with the Zeroth Commandment.

The puzzle, again, is: why doesn’t anyone say this?

And I think the answer is simply that no one ever hears from “moderate incels.”  And the reason, in turn, becomes obvious the instant you think about it.  Would you volunteer to march at the front of the Lifelong Celibacy Awareness Parade?  Or to be identified by name as the Vice President of the League of Peaceful and Moderate Incels?  Would you accept such a social death warrant?  It takes an individual with extraordinary moral courage, such as Scott Alexander, even to write anything whatsoever about this issue that tries to understand or help the sufferers rather than condemn them.  For this reason—i.e., purely, 100% a selection effect, nothing more—the only times the wider world ever hears anything about “incels” is when some despicable lunatic like Rodger or Minassian snaps and murders the innocent.  You might call this the worst PR problem in the history of the world.

So what’s the solution?  While I’m not a Christian, I find that Jesus’ prescription of universal compassion has a great deal to recommend it here—applied liberally, like suntan lotion, to every corner of the bitter “SJW vs. incel” online debate.

The usual stereotype of nerds is that, while we might be good at memorizing facts or proving theorems or coding up filesystems, we’re horrendously deficient in empathy and compassion, constantly wanting to reduce human emotions to numbers in spreadsheets or something.  As I’ve remarked elsewhere, I’ve scarcely encountered any stereotype that rings falser to my experience.  In my younger, depressed phase, when I was metaphorically hanging on to life by my fingernails, it was nerds and social misfits who offered me their hands up, while many of the “normal, well-adjusted, socially competent” people gleefully stepped on my fingers.

But my aspiration is not merely that we nerds can do just as well at compassion as those who hate us.  Rather, I hope we can do better.  This isn’t actually such an ambitious goal.  To achieve it, all we need to do is show universal, Jesus-style compassion, to politically favored and disfavored groups alike.

To me that means: compassion for the woman facing sexual harassment, or simply quizzical glances that wonder what she thinks she’s doing pursuing a PhD in physics.  Compassion for the cancer patient, for the bereaved parent, for the victim of famine.  Compassion for the undocumented immigrant facing deportation.  Compassion for the LGBT man or woman dealing with self-doubts, ridicule, and abuse.  Compassion for the nerdy male facing suicidal depression because modern dating norms, combined with his own shyness and fear of rule-breaking, have left him unable to pursue romance or love.  Compassion for the woman who feels like an ugly, overweight, unlovable freak who no one will ask on dates.  Compassion for the African-American victim of police brutality.  Compassion even for the pedophile who’d sooner kill himself than hurt a child, but who’s been given no support for curing or managing his condition.  This is what I advocate.  This is my platform.

If I ever decided to believe the portrait of me painted by Arthur Chu, or the other anti-Aaronson Twitter warriors, then I hope I’d have the moral courage to complete their unstated modus ponens, by quietly swallowing a bottle of sleeping pills.  After all, Chu’s vision of the ideal future seems to have no more room for me in it than Eichmann’s did.  But the paradoxical corollary is that, every time I remind myself why I think Chu is wrong, it feels like a splendorous affirmation of life itself.  I affirm my love for my wife and children and parents and brother, my bonds with my friends around the world, the thrill of tackling a new research problem and sharing my progress with colleagues, the joy of mentoring students of every background and religion and gender identity, the smell of fresh-baked soft pretzels and the beauty of the full moon over the Mediterranean.  If I had to find pearls in manure, I’d say: with their every attack, the people who hate me give me a brand-new opportunity to choose life over death, and better yet to choose compassion over hatred—even compassion for the haters themselves.

(Far be it from me to psychoanalyze him, as he constantly does to me, but Chu’s unremitting viciousness doesn’t strike me as coming from a place of any great happiness with his life.  So I say: may even Mr. Chu find whatever he’s looking for.  And while his utopia might have no place for me, I’m determined that mine should have a place for him—even if it’s just playing Jeopardy! and jumping around to find the Daily Doubles.)

It’s a commonplace that sometimes, the only way you can get a transformative emotional experience—like awe at watching the first humans walk on the moon, or joy at reuniting with a loved one after a transatlantic flight—is on top of a mountain of coldly rational engineering and planning.  But the current Robin Hanson affair reminds us that the converse is true as well.  I.e., the only way we can have the sort of austere, logical, norm-flouting conversations about the social world that Robin has been seeking to have for decades, without the whole thing exploding in thermonuclear anger, is on top of a mountain of empathy and compassion.  So let’s start building that mountain.

Endnotes. Already, in my mind’s eye, I can see the Twitter warriors copying and sharing whichever sentence of this post angered them the most, using it as proof that I’m some lunatic who should never be listened to about anything. I’m practically on my hands and knees begging you here: show that my fears are unjustified.  Respond, by all means, but respond to the entirety of what I had to say.

I welcome comments, so long as they’re written in a spirit of kindness and mutual respect. But because writing this post was emotionally and spiritually draining for me–not to mention draining in, you know, time—I hope readers won’t mind if I spend a day or two away, with my wife and kids and my research, before participating in the comments myself.

Update (May 7). Numerous commenters have successfully convinced me that the word “incel,” though it literally just means “involuntary celibate,” and was in fact coined by a woman to describe her own experience, has been permanently disgraced by its association with violent misogynists and their online fan clubs.  It will never again regain its original meaning, any more than “Adolf” will ever again be just a name; nor will one be able to discuss “moderate incels” as distinct from the extremist kind.  People of conscience will need to be extremely vigilant against motte-and-bailey tactics—wherein society’s opinion-makers will express their desire for all “incels” to be silenced or fired or removed from the gene pool or whatever, obviously having in mind all romantically frustrated male nerds (all of whom they despise), and will fall back when challenged (and only when challenged) on the defense that they only meant the violence-loving misogynists.  For those of us motivated by compassion rather than hatred, though, we need another word.  I suggest the older term “love-shy,” coined by Brian Gilmartin in his book on the subject.

Meanwhile, be sure to check out this comment by “Sniffnoy” for many insightful criticisms of this post, most of which I endorse.

Review of Bryan Caplan’s The Case Against Education

April 26th, 2018

If ever a book existed that I’d judge harshly by its cover—and for which nothing inside could possibly make me reverse my harsh judgment—Bryan Caplan’s The Case Against Education would seem like it.  The title is not a gimmick; the book’s argument is exactly what it says on the tin.  Caplan—an economist at George Mason University, home of perhaps the most notoriously libertarian economics department on the planet—holds that most of the benefit of education to students (he estimates around 80%, but certainly more than half) is about signalling the students’ preexisting abilities, rather than teaching or improving the students in any way.  He includes the entire educational spectrum in his indictment, from elementary school all the way through college and graduate programs.  He does have a soft spot for education that can be shown empirically to improve worker productivity, such as technical and vocational training and apprenticeships.  In other words, precisely the kind of education that many readers of this blog may have spent their lives trying to avoid.

I’ve spent almost my whole conscious existence in academia, as a student and postdoc and then as a computer science professor.  CS is spared the full wrath that Caplan unleashes on majors like English and history: it does, after all, impart some undeniable real-world skills.  Alas, I’m not one of the CS professors who teaches anything obviously useful, like how to code or manage a project.  When I teach undergrads headed for industry, my only role is to help them understand concepts that they probably won’t need in their day jobs, such as which problems are impossible or intractable for today’s computers; among those, which might be efficiently solved by quantum computers decades in the future; and which parts of our understanding of all this can be mathematically proven.

Granted, my teaching evaluations have been [clears throat] consistently excellent.  And the courses I teach aren’t major requirements, so the students come—presumably?—because they actually want to know the stuff.  And my former students who went into industry have emailed me, or cornered me, to tell me how much my courses helped them with their careers.  OK, but how?  Often, it’s something about my class having helped them land their dream job, by impressing the recruiters with their depth of theoretical understanding.  As we’ll see, this is an “application” that would make Caplan smile knowingly.

If Caplan were to get his way, the world I love would be decimated.  Indeed, Caplan muses toward the end of the book that the world he loves would be decimated too: in a world where educational investment no longer exceeded what was economically rational, he might no longer get to sit around with other economics professors discussing what he finds interesting.  But he consoles himself with the thought that decisionmakers won’t listen to him anyway, so it won’t happen.

It’s tempting to reply to Caplan: “now now, your pessimism about anybody heeding your message seems unwarranted.  Have anti-intellectual zealots not just taken control of the United States, with an explicit platform of sticking it to the educated elites, and restoring the primacy of lower-education jobs like coal mining, no matter the long-term costs to the economy or the planet?  So cheer up, they might listen to you!”

Indeed, given the current stakes, one might simply say: Caplan has set himself against the values that are the incredibly fragile preconditions for all academic debate—even, ironically, debate about the value of academia, like the one we’re now having.  So if we want such debate to continue, then we have no choice but to treat Caplan as an enemy, and frame the discussion around how best to frustrate his goals.

In response to an excerpt of Caplan’s book in The Atlantic, my friend Sean Carroll tweeted:

It makes me deeply sad that a tenured university professor could write something like this about higher education.  There is more to learning than the labor market.

Why should anyone with my basic values, or Sean’s, give Caplan’s thesis any further consideration?  As far as I can tell, there are only two reasons: (1) common sense, and (2) the data.

And: if the value of education comes from what it teaches you, how do we explain the fact that students forget almost everything so soon after the final exam, as attested by both experience and the data?  Why are employers satisfied with a years-ago degree; why don’t they test applicants to see how much understanding they’ve retained?

Or if education isn’t about any of the specific facts being imparted, but about “learning how to learn” or “learning how to think creatively”—then how is it that studies find academic coursework has so little effect on students’ general learning and reasoning abilities either?  That, when there is an improvement in reasoning ability, it’s tightly concentrated on the subject matter of the course, and even then it quickly fades away after the course is over?

More broadly, if the value of mass education derives from making people more educated, how do we explain the fact that high-school and college graduates, most of them, remain so abysmally ignorant?  After 12-16 years in something called “school,” large percentages of Americans still don’t know that the earth orbits the sun; believe that heavier objects fall faster than lighter ones and that only genetically modified organisms contain genes; and can’t locate the US or China on a map.  Are we really to believe, asks Caplan, that these apparent dunces have nevertheless become “deeper thinkers” by virtue of their schooling, in some holistic, impossible-to-measure way?  Or that they would’ve been even more ignorant without school?  But how much more ignorant can you be?  They could be illiterate, yes: Caplan grants the utility of teaching reading, writing, and arithmetic.  But how much beyond the three R’s (if those) do typical students retain, let alone use?

Caplan also poses the usual questions: if you’re not a scientist, engineer, or academic (or even if you are), how much of your undergraduate education do you use in your day job?  How well did the course content match what, in retrospect, you feel someone starting your job really needs to know?  Could your professors do your job?  If not, then how were they able to teach you to do it better?

Caplan acknowledges the existence of inspiring teachers who transform their students’ lives, in ways that need not be reflected in their paychecks: he mentions Robin Williams’ character in The Dead Poets’ Society.  But he asks: how many such teachers did you have?  If the Robin Williamses are vastly outnumbered by the drudges, then wouldn’t it make more sense for students to stream the former directly into their homes via the Internet—as they can now do for free?

OK, but if school teaches so little, then how do we explain the fact that, at least for those students who are actually able to complete good degrees, research confirms that (on average) having gone to school really does pay, exactly as advertised?  Employers do pay more for a college graduate—yes, even an English or art history major—than for a dropout.  More generally, starting salary rises monotonically with level of education completed.  Employers aren’t known for a self-sacrificing eagerness to overpay.  Are they systematically mistaken about the value of school?

Synthesizing decades of work by other economists, Caplan defends the view that the main economic function of school is to give students a way to signal their preexisting qualities, ones that correlate with being competent workers in a modern economy.  I.e., that school is tacitly a huge system for winnowing and certifying young people, which also fulfills various subsidiary functions, like keeping said young people off the street, socializing them, maybe occasionally even teaching them something.  Caplan holds that, judged as a certification system, school actually works—well enough to justify graduates’ higher starting salaries, without needing to postulate any altruistic conspiracy on the part of employers.

For Caplan, a smoking gun for the signaling theory is the huge salary premium of an actual degree, compared to the relatively tiny premium for each additional year of schooling other than the degree year—even when we hold everything else constant, like the students’ academic performance.  In Caplan’s view, this “sheepskin effect” even lets us quantitatively estimate how much of the salary premium on education reflects actual student learning, as opposed to the students signaling their suitability to be hired in a socially approved way (namely, with a diploma or “sheepskin”).

Caplan knows that the signaling story raises an immediate problem: namely, if employers just want the most capable workers, then knowing everything above, why don’t they eagerly recruit teenagers who score highly on the SAT or IQ tests?  (Or why don’t they make job offers to high-school seniors with Harvard acceptance letters, skipping the part where the seniors have to actually go to Harvard?)

Some people think the answer is that employers fear getting sued: in the 1971 Griggs vs. Duke Power case, the US Supreme Court placed restrictions on the use of intelligence tests in hiring, because of disparate impact on minorities.  Caplan, however, rejects this explanation, pointing out that it would be child’s-play for employers to design interview processes that functioned as proxy IQ tests, were that what the employers wanted.

Caplan’s theory is instead that employers don’t value only intelligence.  Instead, they care about the conjunction of intelligence with two other traits: conscientiousness and conformity.  They want smart workers who will also show up on time, reliably turn in the work they’re supposed to, and jump through whatever hoops authorities put in front of them.  The main purpose of school, over and above certifying intelligence, is to serve as a hugely costly and time-consuming—and therefore reliable—signal that the graduates are indeed conscientious conformists.  The sheer game-theoretic wastefulness of the whole enterprise rivals the peacock’s tail or the bowerbird’s ornate bower.

But if true, this raises yet another question.  In the signaling story, graduating students (and their parents) are happy that the students’ degrees land them good jobs.  Employers are happy that the education system supplies them with valuable workers, pre-screened for intelligence, conscientiousness, and conformity.  Even professors are happy that they get paid to do research and teach about topics that interest them, however irrelevant those topics might be to the workplace.  So if so many people are happy, who cares if, from an economic standpoint, it’s all a big signaling charade, with very little learning taking place?

For Caplan, the problem is this: because we’ve all labored under the mistaken theory that education imparts vital skills for a modern economy, there are trillions of dollars of government funding for every level of education—and that, in turn, removes the only obstacle to a credentialing arms race.  The equilbrium keeps moving over the decades, with more and more years of mostly-pointless schooling required to prove the same level of conscientiousness and conformity as before.  Jobs that used to require only a high-school diploma now require a bachelors; jobs that used to require only a bachelors now require a masters, and so on—despite the fact that the jobs themselves don’t seem to have changed appreciably.

For Caplan, a thoroughgoing libertarian, the solution is as obvious as it is radical: abolish government funding for education.  (Yes, he explicitly advocates a complete “separation of school and state.”)  Or if some state role in education must be retained, then let it concentrate on the three R’s and on practical job skills.  But what should teenagers do, if we’re no longer urging them to finish high school?  Apparently worried that he hasn’t yet outraged liberals enough, Caplan helpfully suggests that we relax the laws around child labor.  After all, he says, if we’ve decided anyway that teenagers who aren’t academically inclined should suffer through years of drudgery, then instead of warming a classroom seat, why shouldn’t they apprentice themselves to a carpenter or a roofer?  That way they could contribute to the economy, and gain the independence from their parents that most of them covet, and learn skills that they’d be much more likely to remember and use than the dissection of owl pellets.  Even if working a real job involved drudgery, at least it wouldn’t be as pointless as the drudgery of school.

Given his conclusions, and the way he arrives at them, Caplan realizes that he’ll come across to many as a cartoon stereotype of a narrow-minded economist, who “knows the price of everything but the value of nothing.”  So he includes some final chapters in which, setting aside the charts and graphs, he explains how he really feels about education.  This is the context for what I found to be the most striking passages in the book:

I am an economist and a cynic, but I’m not a typical cynical economist.  I’m a cynical idealist.  I embrace the ideal of transformative education.  I believe wholeheardedly in the life of the mind.  What I’m cynical about is people … I don’t hate education.  Rather I love education too much to accept our Orwellian substitute.  What’s Orwellian about the status quo?  Most fundamentally, the idea of compulsory enlightenment … Many idealists object that the Internet provides enlightenment only for those who seek it.  They’re right, but petulant to ask for more.  Enlightenment is a state of mind, not a skill—and state of mind, unlike skill, is easily faked.  When schools require enlightenment, students predictably respond by feigning interest in ideas and culture, giving educators a false sense of accomplishment. (p. 259-261)

OK, but if one embraces the ideal, then rather than dynamiting the education system, why not work to improve it?  According to Caplan, the answer is that we don’t know whether it’s even possible to build a mass education system that actually works (by his lights).  He says that, if we discover that we’re wasting trillions of dollars on some sector, the first order of business is simply to stop the waste.  Only later should we entertain arguments about whether we should restart the spending in some new, better way, and we shouldn’t presuppose that the sector in question will win out over others.

Above, I took pains to set out Caplan’s argument as faithfully as I could, before trying to pass judgment on it.  At some point in a review, though, the hour of judgment arrives.

I think Caplan gets many things right—even unpopular things that are difficult for academics to admit.  It’s true that a large fraction of what passes for education doesn’t deserve the name—even if, as a practical matter, it’s far from obvious how to cut that fraction without also destroying what’s precious and irreplaceable.  He’s right that there’s no sense in badgering weak students to go to college if those students are just going to struggle and drop out and then be saddled with debt.  He’s right that we should support vocational education and other non-traditional options to serve the needs of all students.  Nor am I scandalized by the thought of teenagers apprenticing themselves to craftspeople, learning skills that they’ll actually value while gaining independence and starting to contribute to society.  This, it seems to me, is a system that worked for most of human history, and it would have to fail pretty badly in order to do worse than, let’s say, the average American high school.  And in the wake of the disastrous political upheavals of the last few years, I guess the entire world now knows that, when people complain that the economy isn’t working well enough for non-college-graduates, we “technocratic elites” had better have a better answer ready than “well then go to college, like we did.”

Yes, probably the state has a compelling interest in trying to make sure nearly everyone is literate, and probably most 8-year-olds have no clue what’s best for themselves.  But at least from adolescence onward, I think that enormous deference ought to be given to students’ choices.  The idea that “free will” (in the practical rather than metaphysical sense) descends on us like a halo on our 18th birthdays, having been absent beforehand, is an obvious fiction.  And we all know it’s fiction—but it strikes me as often a destructive fiction, when law and tradition force us to pretend that we believe it.

Some of Caplan’s ideas dovetail with the thoughts I’ve had myself since childhood on how to make the school experience less horrible—though I never framed my own thoughts as “against education.”  Make middle and high schools more like universities, with freedom of movement and a wide range of offerings for students to choose from.  Abolish hall passes and detentions for lateness: just like in college, the teacher is offering a resource to students, not imprisoning them in a dungeon.  Don’t segregate by age; just offer a course or activity, and let kids of any age who are interested show up.  And let kids learn at their own pace.  Don’t force them to learn things they aren’t ready for: let them love Shakespeare because they came to him out of interest, rather than loathing him because he was forced down their throats.  Never, ever try to prevent kids from learning material they are ready for: instead of telling an 11-year-old teaching herself calculus to go back to long division until she’s the right age (does that happen? ask how I know…), say: “OK hotshot, so you can differentiate a few functions, but can you handle these here books on linear algebra and group theory, like Terry Tao could have when he was your age?”

Caplan mentions preschool as the one part of the educational system that strikes him as least broken.  Not because it has any long-term effects on kids’ mental development (it might not), just because the tots enjoy it at the time.  They get introduced to a wide range of fun activities.  They’re given ample free time, whether for playing with friends or for building or drawing by themselves.  They’re usually happy to be dropped off.  And we could add: no one normally minds if parents drop their kids off late, or pick them up early, or take them out for a few days.  The preschool is just a resource for the kids’ benefit, not a never-ending conformity test.  As a father who’s now seen his daughter in three preschools, this matches my experience.

Having said all this, I’m not sure I want to live in the world of Caplan’s “complete separation of school and state.”  And I’m not using “I’m not sure” only as a euphemism for “I don’t.”  Caplan is proposing a radical change that would take civilization into uncharted territory: as he himself notes, there’s not a single advanced country on earth that’s done what he advocates.  The trend has everywhere been in the opposite direction, to invest more in education as countries get richer and more technology-based.  Where there have been massive cutbacks to education, the causes have usually been things like famine or war.

So I have the same skepticism of Caplan’s project that I’d have (ironically) of Bolshevism or any other revolutionary project.  I say to him: don’t just persuade me, show me.  Show me a case where this has worked.  In the social world, unlike the mathematical world, I put little stock in long chains of reasoning unchecked by experience.

Caplan explicitly invites his readers to test his assertions against their own lives.  When I do so, I come back with a mixed verdict.  Before college, as you may have gathered, I find much to be said for Caplan’s thesis that the majority of school is makework, the main purposes of which are to keep the students out of trouble and on the premises, and to certify their conscientiousness and conformity.  There are inspiring teachers here and there, but they’re usually swimming against the tide.  I still feel lucky that I was able to finagle my way out by age 15, and enter Clarkson University and then Cornell with only a G.E.D.

In undergrad, on the other hand, and later in grad school at Berkeley, my experience was nothing like what Caplan describes.  The professors were actual experts: people who I looked up to or even idolized.  I wanted to learn what they wanted to teach.  (And if that ever wasn’t the case, I could switch to a different class, excepting some major requirements.)  But was it useful?

As I look back, many of my math and CS classes were grueling bootcamps on how to prove theorems, how to design algorithms, how to code.  Most of the learning took place not in the classroom but alone, in my dorm, as I struggled with the assignments—having signed up for the most advanced classes that would allow me in, and thereby left myself no escape except to prove to the professor that I belonged there.  In principle, perhaps, I could have learned the material on my own, but in reality I wouldn’t have.  I don’t still use all of the specific tools I acquired, though I do still use a great many of them, from the Gram-Schmidt procedure to Gaussian integrals to finding my way around a finite group or field.  Even if I didn’t use any of the tools, though, this gauntlet is what upgraded me from another math-competition punk to someone who could actually write research papers with long proofs.  For better or worse, it made me what I am.

Just as useful as the math and CS courses were the writing seminars—places where I had to write, and where my every word got critiqued by the professor and my fellow students, so I had to do a passable job.  Again: intensive forced practice in what I now do every day.  And the fact that it was forced was now fine, because, like some leather-bound masochist, I’d asked to be forced.

On hearing my story, Caplan would be unfazed.  Of course college is immensely useful, he’d say … for those who go on to become professors, like me or him.  He “merely” questions the value of higher education for almost everyone else.

OK, but if professors are at least good at producing more people like themselves, able to teach and do research, isn’t that something, a base we can build on that isn’t all about signaling?  And more pointedly: if this system is how the basic research enterprise perpetuates itself, then shouldn’t we be really damned careful with it, lest we slaughter the golden goose?

Except that Caplan is skeptical of the entire enterprise of basic research.  He writes:

Researchers who specifically test whether education accelerates progress have little to show for their efforts.  One could reply that, given all the flaws of long-run macroeconomic data, we should ignore academic research in favor of common sense.  But what does common sense really say? … True, ivory tower self-indulgence occasionally revolutionizes an industry.  Yet common sense insists the best way to discover useful ideas is to search for useful ideas—not to search for whatever fascinates you and pray it turns out to be useful (p. 175).

I don’t know if common sense insists that, but if it does, then I feel on firm ground to say that common sense is woefully inadequate.  It’s easy to look at most basic research, and say: this will probably never be useful for anything.  But then if you survey the inventions that did change the world over the past century—the transistor, the laser, the Web, Google—you find that almost none would have happened without what Caplan calls “ivory tower self-indulgence.”  What didn’t come directly from universities came from entities (Bell Labs, DARPA, CERN) that wouldn’t have been thinkable without universities, and that themselves were largely freed from short-term market pressures by governments, like universities are.

Caplan’s skepticism of basic research reminded me of a comment in Nick Bostrom’s book Superintelligence:

A colleague of mine likes to point out that a Fields Medal (the highest honor in mathematics) indicates two things about the recipient: that he was capable of accomplishing something important, and that he didn’t.  Though harsh, the remark hints at a truth. (p. 314)

I work in theoretical computer science: a field that doesn’t itself win Fields Medals (at least not yet), but that has occasions to use parts of math that have won Fields Medals.  Of course, the stuff we use cutting-edge math for might itself be dismissed as “ivory tower self-indulgence.”  Except then the cryptographers building the successors to Bitcoin, or the big-data or machine-learning people, turn out to want the stuff we were talking about at conferences 15 years ago—and we discover to our surprise that, just as the mathematicians gave us a higher platform to stand on, so we seem to have built a higher platform for the practitioners.  The long road from Hilbert to Gödel to Turing and von Neumann to Eckert and Mauchly to Gates and Jobs is still open for traffic today.

Yes, there’s plenty of math that strikes even me as boutique scholasticism: a way to signal the brilliance of the people doing it, by solving problems that require years just to understand their statements, and whose “motivations” are about 5,000 steps removed from anything Caplan or Bostrom would recognize as motivation.  But where I part ways is that there’s also math that looked to me like boutique scholasticism, until Greg Kuperberg or Ketan Mulmuley or someone else finally managed to explain it to me, and I said: “ah, so that’s why Mumford or Connes or Witten cared so much about this.  It seems … almost like an ordinary applied engineering question, albeit one from the year 2130 or something, being impatiently studied by people a few moves ahead of everyone else in humanity’s chess game against reality.  It will be pretty sweet once the rest of the world catches up to this.”

I have a more prosaic worry about Caplan’s program.  If the world he advocates were actually brought into being, I suspect the people responsible wouldn’t be nerdy economics professors like himself, who have principled objections to “forced enlightenment” and to signalling charades, yet still maintain warm fuzzies for the ideals of learning.  Rather, the “reformers” would be more on the model of, say, Steve Bannon or Scott Pruitt or Alex Jones: people who’d gleefully take a torch to the universities, fortresses of the despised intellectual elite, not in the conviction that this wouldn’t plunge humanity back into the Dark Ages, but in the hope that it would.

When the US Congress was debating whether to cancel the Superconducting Supercollider, a few condensed-matter physicists famously testified against the project.  They thought that $10-$20 billion for a single experiment was excessive, and that they could provide way more societal value with that kind of money were it reallocated to them.  We all know what happened: the SSC was cancelled, and of the money that was freed up, 0%—absolutely none of it—went to any of the other research favored by the SSC’s opponents.

If Caplan were to get his way, I fear that the story would be similar.  Caplan talks about all the other priorities—from feeding the world’s poor to curing diseases to fixing crumbling infrastructure—that could be funded using the trillions currently wasted on runaway credential signaling.  But in any future I can plausibly imagine where the government actually axes education, the savings go to things like enriching the leaders’ cronies and launching vanity wars.

My preferences for American politics have two tiers.  In the first tier, I simply want the Democrats to vanquish the Republicans, in every office from president down to dogcatcher, in order to prevent further spiraling into nihilistic quasi-fascism, and to restore the baseline non-horribleness that we know is possible for rich liberal democracies.  Then, in the second tier, I want the libertarians and rationalists and nerdy economists and Slate Star Codex readers to be able to experiment—that’s a key word here—with whether they can use futarchy and prediction markets and pricing-in-lieu-of-regulation and other nifty ideas to improve dramatically over the baseline liberal order.  I don’t expect that I’ll ever get what I want; I’ll be extremely lucky even to get the first half of it.  But I find that my desires regarding Caplan’s program fit into the same mold.  First and foremost, save education from those who’d destroy it because they hate the life of the mind.  Then and only then, let people experiment with taking a surgical scalpel to education, removing from it the tumor of forced enlightenment, because they love the life of the mind.