## Archive for the ‘Adventures in Meatspace’ Category

### NP-complete Problems and Physics: A 2019 View

Sunday, June 2nd, 2019

If I want to get back to blogging on a regular basis, given the negative amount of time that I now have for such things, I’ll need to get better at dispensing with pun-filled titles, jokey opening statements, etc. etc., and resigning myself to a less witty, more workmanlike blog.

So in that spirit: a few weeks ago I gave a talk at the Fields Institute in Toronto, at a symposium to celebrate Stephen Cook and the 50th anniversary (or actually more like 48th anniversary) of the discovery of NP-completeness. Thanks so much to the organizers for making this symposium happen.

You can watch the video of my talk here (or read the PowerPoint slides here). The talk, on whether NP-complete problems can be efficiently solved in the physical universe, covers much the same ground as my 2005 survey article on the same theme (not to mention dozens of earlier talks), but this is an updated version and I’m happier with it than I was with most past iterations.

As I explain at the beginning of the talk, I wasn’t going to fly to Toronto at all, due to severe teaching and family constraints—but my wife Dana uncharacteristically urged me to go (“don’t worry, I’ll watch the kids!”). Why? Because in her view, it was the risks that Steve Cook took 50 years ago, as an untenured assistant professor at Berkeley, that gave birth to the field of computational complexity that Dana and I both now work in.

Anyway, be sure to check out the other talks as well—they’re by an assortment of random nobodies like Richard Karp, Avi Wigderson, Leslie Valiant, Michael Sipser, Alexander Razborov, Cynthia Dwork, and Jack Edmonds. I found the talk by Edmonds particularly eye-opening: he explains how he thought about (the objects that we now call) P and NP∩coNP when he first defined them in the early 60s, and how it was similar to and different from the way we think about them today.

Another memorable moment came when Edmonds interrupted Sipser’s talk—about the history of P vs. NP—to deliver a booming diatribe about how what really matters is not mathematical proof, but just how quickly you can solve problems in the real world. Edmonds added that, from a practical standpoint, P≠NP is “true today but might become false in the future.” In response, Sipser asked “what does a mathematician like me care about the real world?,” to roars of approval from the audience. I might’ve picked a different tack—about how for every practical person I meet for whom it’s blindingly obvious that “in real life, P≠NP,” I meet another for whom it’s equally obvious that “in real life, P=NP” (for all the usual reasons: because SAT solvers work so well in practice, because physical systems so easily relax as their ground states, etc). No wonder it took 25+ years of smart people thinking about operations research and combinatorial optimization before the P vs. NP question was even explicitly posed.

Unrelated Announcement: The Texas Advanced Computing Center (TACC), a leading supercomputing facility in North Austin that’s part of the University of Texas, is seeking to hire a Research Scientist focused on quantum computing. Such a person would be a full participant in our Quantum Information Center at UT Austin, with plenty of opportunities for collaboration. Check out their posting!

### “Quantum Computing and the Meaning of Life”

Wednesday, March 13th, 2019

Manolis Kellis is a computational biologist at MIT, known as one of the leaders in applying big data to genomics and gene regulatory networks. Throughout my 9 years at MIT, Manolis was one of my best friends there, even though our research styles and interests might seem distant. He and I were in the same PECASE class; see if you can spot us both in this photo (in the rows behind America’s last sentient president). My and Manolis’s families also became close after we both got married and had kids. We still keep in touch.

Today Manolis will be celebrating his 42nd birthday, with a symposium on the meaning of life (!). He asked his friends and colleagues to contribute talks and videos reflecting on that weighty topic.

Here’s a 15-minute video interview that Manolis and I recorded last night, where he asks me to pontificate about the implications of quantum mechanics for consciousness and free will and whether the universe is a computer simulation—and also about, uh, how to balance blogging with work and family.

Also, here’s a 2-minute birthday video that I made for Manolis before I really understood what he wanted. Unlike the first video, this one has no academic content, but it does involve me wearing a cowboy hat and swinging a makeshift “lasso.”

Happy birthday Manolis!

### De-sneering my life

Wednesday, February 27th, 2019

If I’m being honest, the most exciting recent development in my life is this: a little over a month ago, I stopped checking “SneerClub” (a place I’d previously resolved not even to name here, but I think an exception is warranted now). Permanently, cold turkey. I won’t even visit to read their sneers about this post. I’ve made progress cutting down on other self-destructive social media fixations as well. Many friends suggested this course to me, and I thank them all, though I ultimately had to follow my own path to the obvious.

Ironically, the SneerClubbers themselves begged me to stop reading them (!), so presumably for once they’ll be okay with something I did (but if not, I don’t care). If any of them still have something to say to me, they can come to this blog, or email me, or if they pass through Austin, set up a time to hash it out over chips and queso (my treat). What I’ll no longer do is spend hours every week binge-reading a forum of people who’ve adopted nastiness and bad faith as their explicit principles. I’ll no longer toss and turn at night wondering how it came about that two thousand Redditors hate Scott Aaronson so much, and what I could say or do (short of total self-abnegation) that would make them hate me less. I plan to spend the freed-up time being Scott Aaronson.

Resolving to ignore one particular online hate pit—and then sticking to the resolution, as so far I have—has been a pure, unmitigated improvement to my quality of life. If you don’t believe me, ask my wife and kids. I recommend this course to anyone.

