## Archive for April, 2018

### Review of Bryan Caplan’s The Case Against Education

Thursday, 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.

### Summer of the Shark

Thursday, April 19th, 2018

Sometimes a single word or phrase is enough to expand your mental toolkit across almost every subject.  “Averaging argument.”  “Motte and bailey.”  “Empirically indistinguishable.”  “Overfitting.”  Yesterday I learned another such phrase: “Summer of the Shark.”

This, apparently, was the summer of 2001, when lacking more exciting news, the media gave massive coverage to every single shark attack it could find, creating the widespread impression of an epidemic—albeit, one that everyone forgot about after 9/11.  In reality, depending on what you compare it to, the rate of shark attacks was either normal or unusually low in the summer of 2001.  As far as I can tell, the situation is that the absolute number of shark attacks has been increasing over the decades, but the increase is entirely attributable to human population growth (and to way more surfers and scuba divers).  The risk per person, always minuscule (cows apparently kill five times more people), appears to have been going down.  This might or might not be related to the fact that shark populations are precipitously declining all over the world, due mostly to overfishing and finning, but also the destruction of habitat.

There’s a tendency—I notice it in myself—to say, “fine, news outlets have overhyped this trend; that’s what they do.  But still, there must be something going on, since otherwise you wouldn’t see everyone talking about it.”

The point of the phrase “Summer of the Shark” is to remind yourself that a “trend” can be, and often is, entirely a product of people energetically looking for a certain thing, even while the actual rate of the thing is unremarkable, abnormally low, or declining.  Of course this has been a favorite theme of Steven Pinker, but I don’t know if even reading his recent books, Better Angels and Enlightenment Now, fully brought home the problem’s pervasiveness for me.  If a self-sustaining hype bubble can form even over something as relatively easy to measure as the number of shark attacks, imagine how common it must be with more nebulous social phenomena.

Without passing judgment—I’m unsure about many of them myself—how many of the following have you figured, based on the news or your Facebook or Twitter feeds, are probably some sort of epidemic?

• Crime by illegal immigrants
• Fraudulent voting by non-citizens
• SJWs silencing free speech on campus
• Unemployment in heartland America
• Outrageous treatment of customers by airlines
• Mass school shootings
• Sexism in Silicon Valley
• Racism at Starbucks

Now be honest: for how many of these do you have any real idea whether the problem is anomalously frequent relative to its historical rate, or to the analogous problems in other sectors of society?  How many seem to be epidemics that require special explanations (“the dysfunctional culture of X”), but only because millions of people started worrying about these particular problems and discussing them—in many cases, thankfully so?  How many seem to be epidemics, but only because people can now record outrageous instances with their smartphones, then make them viral on social media?

Needless to say, the discovery that a problem is no worse in domain X than it is in Y, or is better, doesn’t mean we shouldn’t fight hard to solve it in X—especially if X happens to be our business.  Set thy own house in order.  But it does mean that, if we see X but not Y attacked for its deeply entrenched, screwed-up culture, a culture that lets these things happen over and over, then we’re seeing a mistake at best, and the workings of prejudice at worst.

I’m not saying anything the slightest bit original here.  But my personal interest is less in the “Summer of the Shark” phenomenon itself than in its psychology.  Somehow, we need to figure out a trick to move this cognitive error from the periphery of consciousness to center stage.  I mustn’t treat it as just a 10% correction: something to acknowledge intellectually, before I go on to share a rage-inducing headline on Facebook anyway, once I’ve hit on a suitable reason why my initial feelings of anger were basically justified after all.  Sometimes it’s a 100% correction.  I’ve been guilty, I’m sure, of helping to spread SotS-type narratives.  And I’ve laughed when SotS narratives were uncritically wielded by others, for example in The Onion.  I should do better.

I can’t resist sharing one of history’s most famous Jewish jokes, with apologies to those who know it.  In the shtetl, a horrible rumor spreads: a Jewish man raped and murdered a beautiful little Christian girl in the forest.  Terrified, the Jews gather in the synagogue and debate what to do.  They know that the Cossacks won’t ask: “OK, but before we do anything rash, what’s the rate of Jewish perpetration of this sort of crime?  How does it compare to the Gentile rate, after normalizing by the populations’ sizes?  Also, what about Jewish victims of Gentile crimes?  Is the presence of Jews causally related to more of our children being murdered than would otherwise be?”  Instead, a mob will simply slaughter every Jew it can find.  But then, just when it seems all is lost, the rabbi runs into the synagogue and jubilantly declares: “wonderful news, everyone!  It turns out the murdered girl was Jewish!”

And now I should end this post, before it jumps the shark.

Update: This post by Scott Alexander, which I’d somehow forgotten about, makes exactly the same point, but better and more memorably. Oh well, one could do worse than to serve as a Cliff Notes and link farm for Slate Star Codex.

### How to upper-bound the probability of something bad

Friday, April 13th, 2018

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

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

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

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

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

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

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

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

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

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

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

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

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

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

### Amazing progress on longstanding open problems

Wednesday, April 11th, 2018

For those who haven’t seen it:

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

Huge congratulations to Aubrey and Urmila for their achievements!

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

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

### Two announcements

Saturday, April 7th, 2018

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

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