You could sensibly ask: why did I ever spend time worrying about an anti-nerds-like-me forum that’s so poisonous for its targets and participants alike? After long introspection, I think the answer is: there’s a part of me, perhaps a gift from the childhood bullies, that’s so obsessed with “society’s hatred of STEM nerds,” that it constantly seeks out evidence to confirm that its fears are justified—evidence that it can then wave in front of the rest of my brain to say “you see?? what did I always tell you?” And alas, whenever that part of my brain seeks such evidence, the world dutifully supplies mountains of it. It’s never once disappointed.

Now the SneerClubbers—who are perceptive and talented in their cruelty, if in nothing else—notice this about me, and gleefully ridicule me for it. But they’re oblivious to the central irony: that unlike the vast majority of humankind, or even the vast majority of social justice activists, they (the SneerClubbers) really do hate everyone like me. They’re precisely what the paranoid part of my brain wrongly fears that everyone else I meet is secretly like. They’re like someone who lectures you about your hilariously overblown fear of muggers, while simultaneously mugging you.

But at least they’re not the contented and self-confident bullies of my childhood nightmares, kicking dirt down at nerds from atop their pinnacle of wokeness and social adeptness. If you spend enough time studying them, they themselves come across as angry, depressed, pathetic. So for example: here’s one of my most persistent attackers, popping up on a math thread commemorating Michael Atiyah (one of the great mathematicians of the 20th century), just to insult Atiyah—randomly, gratuitously, and a few days after Atiyah had died. Almost everything posted all over Reddit by this individual—who uses the accurate tagline “unpleasantly radical”—has the same flavor. Somehow seeing this made it click for me: wait a second, these are the folks are lecturing me about my self-centeredness and arrogance and terrible social skills? Like, at least I try to be nice.

Scott Alexander, who writes the world’s best blog and is a more central target of SneerClub than I’ve been, recently announced that he asked the moderators of r/ssc to close its notorious “Culture War” thread, and they’ve done so—moving the thread to a new home on Reddit called “TheMotte.”

For those who don’t know: r/ssc is the place on Reddit to discuss Scott’s SlateStarCodex blog, though Scott himself was never too involved as more than a figurehead.  The Culture War thread was the place within r/ssc to discuss race, gender, immigration, and other hot-button topics.  The thread, which filled up with a bewildering thousands of comments per week (!), attracted the, err … full range of political views, including leftists, libertarians, and moderates but also alt-righters, neoreactionaries, and white nationalists. Predictably, SneerClub treated the thread as a gift from heaven: a constant source of inflammatory material that they could use to smear Scott personally (even if most of the time, Scott hadn’t even seen the offending content, let alone endorsing it).

Four months ago, I was one of the apparently many friends who told Scott that I felt he should dissociate the Culture War thread from his brand. So I congratulate him on his decision, which (despite his eloquently-expressed misgivings) I feel confident was the right one. Think about it this way: nobody’s freedom of speech has been curtailed—the thread continues full steam at TheMotte, for anyone who enjoys it—but meanwhile, the sneerers have been deprived of a golden weapon with which to slime Scott. Meanwhile, while the sneerers themselves might never change their minds about anything, Scott has demonstrated to third parties that he’s open and reasonable and ready to compromise, like the debater who happily switches to his opponent’s terminology. What’s not to like?

A couple weeks ago, while in Albuquerque for the SQuInT conference, I visited the excellent National Museum of Nuclear Science and History.  It was depressing, as it should have been, to tour the detailed exhibits about the murderous events surrounding the birth of the nuclear era: the Holocaust, the Rape of Nanking, the bombings of Hiroshima and Nagasaki. It was depressing in a different way to tour the exhibits about the early Atomic Age, and see the boundless optimism that ‘unleashing the power of the atom’ would finally usher in a near-utopia of space travel and clean energy—and then to compare that vision to where we are now, with climate change ravaging the planet and (in a world-historic irony) the people who care most about the environment having denounced and marginalized the most reliable source of carbon-free energy, the one that probably had the best chance to avert our planet’s terrifying future.

But on the bright side: how wonderful to have born into a time and place when, for the most part, those who hate you have only the power to destroy your life that you yourself grant them. How wonderful when one can blunt their knives by simply refusing to open a browser tab.

### Announcements

Thursday, December 27th, 2018

I’m planning to be in Australia soon—in Melbourne January 4-10 for a friend’s wedding, then in Sydney January 10-11 to meet colleagues and give a talk. It will be my first trip down under for 12 years (and Dana’s first ever). If there’s interest, I might be able to do a Shtetl-Optimized meetup in Melbourne the evening of Friday the 4th (or the morning of Saturday the 5th), and/or another one in Sydney the evening of Thursday the 10th. Email me if you’d go, and then we’ll figure out details.

The National Quantum Initiative Act is now law. Seeing the photos of Trump signing it, I felt … well, whatever emotions you might imagine I felt.

Frank Verstraete asked me to announce that the University of Vienna is seeking a full professor in quantum algorithms; see here for details.

### Airport idiocy

Wednesday, November 28th, 2018

On Sunday, I returned to Austin with Dana and the kids from Thanksgiving in Pennsylvania.  The good news is that I didn’t get arrested this time, didn’t mistake any tips for change, and didn’t even miss the flight!  But I did experience two airports that changed decisively for the worse.

In Newark Terminal C—i.e., one of the most important terminals of one of the most important airports in the world—there’s now a gigantic wing without a single restaurant or concession stand that, quickly and for a sane price, serves the sort of food that a child (say) might plausibly want to eat.  No fast food, not even an Asian place with rice and teriyaki to go.  Just one upscale eatery after the next, with complicated artisanal foods at brain-exploding prices, and—crucially—“servers” who won’t even acknowledge or make eye contact with the customers, because you have to do everything through a digital ordering system that gives you no idea how long the food might take to be ready, and whether your flight is going to board first.  The experience was like waking up in some sci-fi dystopia, where all the people have been removed from a familiar environment and replaced with glassy-eyed cyborgs.  And had we not thought to pack a few snacks with us, our kids would’ve starved.

Based on this and other recent experiences, I propose the following principle: if a customer’s digitally-mediated order to your company is eventually going to need to get processed by a human being anyhow—a fallible human who could screw things up—and if you’re less competent at designing user interfaces than Amazon (which means: anyone other than Amazon), then you must make it easy for the customer to talk to one of the humans behind the curtain.  Besides making the customer happy, such a policy is good business, since when you do screw things up due to miscommunications caused by poor user interfaces—and you will—it will be on you to fix things anyway, which will eat into your profit margin.  To take another example, besides Newark Terminal C, all these comments apply with 3000% force to the delivery service DoorDash.

Returning to airports, though: whichever geniuses ruined Terminal C at Newark are amateurs compared to those in my adopted home city of Austin.  Austin-Bergstrom International Airport (ABIA) chose Thanksgiving break—i.e., the busiest travel time of the year—to roll out a universally despised redesign where you now need to journey for an extra 5-10 minutes (or 15 with screaming kids in tow), up and down elevators and across three parking lots, to reach the place where taxis and Ubers are.  The previous system was that you simply walked out of the terminal, crossed one street, and the line of taxis was there.

Supposedly this is to “reduce congestion” … except that, compared to other airports, ABIA never had any significant congestion caused by taxis.  I’d typically be the only person walking to them at a given time, or I’d join a line of just 3 or 4 people.  Nor does this do anything for the environment, since the city of Austin has no magical alternative, no subway or monorail to whisk you from the airport to downtown.  Just as many people will need a taxi or Uber as before; the only difference is that they’ll need to go ten times further out of their way as they’d need to go at a ten times busier airport.  For new visitors, this means their first experience of Austin will be one of confusion and anger; for Austin residents who fly a few times per month, it means that days or weeks have been erased from their lives.  From the conversations I’ve had so far, it appears that every single passenger of ABIA, and every single taxi and Uber driver, is livid about the change.  With one boneheaded decision, ABIA singlehandedly made Austin a less attractive place to live and work.

Postscript I.  But if you’re a prospective grad student, postdoc, or faculty member, you should still come to UT!  The death of reason, and the triumph of the blank-faced bureaucrats, is a worldwide problem, not something in any way unique to Austin.

Postscript II.  No, I don’t harbor any illusions that posts like this, or anything else I can realistically say or do, will change anything for the better, at my local airport let alone in the wider world.  Indeed, I sometimes wonder whether, for the bureaucrats, the point of ruining facilities and services that thousands rely on is precisely to grind down people’s sense of autonomy, to make them realize the futility of argument and protest.  Even so, if someone responsible for the doofus decisions in question happened to come across this post, and if they felt even the tiniest twinge of fear or guilt, felt like their victory over common sense wouldn’t be quite as easy or painless as they’d hoped—well, that would be reason enough for the post.

### Boof

Tuesday, October 2nd, 2018

(Just a few politics-related comments to get off my chest.  Feel free to skip if American politics isn’t your 5-liter bottle of Coke.)

FiveThirtyEight currently gives Beto O’Rourke a ~29% chance of winning Ted Cruz’s Senate seat.  I wish it were higher, but I think this will be such a spectacular upset if it happens, and so transformative for Texas, that it’s well worth our support.  I’ve also been impressed by the enthusiasm of Beto’s campaign—including a rally in Austin this weekend where the 85-year-old Willie Nelson, headlining the first political event of his 60-year music career, performed a new song (“Vote ‘Em Out”).  I’ll tell you what: if anyone donates to Beto’s campaign within the next two days as a result of reading this post, and emails or leaves a comment to tell me about it, I’ll match their donation, up to my personal Tsirelson bound of $853. Speaking of which, if you’re a US citizen and are not currently registered to vote, please do so! And then show up and vote in the midterms! My personal preference is to treat voting as simply a categorical imperative. But if you’d like a mathematical discussion of the expected utility of voting, then check out this, by my former MIT undergraduate advisee Shaunak Kishore. But what about the highest questions currently facing the American republic: namely, the exact meanings of “boofing,” “Devil’s triangle,” and “Renate alumnius”? I’ve been reading the same articles and analyses as everybody else, and have no privileged insight. For what it’s worth, though, I think it’s likely that Blasey Ford is teling the truth. And I think it’s likely that Kavanaugh is lying—if not about the assault itself (which he might genuinely have no memory of—blackout is a real phenomenon), then certainly about his teenage drinking and other matters. And while, absent some breakthrough in the FBI investigation, none of this rises to the beyond-a-reasonable-doubt standard, I think it likely should be seen as disqualifying for the Supreme Court. (Admittedly, I’m not a good arbiter of that question, since there are about 200 unrelated reasons why I don’t want Kavanaugh near the Court.) I also think it’s perfectly reasonable of Senate Democrats to fight this one to the bitter end, particularly after what the Republicans did to Merrick Garland, and what Kavanaugh himself did to Bill Clinton. If you’re worried about the scorched-earth, all-defect equilibrium that seems to prevail in Congress—well, the Democrats are not the ones who started it. All of that would be one thing, coming from some hardened social-justice type who might have happily convicted Kavanaugh of aggravated white male douchiness even before his umbilical cord was cut. But I daresay that it means a bit more, coming from an individual who hundreds of online activists once denounced just as fervently as they now denounce Kavanaugh—someone who understands perfectly well that not even the allegation of wrongdoing is needed any longer for a person to be marked for flattening by the steamroller of Progress. What can I say? The enemy of my enemy is sometimes still my enemy. My friend is anybody, of whatever party or creed, who puts their humanity above their ideology. Justice is no respecter of persons. Sometimes those who earn the mob’s ire are nevertheless guilty. I was actually in the DC area the week of the Kavanaugh hearings, to speak at a quantum information panel on Capitol Hill convened by the House Science Committee, to participate in a quantum machine learning workshop at UMD, and to deliver the Nathan Krasnopoler Memorial Lecture at Johns Hopkins, which included the incredibly moving experience of meeting Nathan’s parents. The panel went fine, I think. Twenty or thirty Congressional staffers attended, including many of those involved in the National Quantum Initiative bill. They asked us about the US’s standing relative to China in QIS; the relations among academia, industry, and national labs; and how to train a ‘quantum workforce.’ We panelists came prepared with a slide about what qubits and interference are, but ended up never needing it: the focus was emphatically on policy, not science. Kamala Harris (D-CA) is the leader in the Senate for what’s now called the Quantum Computing Research Act. One of Sen. Harris’s staffers conveyed to me that, given her great enthusiasm for quantum computing, the Senator would have been delighted to meet with me, but was unfortunately too busy with Kavanaugh-related matters. This was better than what I’d feared, namely: “following the lead of various keyboard warriors on Twitter and Reddit, Sen. Harris denounces you, Dr. Aaronson, as a privileged white male techbro and STEMlord, and an enemy of the people.” So once again I was face-to-face with the question: is it conceivable that social-media discourse is a bit … unrepresentative of the wider world? ### My Tomassoni-Chisesi Prize talk Saturday, September 15th, 2018 Update (Sep. 21) Video of Philip Kim’s and my talks is now available! (But not streaming, just a giant mp4 that you can download.) On Thursday, I had the incredible honor of accepting the 2018 Tomassoni-Chisesi Prize in Physics at Università “La Sapienza” in Rome—“incredible” mostly because I’m of course not a physicist. (I kept worrying they’d revoke the award when they realized I could barely solve the wave equation.) This is not the first time quantum information was recognized; the prize has previously gone to Serge Haroche and Alain Aspect. This year, for the first time, there was both an under-40 and an over-40 award; the latter went to Philip Kim, a quantum materials researcher at Harvard who I had the privilege to meet on this trip (he’s the taller one below). I’m unbelievably grateful, not only to the committee, and its chair Giorgio Parisi (whose seminal work on phase transitions and satisfiability I’d long known, but who I met for the first time on this trip), but to Fabio Sciarrino, Paolo Mataloni, Fernanda Lupinacci, and everyone else who graciously hosted me and helped make my hastily-planned visit to Europe a success. The department I visited has a storied history: here are the notes that Enrico Fermi left, documenting what he covered each day in his physics class in 1938. The reason the last squares are blank is that, when Fermi and his Jewish wife left for Stockholm on the occasion of Fermi’s Nobel Prize, they continued directly to the US rather than return to an Italy that had just passed the racial laws. On my way to Rome, I also gave two talks at a “quantum computing hackathon” in Zurich, called QuID (Quantum Information for Developers). Thanks so much to Lidia del Rio for arranging that visit, which was fantastic as well. To accept the Tomassoni-Chisesi prize, I had to give a 40-minute talk summarizing all my research from 2000 to the present—the hardest part being that I had to do it while wearing a suit, and sweating at least half my body weight. (I also had a cold and a hacking cough.) I think there will eventually be video of my and Prof. Kim’s talks, but it’s not yet available. In the meantime, for those who are interested, here are my PowerPoint slides, and here’s the title and abstract: Three Questions About Quantum Computing Scott Aaronson (University of Texas at Austin) I’ll discuss some of my work in quantum computing over the past 18 years, organizing it in terms of three questions. First, how can we demonstrate, using near-future hardware, that quantum computers can get any genuine speedups at all over classical computers (ideally useful speedups)? Second, what sorts of problems would be hard even for quantum computers, and can we turn the intractability of those problems to our advantage? Third, are there physically reasonable models of computation even more powerful than quantum computing, or does quantum computing represent an ultimate limit? If you’re a regular reader here, most of the content will be stuff you’ve seen before, with the exception of a story or two like the following: Last night I was talking to my mom about my grandfather, who as it happens came through Rome 73 years ago, as an engineer with the US Army. Disabling landmines was, ironically, one of the safer ways to be a Jew in Europe at that time. If you’d told him then that, three-quarters of a century later, his grandson would be back here in Rome to accept an award for research in quantum computational complexity … well, I’m sure he’d have any number of questions about it. But one thing I clearly remember is that my grandfather was always full of effusive praise for the warmth of the people he met in Italy—how, for example, Italian farmers would share food with the hungry and inadequately-provisioned Allied soldiers, despite supposedly being on the opposing side. Today, every time I’m in Italy for a conference or a talk, I get to experience that warmth myself, and certainly the food part. (Awww! But I meant it. Italians are super-warm.) There’s a view that scientists should just pursue the truth and be serenely unaffected by prizes, recognition, and other baubles. I think that view has a great deal to be said for it. But thinking it over recently, I struck the following mental bargain: if I’m going to get depressed on a semi-regular basis by people attacking me online—and experience shows that I will—well then, I also get to enjoy whatever’s the opposite of that with a clear conscience. It’s not arrogance or self-importance; it’s just trying to balance things out a bit! So again, thanks so much—to the physics department of La Sapienza, but also to my family, friends, mentors, readers, colleagues at UT Austin and around the world, and everyone else who helps make possible whatever it is that I do. ### Beyond fiction Wednesday, August 8th, 2018 I now know firsthand what it’s like to be arrested by armed police officers, handcuffed, and sharply interrogated, while one’s wife and children look on helplessly. This is not a prank post. It happened in Philadelphia International Airport. As someone who was born in Philadelphia, and who’s since visited ~40 countries on 6 continents and flies every week or two, I’ve long considered PHL possibly the most depressing airport on the planet (and the competition is fierce). I’d just eaten dinner with my wife Dana and our two kids in a food court—after a day of travel that had already, before this happened, involved a missed flight and a lost suitcase, owing to a chain of mishaps that I’d (probably melodramatically) been describing to Dana as insane beyond the collective imagination of Homer and Shakespeare and Tolstoy and the world’s other literary giants to invent. Again, that was before my arrest. Two large uniformed men with holstered pistols saw me as we were exiting the airport, surrounded and handcuffed me, and demanded that I confess. “I’m … sorry, officers,” I managed. “I don’t understand what this is about.” “Stop the games. You know exactly what you took. We have it all on video. Where is it?” Me, a thief? I felt terrified to be at the beginning of a Kafka story. But if I’m going to be brutally honest about it, I also felt … secretly vindicated in my irrational yet unshakeable beliefs that 1. the laws of probability are broken, capricious horribleness reigning supreme over the universe, 2. I’m despised by a large fraction of the world just for being who I am, and 3. it’s only a matter of time until big, scary armed guys come for me, as they came for so many other nerdy misfits. I almost wanted to say to the police: where have you been? I’ve been expecting you my whole life. And I wanted to say to Dana: you see?? see what I’ve been telling you all these years, about the nature of the universe we were born into? Dana, for her part, was remonstrating with the officers that there must be some misunderstanding, that her husband was often absentminded but it’s completely impossible that he stole anything. The officers brushed her away, told her to remove the kids from the situation. “Are you gonna come clean?” one of the cops barked at me. “We know you took it.” “I didn’t take anything.” Then I thought it over more. “Or if somehow I did … then I’m certain that it would’ve been an accident, and I’d be more than happy to fix the…” “Wait, if you did? It sounds like you just confessed!” “No, I definitely didn’t steal anything. I’m just saying it’s possible that I might have mistakenly…” “Your answers are rambling and all over the place. Stop making up stories. We know you did it.” I’m not proud of myself for the next part, but the officers were so serious, and somehow I had to make them realize the sheer comical absurdity of what was happening. “Look, I’m a computer science professor,” I said. “I’ve never stolen a penny in my life, and it’s not something I’d ever…” “Yeah, well I’m a police officer. I’ve seen a lot in my thirty years in this job. This is not about who you are, it’s about what you did.” But what did I do? After many more attempts to intimidate me, I was finally informed of the charge: “that smoothie place over there says you stole cash from their tip jar.” Huh? How much? One of the officers returned from the smoothie bar, and said, a bit sheepishly: “they say it was$4.”

Now a vague recollection came into sharper focus.  Yes, I had bought a berry smoothie for my daughter and a sparkling grapefruit juice for me.  I’d paid with a debit card, for reasons that I don’t remember, even though I normally pay cash.  My mind was elsewhere: on the missed flight, the lost suitcase, the brazen behavior of American Airlines (about which more later).  Then, completely forgetting I hadn’t paid cash this time, I looked down for my change: $4 in an unmarked plastic change cup. I collected the change, put it in my wallet, then completely forgot about it. After a minute, an employee angrily pointed down at a tray that the plastic cup was on (though not clearly at the cup itself), and said “hey, the tips go here!” So I took a dollar from my wallet and put it on the tray. I thought: this guy has some chutzpah, to demand a tip, and for an over-the-counter smoothie! But whatever, he probably needs the dollar more than I do. So if it will make him stop being angry… But he was still angry. He repeated: “this here is for tips!” I said something to the effect of: “yeah, I know–that’s what you just told me, isn’t it? So that’s why I just left you a tip!” Sheesh. At no point did he ever say, “you accidentally took from the tip jar,” or any other statement that would’ve clarified his meaning. As I turned and walked away, I thought: yes, this is the strange world I was born into. A world where people yell at me for not tipping at a smoothie bar–is that expected? I didn’t think it was–and then continue yelling even after I do. But what did I expect? Did I expect, as a nerdy outsider, to be able to buy normal people’s toleration with mere money? As soon as I figured out what had happened, of course I offered to pay back the smoothie bar, not merely the$3 I still owed them, but $40 or whatever other amount would express my goodwill and compensate them for their trouble. But the smoothie bar returned the$40 that I’d asked Dana to give them—I was unable to bring it myself on account of being handcuffed—and refused to press charges.  (In fact, apparently the employees hadn’t wanted to involve the police at all.  It was the manager, who hadn’t seen what happened, who’d insisted on it.)

So with no case, the police finally had no choice but to let me go–though not before giving me a stern lecture about never again putting my hands on stuff that’s not mine.

A week later, I’m still processing the experience.  In the rest of the post, I’d like to reflect on some lessons I think I learned from it.

First, it’s said that “a conservative is a liberal who’s been mugged; a liberal is a conservative who’s been arrested.”  It’s true: there are aspects of being arrested that are hard to understand until you’ve been through it.  While I’m white (well, insofar as Ashkenazim are), and while both officers who interrogated me happened to be African-Americans, what I went through further increased my sympathy for the many minority victims of aggressive policing.  Sitting in your armchair, it’s easy to think: in a liberal democracy, as long you know you did nothing wrong, even if you got arrested, frisked, detained, there’d probably be no real need to panic.  All you’d need to do is calmly clear up the misunderstanding and be back on your merry way.

But at least in my experience, an actual arrest isn’t like that.  The presumption of innocence, Miranda rights, all the things you might learn about in civics class—none of it seems to play any role.  From the very beginning, there’s an overwhelming presumption of guilt.  Everything you say gets interpreted as if you’re a red-handed criminal trying to fabricate a story, no matter how strained and how ludicrous such an interpretation might become.

And something strange happened: the officers seemed so certain I was guilty, that after only a few minutes I started to feel guilty.  I still had only a hazy sense of my “crime,” but I knew I was going to be punished for it, and I only hoped that the punishment wouldn’t tear me away from my family and previous life forever.

I came away from this incident with a visceral feel for just how easy it would be to procure a false confession from someone, which I didn’t have before but which will now stay with me as long as I live.

Second, it occurred to me that the sight of me, stuttering and potbellied complexity blogger, shackled and interrogated by armed policemen demanding that he confess to the theft of $3 from an airport stand, is a decent visual metaphor for much of my life. If you doubt this, simply imagine Arthur Chu or Amanda Marcotte in place of the police officers. It’s like: my accusers arrive on the scene committed to a specific, hostile theory of me: that I’m a petty thief of smoothie bars, let’s say, or a sexual-harassment-loving misogynist. With all due modesty, people who know me might say that it’s not merely that I don’t fit the theory, that I happen to be innocent of the charge. Rather, it’s that I’m one of the most astronomically, ridiculously unlikely people to fit the theory you could ever meet. Not because I’m especially saintly, but simply because I already walk around all day feeling like my right to exist is conditional and might be revoked at any minute. Breaking the normal people’s rules is the last thing on my agenda! And yes, I still often feel that way, even as a professor with an endowed chair and awards and whatever. The only times when I really relax, among strangers, is when everyone’s there to discuss ideas. But my accusers don’t know any of that, or they refuse to believe it. Everything I say gets interpreted in the light of the hostile theory, and therefore serves only as further confirmation of it. Ironically—and this is key—the very unusual personality traits that make me so unlikely to be an offender, are also what throw off my accusers’ detection algorithms, and make them double down on their wrong theory. When I’m trapped, I tend to fall back on the only tools I know: argument, openness, frank confession of my mistakes and failings, sometimes a little self-deprecating humor. Unfortunately, I find this often backfires, as my accusers see in my vulnerability a golden opportunity to mount another wretched evildoer above their fireplace. Or, to go even further out on a psychoanalytic limb: I sometimes get the sense that it gradually does dawn on my accusers that I’m not who they thought I was. And then, far from prompting an apology, that realization seems to make my accusers even angrier, as if my throwing off their model of reality so badly, was an even worse offense than actually being guilty of whatever they thought! A thief, a misogynist, they know how to handle. But a living, breathing adversarial example for their worldview? Dana, who watched the entire arrest, tells me that the central mistake I made was to try to reason with the police officers: “you say I took$3 that wasn’t mine?  If so, then I’m sure it was an accident, so let’s try to figure out what happened so we can fix it…”  In Dana’s view, what I saw as an earnest desire to get to the bottom of things, came across to grizzled cops only as evasiveness and guilt.  She says it would’ve been far better if I’d categorically denied: “no, I did not steal.  That’s completely absurd.  Please release me immediately.”

I’ve asked myself: how do you live in a world where, again and again, you can choose the hard right path over the easy wrong one, and then see your choice gleefully wielded against you?  Where you can spill your guts out to your accusers, in a desperate attempt to talk with them not as hardened warriors, but one confused and vulnerable human to another–and your reward is (to take one example) your picture in Salon above the headline “The Plight of the Bitter Nerd”?

The only way to live in such a world, as far as I can see, is to remind yourself that sometimes openness and vulnerability work.  In the course of my arrest, the two officers gradually differentiated themselves into a “good cop” and a “bad cop.”  While the “bad cop” treated me till the end like an unrepentant kleptomaniac being freed on a technicality, the “good cop,” who talked to me and Dana much more, became almost apologetic: “look man, when we get a call that someone stole money, we have to treat it like that’s the situation, you understand what I’m saying?  And then if it’s not, well then it’s not.”  Likewise, Arthur Chu recently tweeted that he’s “unhappy about [my] continued existence”–i.e., on a straightforward reading, that he wants me to die.  But I try to remind myself every day that the human race doesn’t consist solely of Arthur Chus (or Amanda Marcottes, or Lubos Motls, or SneerClub posters, or Paul Manaforts or Donald Trumps).  The world contains millions of women and men of every background and ideology who want actual dialogue, many of whom I’m lucky to count as friends, many of whom I met through this blog.  Vulnerability is possible because the world is not uniformly evil.

Third, I emerged from my arrest with a self-help technique that’s probably well-known to somebody, but that was new to me, and that I hope others will find as useful as I’m finding it.  Here it is: when something freakishly bad happens to you, draw a directed graph of all the known causes of the event, and the causes of the causes, and so forth as far back as you can trace them.  Also draw all the known measures that could have blocked the causal path leading to the bad event, and what prevented those measures from working or from being tried.

For example: why did I end up in handcuffs?  Firstly because, earlier in the day, Lily threw a temper tantrum that prevented us from packing and leaving for Logan Airport on time.  Because there was also heavy traffic on the way there.  Because we left from Harvard Square, and failed to factor in the extra 10 minutes to reach the airport, compared to if we’d left from MIT.  Because online check-in didn’t work.  Because when we did arrive, (barely) on time, the contemptuous American Airlines counter staff deliberately refused to check us in, chatting as we stewed impotently, so that we’d no longer be on time and they could legally give our seats away to others, and strand us in an airport with two young kids.  Because the only replacement flight was in a different terminal.  Because, in the stress of switching terminals–everything is stressful with two kids in an airport–I lost our suitcase.  Because the only shuttle to get back to the terminal went around the long way, and was slow as molasses, and by the time I returned our suitcase had been taken by the bomb squad.  Because the stress of such events bears down on me like an iron weight, and makes me unable to concentrate on the reality in front of me.  Because the guy at the smoothie counter and I failed to communicate.  Because the police chose to respond (or were trained to respond), not by politely questioning me to try to understand what had happened, but by handcuffing me and presuming guilt.

I actually drew the graph, filled a notebook page with it–and when I searched it for answers, neither I nor the world got off easily.  Looking over the strange chain of events that led to my arrest, I could find much to support my “default narrative,” that the laws of probability are broken and the universe is grotesquely awful.  But also, my belief in the universe’s grotesque awfulness clearly played a role in the events.  Had I been able maintain a calm demeanor, I would not have made so many mistakes.

Again and again, I screwed up.  Again and again, airport personnel responded to my honest mistakes with a maximum of cold bureaucracy rather than commonsense discussion: the booting from the flight, the bomb squad, the handcuffs.

We tend to think of bureaucracy as a mere nuisance, the person behind the counter at the Department of Motor Vehicles who makes you wait all day and then sends you home to get a different form of ID.  In my view, though, the bureaucratic impulse is one of the worst evils of which the human mind is capable.  It is, after all, the impulse that once sent trainloads of Jewish children to their deaths because that was the policy and there were no documents stating that any exception should be made in this case.  Today it’s the impulse that rounds up and deports people who’ve lived in the US for decades, sometimes served in the army, etc., and that separates screaming children from their parents.  To me, the mindset that willingly carries out such orders is almost more terrifying than the mindset that gives the orders in the first place.  I don’t mean to suggest, of course, that my arrest was even a trillionth as bad as those other things; at most I got a tiny, accidental taste of many less fortunate people’s daily reality.  But it’s worth remembering: every time you exercise official power over another person without even trying to talk it over first, clear up any honest misunderstandings, find out if there’s a reasonable explanation, you’re surrendering to one of the most destructive impulses in the history of civilization.

May we each strive to kill the bureaucrat in us and nurture the human being.

Unrelated Announcements:

I’m in Mexico City this week, to participate in a computer science and philosophy conference at UNAM and then give a broad quantum computing talk at CViCom 2018.  Because of this, responses to this post might be delayed.

(Update: But I’m having a wonderful time in Mexico!  Lots of delicious mole and horchata, and no arrests so far.  Today I gave my survey talk on P vs. NP.  I opened with the following icebreaker: “As a computer scientist speaking in a philosophy institute, I apologize that my talk will contain very little philosophy  Also, as an American speaking in Mexico, I apologize for our president.”)

My friend Elette Boyle asked me to announce that the 2018 CRYPTO conference, to be held in Santa Barbara, will be preceded by exciting workshops, including one that I’ll be speaking at myself entitled Beyond Crypto: A Theory Perspective.  Register now if you’re interested.

Huge congratulations to Costis Daskalakis, my former MIT colleague, for winning the Nevanlinna Prize for his work in algorithmic game theory!  While I don’t pretend to understand their work, congratulations to the four new Fields Medalists as well.

I put a new preprint online: Quantum Lower Bound for Approximate Counting Via Laurent Polynomials.

I’ve added a new blog to my blogroll: The Unit of Caring. I’ve been impressed by the author’s moral adeptness: when she addresses contentious debates among nerds, rationalists, feminists, SJWs, etc. etc., she often seems perfectly balanced on an atom-thin tightrope, even as some of us are plummetting left and right.

I forgot to mention this earlier, but I’m now a donor to the campaign of Beto O’Rourke, as he strives to unseat the quisling Ted Cruz in my adopted home state of Texas.  Americans: please consider donating as well!

Further Thoughts (Aug. 9):

1. I wholeheartedly endorse an observation that many commenters (on this blog and elsewhere) made independently: that what really happened, is that I was forced to live out an episode of Seinfeld or Curb Your Enthusiasm.  To my detractors, I say the following: try for one minute to imagine how pathological, narcissistic, far outside the human norm, etc. etc. you could make Seinfeld or George or Kramer or Elaine seem, if their misadventures from any given episode were described and analyzed with clinical detachment.  (Or you were never a Seinfeld fan, then I guess this argument fails and we have nothing to say to each other.)
2. I feel like some commenters are imposing their own after-the-fact knowledge (“c’mon, it was obviously a tip jar, he must be lying!”).  Dana, who’s generally more grounded than I am, saw their whole setup and agreed it was profoundly non-obvious that the tiny, unmarked plastic cup was supposed to be for tips, particularly to someone who was extremely stressed and not concentrating.  And when the employee later talked about tips, he didn’t indicate the cup so I didn’t make a connection.
3. Most importantly: I wish to clarify that I don’t regard the police officers who handcuffed and interrogated me as having been “evil” in any sense.  I even took a liking to the “good cop,” the one who implicitly acknowledged the situation’s surreal absurdity by the end (although maybe that’s the whole point of a “good cop”?).  Having said that, I’m still rattled by the way the “bad cop” treated me as an unrepentant thief even to the end, even after the situation had been cleared up to everyone else’s satisfaction.  And I stand by my view that there was no need to handcuff me in front of my wife and young children, when I’d shown not a single subatomic particle of resistance.
4. Speaking of which, let me now relate the most interesting and unexpected part of the reaction to my story.  Again and again, I found that fellow Americans, even nominally left-wing ones, sided with the police, said that I was crazy and guilty as charged and should’ve expected much worse, etc.  And again and again, commenters from Australia and New Zealand sided with me 300%, said that handcuffing someone over such a trivial mishap was a ludicrous overreaction, which would be totally unheard of in their countries and which confirms all the bad things they’ve heard about the US.  So maybe the rational conclusion is that I should be learning to enjoy vegemite in preparation for a move down under?

### Summer recapitulates life

Tuesday, July 24th, 2018

Last week, I was back at the IAS in Princeton, to speak at a wonderful PITP summer school entitled “From Qubits to Spacetime,” co-organized by Juan Maldacena and Edward Witten. This week, I’ll be back in Waterloo, to visit old and new friends at the Perimeter Institute and Institute for Quantum Computing and give a couple talks.  Then, over the weekend, I’ll be back in Boston to see old friends, colleagues, and students.  After some other miscellaneous travel, I’ll then return to Austin in late August when the semester begins.  The particular sequence IAS → Waterloo → Boston → Austin is of course one that I’ve followed before, over a longer timescale.

Two quick announcements:

First, at the suggestion of reader Sanketh Menda, I’m thinking of holding a Shtetl-Optimized meetup in Waterloo this week.  Please send me an email if you’re interested, and we’ll figure out a time and place that work for everyone.

Second, many of the videos from the IAS summer school are now available, including mine: Part I and Part II.  I cover some basics of complexity theory, the complexity of quantum states and unitary transformations, the Harlow-Hayden argument about the complexity of turning a black hole event horizon into a firewall (with my refinement), and my and Lenny Susskind’s work on circuit complexity, wormholes, and AdS/CFT.  As a special bonus, check out the super-embarrassing goof at the beginning of my first lecture—claiming a mistaken symmetry of conditional entropy and even attributing it to Edward Witten’s lecture!  (But Witten, who I met for the first time on this visit, was kind enough to call my talk “lots of fun” anyway, and give me other positive comments, which I should put on my CV or something.)

Addendum: Many of the PITP videos are well worth watching!  As one example, I found Witten’s talks to be shockingly accessible.  I’d been to a previous talk of his involving Khovanov homology, but beyond the first few minutes, it went so far over my head that I couldn’t tell you how it was for its intended audience.  I’d also been to a popular talk of Witten’s on string theory, but that’s something he could do with only 3 awake brain cells.  In these talks, by contrast, Witten proves some basic inequalities of classical and quantum information theory, then proves the Reeh-Schlieder Theorem of quantum field theory and the Hawking and Penrose singularity theorems of GR, and finally uses quantum information theory to prove positive energy conditions from quantum field theory that are often needed to make statements about GR.

### My Y Combinator podcast

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