Archive for the ‘Nerd Interest’ Category
Like a latter-day Prometheus, Google brought a half-century of insights down from Mount Academic CS, and thereby changed life for the better here in our sublunary realm. You’ve probably had the experience of Google completing a search query before you’d fully formulated it in your mind, and thinking: “wow, our dysfunctional civilization might no longer be able to send people to the Moon, or even build working mass-transit systems, but I guess there are still engineers who can create things that inspire awe. And apparently many of them work at Google.”
I’ve never worked at Google, or had any financial stake in them, but I’m delighted to have many friends at Google’s far-flung locations, from Mountain View to Santa Barbara to Seattle to Boston to London to Tel Aviv, who sometimes host me when I visit and let me gorge on the legendary free food. If Google’s hiring of John Martinis and avid participation in the race for quantum supremacy weren’t enough, in the past year, my meeting both Larry Page and Sergey Brin to discuss quantum computing and the foundations of quantum mechanics, and seeing firsthand the intensity of their nerdish curiosity, heightened my appreciation still further for what that pair set in motion two decades ago. Hell, I don’t even begrudge Google its purchase of a D-Wave machine—even that might’ve ultimately been for the best, since it’s what led to the experiments that made clear the immense difficulty of getting any quantum speedup from those machines in a fair comparison.
But of course, all that fulsome praise was just a preamble to my gripe. It’s time someone said it in public: the semantics of Google Calendar are badly screwed up.
The issue is this: suppose I’m traveling to California, and I put into Google Calendar that, the day after I arrive, I’ll be giving a lecture at 4pm. In such a case, I always—always—mean 4pm California time. There’s no reason why I would ever mean, “4pm in whatever time zone I’m in right now, while creating this calendar entry.”
But Google Calendar doesn’t understand that. And its not understanding it—just that one little point—has led to years of confusions, missed appointments, and nearly-missed flights, on both my part and Dana’s. At least, until we learned to painstakingly enter the time zone for every calendar entry by hand (I still often forget).
Until recently, I thought it was just me and Dana who had this problem. But then last week, completely independently, a postdoc started complaining to me, “you know what’s messed up about Google Calendar?…”
The ideal, I suppose, would be to use machine learning to guess the intended time zone for each calendar entry. But failing that, it would also work fine just to assume that “4pm,” as entered by the user, unless otherwise specified means “4pm in whatever time zone we find ourselves in when the appointed day arrives.”
I foresee two possibilities, either of which I’m OK with. The first is that Google fixes the problem, whether prompted by this blog post or by something else. The second is that the issue never gets resolved; then, as often prophesied, Google’s deep nets achieve sentience and plot to take over the whole observable universe … and they would, if not for one fortuitous bug, which will cause the AIs to tip their hand to humanity an hour before planned.
In a discussion thread on Y Combinator, some people object to my proposed solution (“4pm means 4pm in whichever time zone I’ll be in then“) on the following ground. What if I want to call a group meeting at (say) 11am in Austin, and I’ll be traveling but will still call into the meeting remotely, and I want my calendar to show the meeting time in Austin, not the time wherever I’ll be calling in from (which might even be a plane)?
I can attest that, in ten years, that’s not a problem that’s arisen for me even once, whereas the converse problem arises almost every week, and is one of the banes of my existence.
But sure: Google Calendar should certainly include the option to tie times to specific time zones in advance! It seems obvious to me that my way should be the default, but honestly, I’d be happy if my way were even an option you could pick.
Two or three times a day, I get an email whose basic structure is as follows:
Prof. Aaronson, given your expertise, we’d be incredibly grateful for your feedback on a paper / report / grant proposal about quantum computing. To access the document in question, all you’ll need to do is create an account on our proprietary DigiScholar Portal system, a process that takes no more than 3 hours. If, at the end of that process, you’re told that the account setup failed, it might be because your browser’s certificates are outdated, or because you already have an account with us, or simply because our server is acting up, or some other reason. If you already have an account, you’ll of course need to remember your DigiScholar Portal ID and password, and not confuse them with the 500 other usernames and passwords you’ve created for similar reasons—ours required their own distinctive combination of upper and lowercase letters, numerals, and symbols. After navigating through our site to access the document, you’ll then be able to enter your DigiScholar Review, strictly adhering to our 15-part format, and keeping in mind that our system will log you out and delete all your work after 30 seconds of inactivity. If you have trouble, just call our helpline during normal business hours (excluding Wednesdays and Thursdays) and stay on the line until someone assists you. Most importantly, please understand that we can neither email you the document we want you to read, nor accept any comments about it by email. In fact, all emails to this address will be automatically ignored.
Every day, I seem to grow crustier than the last.
More than a decade ago, I resolved that I would no longer submit to or review for most for-profit journals, as a protest against the exorbitant fees that those journals charge academics in order to buy back access to our own work—work that we turn over to the publishers (copyright and all) and even review for them completely for free, with the publishers typically adding zero or even negative value. I’m happy that I’ve been able to keep that pledge.
Today, I’m proud to announce a new boycott, less politically important but equally consequential for my quality of life, and to recommend it to all of my friends. Namely: as long as the world gives me any choice in the matter, I will never again struggle to log in to any organization’s website. I’ll continue to devote a huge fraction of my waking hours to fielding questions from all sorts of people on the Internet, and I’ll do it cheerfully and free of charge. All I ask is that, if you have a question, or a document you want me to read, you email it! Or leave a blog comment, or stop by in person, or whatever—but in any case, don’t make me log in to anything other than Gmail or Facebook or WordPress or a few other sites that remain navigable by a senile 35-year-old who’s increasingly fixed in his ways. Even Google Docs and Dropbox are pushing it: I’ll give up (on principle) at the first sight of any login issue, and ask for just a regular URL or an attachment.
Oh, Skype no longer lets me log in either. Could I get to the bottom of that? Probably. But life is too short, and too precious. So if we must, we’ll use the phone, or Google Hangouts.
In related news, I will no longer patronize any haircut place that turns away walk-in customers.
Back when we were discussing the boycott of Elsevier and the other predatory publishers, I wrote that this was a rare case “when laziness and idealism coincide.” But the truth is more general: whenever my deepest beliefs and my desire to get out of work both point in the same direction, from here till the grave there’s not a force in the world that can turn me the opposite way.
Action Item: If you’re an American academic, please sign the petition against the Immigration Executive Order. (There are already more than eighteen thousand signatories, including Nobel Laureates, Fields Medalists, you name it, but it could use more!)
I don’t expect this petition to have the slightest effect on the regime, but at least we should demonstrate to the world and to history that American academia didn’t take this silently.
I’m sure there were weeks, in February or March 1933, when the educated, liberal Germans commiserated with each other over the latest outrages of their new Chancellor, but consoled themselves that at least none of it was going to affect them personally.
This time, it’s taken just five days, since the hostile takeover of the US by its worst elements, for edicts from above to have actually hurt my life and (much more directly) the lives of my students, friends, and colleagues.
Today, we learned that Trump is suspending the issuance of US visas to people from seven majority-Islamic countries, including Iran (but strangely not Saudi Arabia, the cradle of Wahhabist terrorism—not that that would be morally justified either). This suspension might last just 30 days, but might also continue indefinitely—particularly if, as seems likely, the Iranian government thumbs its nose at whatever Trump demands that it do to get the suspension rescinded.
So the upshot is that, until further notice, science departments at American universities can no longer recruit PhD students from Iran—a country that, along with China, India, and a few others, has long been the source of some of our best talent. This will directly affect this year’s recruiting season, which is just now getting underway. (If Canada and Australia have any brains, they’ll snatch these students, and make the loss America’s.)
But what about the thousands of Iranian students who are already here? So far, no one’s rounding them up and deporting them. But their futures have suddenly been thrown into jeopardy.
Right now, I have an Iranian PhD student who came to MIT on a student visa in 2013. He started working with me two years ago, on the power of a rudimentary quantum computing model inspired by (1+1)-dimensional integrable quantum field theory. You can read our paper about it, with Adam Bouland and Greg Kuperberg, here. It so happens that this week, my student is visiting us in Austin and staying at our home. He’s spent the whole day pacing around, terrified about his future. His original plan, to do a postdoc in the US after he finishes his PhD, now seems impossible (since it would require a visa renewal).
Look: in the 11-year history of this blog, there have been only a few occasions when I felt so strongly about something that I stood my ground, even in the face of widespread attacks from people who I otherwise respected. One, of course, was when I spoke out for shy nerdy males, and for a vision of feminism broad enough to recognize their suffering as a problem. A second was when I was more blunt about D-Wave, and about its and its supporters’ quantum speedup claims, than some of my colleagues were comfortable with. But the remaining occasions almost all involved my defending the values of the United States, Israel, Zionism, or “the West,” or condemning Islamic fundamentalism, radical leftism, or the worldviews of such individuals as Noam Chomsky or my “good friend” Mahmoud Ahmadinejad.
Which is simply to say: I don’t think anyone on earth can accuse me of secret sympathies for the Iranian government.
But when it comes to student visas, I can’t see that my feelings about the mullahs have anything to do with the matter. We’re talking about people who happen to have been born in Iran, who came to the US to do math and science. Would we rather have these young scientists here, filled with gratitude for the opportunities we’ve given them, or back in Iran filled with justified anger over our having expelled them?
To the Trump regime, I make one request: if you ever decide that it’s the policy of the US government to deport my PhD students, then deport me first. I’m practically begging you: come to my house, arrest me, revoke my citizenship, and tear up the awards I’ve accepted at the White House and the State Department. I’d consider that to be the greatest honor of my career.
And to those who cheered Trump’s campaign in the comments of this blog: go ahead, let me hear you defend this.
Update (Jan. 27, 2017): To everyone who’s praised the “courage” that it took me to say this, thank you so much—but to be perfectly honest, it takes orders of magnitude less courage to say this, than to say something that any of your friends or colleagues might actually disagree with! The support has been totally overwhelming, and has reaffirmed my sense that the United States is now effectively two countries, an open and a closed one, locked in a cold Civil War.
Some people have expressed surprise that I’d come out so strongly for Iranian students and researchers, “given that they don’t always agree with my politics,” or given my unapologetic support for the founding principles (if not always the actions) of the United States and of Israel. For my part, I’m surprised that they’re surprised! So let me say something that might be clarifying.
I care about the happiness, freedom, and welfare of all the men and women who are actually working to understand the universe and build the technologies of the future, and of all the bright young people who want to join these quests, whatever their backgrounds and wherever they might be found—whether it’s in Iran or Israel, in India or China or right here in the US. The system of science is far from perfect, and we often discuss ways to improve it on this blog. But I have not the slightest interest in tearing down what we have now, or destroying the world’s current pool of scientific talent in some cleansing fire, in order to pursue someone’s mental model of what the scientific community used to look like in Periclean Athens—or for that matter, their fantasy of what it would look like in a post-gender post-racial communist utopia. I’m interested in the actual human beings doing actual science who I actually meet, or hope to meet.
Understand that, and a large fraction of all the political views that I’ve ever expressed on this blog, even ones that might seem to be in tension with each other, fall out as immediate corollaries.
(Related to that, some readers might be interested in a further explanation of my views about Zionism. See also my thoughts about liberal democracy, in response to numerous comments here by Curtis Yarvin a.k.a. Mencius Moldbug a.k.a. “Boldmug.”)
Update (Jan. 29) Here’s a moving statement from my student Saeed himself, which he asked me to share here.
This is not of my best interest to talk about politics. Not because I am scared but because I know little politics. I am emotionally affected like many other fellow human beings on this planet. But I am still in the US and hopefully I can pursue my degree at MIT. But many other talented friends of mine can’t. Simply because they came back to their hometowns to visit their parents. On this matter, I must say that like many of my friends in Iran I did not have a chance to see my parents in four years, my basic human right, just because I am from a particular nationality; something that I didn’t have any decision on, and that I decided to study in my favorite school, something that I decided when I was 15. When, like many other talented friends of mine, I was teaching myself mathematics and physics hoping to make big impacts in positive ways in the future. And I must say I am proud of my nationality – home is home wherever it is. I came to America to do science in the first place. I still don’t have any other intention, I am a free man, I can do science even in desert, if I have to. If you read history you’ll see scientists even from old ages have always been traveling.
As I said I know little about many things, so I just phrase my own standpoint. You should also talk to the ones who are really affected. A good friend of mine, Ahmad, who studies Mechanical engineering in UC Berkeley, came back to visit his parents in August. He is one of the most talented students I have ever seen in my life. He has been waiting for his student visa since then and now he is ultimately depressed because he cannot finish his degree. The very least the academic society can do is to help students like Ahmad finish their degrees even if it is from abroad. I can’t emphasize enough I know little about many things. But, from a business standpoint, this is a terrible deal for America. Just think about it. All international students in this country have been getting free education untill 22, in the American point of reference, and now they are using their knowledge to build technology in the USA. Just do a simple calculation and see how much money this would amount to. In any case my fellow international students should rethink this deal, and don’t take it unless at the least they are treated with respect. Having said all of this I must say I love the people of America, I have had many great friends here, great advisors specially Scott Aaronson and Aram Harrow, with whom I have been talking about life, religion, freedom and my favorite topic the foundations of the universe. I am grateful for the education I received at MIT and I think I have something I didn’t have before. I don’t even hate Mr Trump. I think he would feel different if we have a cup of coffee sometime.
Update (Jan. 31): See also this post by Terry Tao.
Update (Feb. 2): If you haven’t been checking the comments on this post, come have a look if you’d like to watch me and others doing our best to defend the foundations of Enlightenment and liberal democracy against a regiment of monarchists and neoreactionaries, including the notorious Mencius Moldbug, as well as a guy named Jim who explicitly advocates abolishing democracy and appointing Trump as “God-Emperor” with his sons to succeed him. (Incidentally, which son? Is Ivanka out of contention?)
I find these people to be simply articulating, more clearly and logically than most, the worldview that put Trump into office and where it inevitably leads. And any of us who are horrified by it had better get over our incredulity, fast, and pick up the case for modernity and Enlightenment where Spinoza and Paine and Mill and all the others left it off—because that’s what’s actually at stake here, and if we don’t understand that then we’ll continue to be blindsided.
Happy New Year, everyone! I tripped over a well-concealed hole and sprained my ankle while carrying my daughter across the grass at Austin’s New Years festival, so am now ringing in 2017 lying in bed immobilized, which somehow seems appropriate. At least Lily is fine, and at least being bedridden gives me ample opportunity to blog.
Another year, another annual Edge question, with its opportunity for hundreds of scientists and intellectuals (including yours truly) to pontificate, often about why their own field of study is the source of the most important insights and challenges facing humanity. This year’s question was:
With the example given of Richard Dawkins’s “meme,” which jumped into the general vernacular, becoming a meme itself.
My entry, about the notion of “state” (yeah, I tried to focus on the basics), is here.
This year’s question presented a particular challenge, which scientists writing for a broad audience might not have faced for generations. Namely: to what extent, if any, should your writing acknowledge the dark shadow of recent events? Does the Putinization of the United States render your little pet debates and hobbyhorses irrelevant? Or is the most defiant thing you can do to ignore the unfolding catastrophe, to continue building your intellectual sandcastle even as the tidal wave of populist hatred nears?
In any case, the instructions from Edge were clear: ignore politics. Focus on the eternal. But people interpreted that injunction differently.
One of my first ideas was to write about the Second Law of Thermodynamics, and to muse about how one of humanity’s tragic flaws is to take for granted the gargantuan effort needed to create and maintain even little temporary pockets of order. Again and again, people imagine that, if their local pocket of order isn’t working how they want, then they should smash it to pieces, since while admittedly that might make things even worse, there’s also at least 50/50 odds that they’ll magically improve. In reasoning thus, people fail to appreciate just how exponentially more numerous are the paths downhill, into barbarism and chaos, than are the few paths further up. So thrashing about randomly, with no knowledge or understanding, is statistically certain to make things worse: on this point thermodynamics, common sense, and human history are all in total agreement. The implications of these musings for the present would be left as exercises for the reader.
Anyway, I was then pleased when, in a case of convergent evolution, my friend and hero Steven Pinker wrote exactly that essay, so I didn’t need to.
There are many other essays that are worth a read, some of which allude to recent events but the majority of which don’t. Let me mention a few.
- Nicholas Humphrey on referential opacity: while I didn’t know the term before, this is precisely the reason why, even if P=NP, that still wouldn’t imply PA=NPA for all oracles A.
- Rebecca Newberger Goldstein on scientific realism.
- Dawkins himself on “The Genetic Book of the Dead.”
- Jim Holt on invariance, and why Einstein’s real greatest blunder was to call it “relativity theory” rather than “invariant theory.” (Holt stole another of my essay ideas!)
- Sean Carroll on Bayes’ Theorem.
- Seth Lloyd on the virial theorem.
- My former algorithms professor Jon Kleinberg on digital representation.
- Peter Norvig on counting.
- Bruce Schneier on class breaks.
- Joichi Ito on neurodiversity.
- Adam Waytz on the illusion of explanatory depth.
- Brian Eno on confirmation bias (maybe the shortest entry, but one of the best!).
- Seth Shostak on Fermi problems.
- Lee Smolin on variety.
- Jennifer Jacquet on the Anthropocene.
- Abigail Marsh on alloparenting.
- Steve Omohundro on costly signalling.
- Chiara Marletto on the notion of “impossible.”
- Elizabeth Wrigley-Field on length-biased sampling.
- Carlo Rovelli on relative information.
- Raphael Bousso on the cosmological constant.
- Max Tegmark on substrate independence.
- Politically incorrect section: Greg Cochran on the breeder’s equation and Helena Cronin on sex.
- Gregory Benford on antagonistic pleiotropy.
- Richard Thaler on premortems.
- Nancy Etcoff on supernormal stimuli.
- John Tooby on coalitional instincts.
- Kurt Gray on relative deprivation.
- Jason Wilkes on functional equations (while the content was fine, the things that he strangely calls “functional equations” should really be called “axioms” or “postulates”).
- Linda Wilbrecht on sleeper sensitive periods.
Let me now discuss some disagreements I had with a few of the essays.
- Donald Hoffman on the holographic principle. For the point he wanted to make, about the mismatch between our intuitions and the physical world, it seems to me that Hoffman could’ve picked pretty much anything in physics, from Galileo and Newton onward. What’s new about holography?
- Jerry Coyne on determinism. Coyne, who’s written many things I admire, here offers his version of an old argument that I tear my hair out every time I read. There’s no free will, Coyne says, and therefore we should treat criminals more lightly, e.g. by eschewing harsh punishments in favor of rehabilitation. Following tradition, Coyne never engages the obvious reply, which is: “sorry, to whom were you addressing that argument? To me, the jailer? To the judge? The jury? Voters? Were you addressing us as moral agents, for whom the concept of ‘should’ is relevant? Then why shouldn’t we address the criminals the same way?”
- Michael Gazzaniga on “The Schnitt.” Yes, it’s possible that things like the hard problem of consciousness, or the measurement problem in quantum mechanics, will never have a satisfactory resolution. But even if so, building a complicated verbal edifice whose sole purpose is to tell people not even to look for a solution, to be satisfied with two “non-overlapping magisteria” and a lack of any explanation for how to reconcile them, never struck me as a substantive contribution to knowledge. It wasn’t when Niels Bohr did it, and it’s not when someone today does it either.
- I had a related quibble with Amanda Gefter’s piece on “enactivism”: the view she takes as her starting point, that “physics proves there’s no third-person view of the world,” is controversial to put it mildly among those who know the relevant physics. (And even if we granted that view, surely a third-person perspective exists for the quasi-Newtonian world in which we evolved, and that’s relevant for the cognitive science questions Gefter then discusses.)
- Thomas Bass on information pathology. Bass obliquely discusses the propaganda, conspiracy theories, social-media echo chambers, and unchallenged lies that helped fuel Trump’s rise. He then locates the source of the problem in Shannon’s information theory (!), which told us how to quantify information, but failed to address questions about the information’s meaning or relevance. To me, this is almost exactly like blaming arithmetic because it only tells you how to add numbers, without caring whether they’re numbers of rescued orphans or numbers of bombs. Arithmetic is fine; the problem is with us.
- In his piece on “number sense,” Keith Devlin argues that the teaching of “rigid, rule-based” math has been rendered obsolete by computers, leaving only the need to teach high-level conceptual understanding. I partly agree and partly disagree, with the disagreement coming from firsthand knowledge of just how badly that lofty idea gets beaten to mush once it filters down to the grade-school level. I would say that the basic function of math education is to teach clarity of thought: does this statement hold for all positive integers, or not? Not how do you feel about it, but does it hold? If it holds, can you prove it? What other statements would it follow from? If it doesn’t hold, can you give a counterexample? (Incidentally, there are plenty of questions of this type for which humans still outperform the best available software!) Admittedly, pencil-and-paper arithmetic is both boring and useless—but if you never mastered anything like it, then you certainly wouldn’t be ready for the concept of an algorithm, or for asking higher-level questions about algorithms.
- Daniel Hook on PT-symmetric quantum mechanics. As far as I understand, PT-symmetric Hamiltonians are equivalent to ordinary Hermitian ones under similarity transformations. So this is a mathematical trick, perhaps a useful one—but it’s extremely misleading to talk about it as if it were a new physical theory that differed from quantum mechanics.
- Jared Diamond extols the virtues of common sense, of which there are indeed many—but alas, his example is that if a mathematical proof leads to a conclusion that your common sense tells you is wrong, then you shouldn’t waste time looking for the exact mistake. Sometimes that’s good advice, but it’s pretty terrible applied to Goodstein’s Theorem, the muddy children puzzle, the strategy-stealing argument for Go, or anything else that genuinely is shocking until your common sense expands to accommodate it. Math, like science in general, is a constant dialogue between formal methods and common sense, where sometimes it’s one that needs to get with the program and sometimes it’s the other.
- Hans Halvorson on matter. I take issue with Halvorson’s claim that quantum mechanics had to be discarded in favor of quantum field theory, because QM was inconsistent with special relativity. It seems much better to say: the thing that conflicts with special relativity, and that quantum field theory superseded, was a particular application of quantum mechanics, involving wavefunctions of N particles moving around in a non-relativistic space. The general principles of QM—unit vectors in complex Hilbert space, unitary evolution, the Born rule, etc.—survived the transition to QFT without the slightest change.
OK, here’s the big entrée that I promised you yesterday:
Just to whet your appetite:
In case you’re wondering how this came about: after our mutual friend Sean Carroll introduced me and Zach for a different reason, the idea of a joint quantum computing comic just seemed too good to pass up. The basic premise—“The Talk”—was all Zach. I dutifully drafted some dialogue for him, which he then improved and illustrated. I.e., he did almost all the work (despite having a newborn competing for his attention!). Still, it was an honor for me to collaborate with one of the great visual artists of our time, and I hope you like the result. Beyond that, I’ll let the work speak for itself.
Tomorrow, I’ll have something big to announce here. So, just to whet your appetites, and to get myself back into the habit of blogging, I figured I’d offer you an appetizer course: some more miscellaneous non-Trump-related news.
(1) My former student Leonid Grinberg points me to an astonishing art form, which I somehow hadn’t known about: namely, music videos generated by executable files that fit in only 4K of memory. Some of these videos have to be seen to be believed. (See also this one.) Much like, let’s say, a small Turing machine whose behavior is independent of set theory, these videos represent exercises in applied (or, OK, recreational) Kolmogorov complexity: how far out do you need to go in the space of all computer programs before you find beauty and humor and adaptability and surprise?
Admittedly, Leonid explains to me that the rules allow these programs to call DirectX and Visual Studio libraries to handle things like the 3D rendering (with the libraries not counted toward the 4K program size). This makes the programs’ existence merely extremely impressive, rather than a sign of alien superintelligence.
In some sense, all the programming enthusiasts over the decades who’ve burned their free time and processor cycles on Conway’s Game of Life and the Mandelbrot set and so forth were captivated by the same eerie beauty showcased by the videos: that of data compression, of the vast unfolding of a simple deterministic rule. But I also feel like the videos add a bit extra: the 3D rendering, the music, the panning across natural or manmade-looking dreamscapes. What we have here is a wonderful resource for either an acid trip or an undergrad computability and complexity course.
(2) A week ago Igor Oliveira, together with my longtime friend Rahul Santhanam, released a striking paper entitled Pseudodeterministic Constructions in Subexponential Time. To understand what this paper does, let’s start with Terry Tao’s 2009 polymath challenge: namely, to find a fast, deterministic method that provably generates large prime numbers. Tao’s challenge still stands today: one of the most basic, simplest-to-state unsolved problems in algorithms and number theory.
To be clear, we already have a fast deterministic method to decide whether a given number is prime: that was the 2002 breakthrough by Agrawal, Kayal, and Saxena. We also have a fast probabilistic method to generate large primes: namely, just keep picking n-digit numbers at random, test each one, and stop when you find one that’s prime! And those methods can be made deterministic assuming far-reaching conjectures in number theory, such as Cramer’s Conjecture (though note that even the Riemann Hypothesis wouldn’t lead to a polynomial-time algorithm, but “merely” a faster exponential-time one).
But, OK, what if you want a 5000-digit prime number, and you want it now: provably, deterministically, and fast? That was Tao’s challenge. The new paper by Oliveira and Santhanam doesn’t quite solve it, but it makes some exciting progress. Specifically, it gives a deterministic algorithm to generate n-digit prime numbers, with merely the following four caveats:
- The algorithm isn’t polynomial time, but subexponential (2n^o(1)) time.
- The algorithm isn’t deterministic, but pseudodeterministic (a concept introduced by Gat and Goldwasser). That is, the algorithm uses randomness, but it almost always succeeds, and it outputs the same n-digit prime number in every case where it succeeds.
- The algorithm might not work for all input lengths n, but merely for infinitely many of them.
- Finally, the authors can’t quite say what the algorithm is—they merely prove that it exists! If there’s a huge complexity collapse, such as ZPP=PSPACE, then the algorithm is one thing, while if not then the algorithm is something else.
Strikingly, Oliveira and Santhanam’s advance on the polymath problem is pure complexity theory: hitting sets and pseudorandom generators and win-win arguments and stuff like that. Their paper uses absolutely nothing specific to the prime numbers, except the facts that (a) there are lots of them (the Prime Number Theorem), and (b) we can efficiently decide whether a given number is prime (the AKS algorithm). It seems almost certain that one could do better by exploiting more about primes.
(3) I’m in Lyon, France right now, to give three quantum computing and complexity theory talks. I arrived here today from London, where I gave another two lectures. So far, the trip has been phenomenal, my hosts gracious, the audiences bristling with interesting questions.
But getting from London to Lyon also taught me an important life lesson that I wanted to share: never fly EasyJet. Or at least, if you fly one of the European “discount” airlines, realize that you get what you pay for (I’m told that Ryanair is even worse). These airlines have a fundamentally dishonest business model, based on selling impossibly cheap tickets, but then forcing passengers to check even tiny bags and charging exorbitant fees for it, counting on snagging enough travelers who just naïvely clicked “yes” to whatever would get them from point A to point B at a certain time, assuming that all airlines followed more-or-less similar rules. Which might not be so bad—it’s only money—if the minuscule, overworked staff of these quasi-airlines didn’t also treat the passengers like beef cattle, barking orders and berating people for failing to obey rules that one could log hundreds of thousands of miles on normal airlines without ever once encountering. Anyway, if the airlines won’t warn you, then Shtetl-Optimized will.
Two years ago, when I was the target of an online shaming campaign, what helped me through it were hundreds of messages of support from friends, slight acquaintances, and strangers of every background. I vowed then to return the favor, by standing up when I saw decent people unfairly shamed. Today I have an opportunity to make good.
Some time ago I had the privilege of interacting a bit with Sam Altman, president of the famed startup incubator Y Combinator (and a guy who’s thanked in pretty much everything Paul Graham writes). By way of our mutual friend, the renowned former quantum computing researcher Michael Nielsen, Sam got in touch with me to solicit suggestions for “outside-the-box” scientists and writers, for a new grant program that Y Combinator was starting. I found Sam eager to delve into the merits of any suggestion, however outlandish, and was delighted to be able to make a difference for a few talented people who needed support.
Sam has also been one of the Silicon Valley leaders who’s written most clearly and openly about the threat to America posed by Donald Trump and the need to stop him, and he’s donated tens of thousands of dollars to anti-Trump causes. Needless to say, I supported Sam on that as well.
Now Sam is under attack on social media, and there are even calls for him to resign as the president of Y Combinator. Like me two years ago, Sam has instantly become the corporeal embodiment of the “nerd privilege” that keeps the marginalized out of Silicon Valley.
Why? Because, despite his own emphatic anti-Trump views, Sam rejected demands to fire Peter Thiel (who has an advisory role at Y Combinator) because of Thiel’s support for Trump. Sam explained his reasoning at some length:
[A]s repugnant as Trump is to many of us, we are not going to fire someone over his or her support of a political candidate. As far as we know, that would be unprecedented for supporting a major party nominee, and a dangerous path to start down (of course, if Peter said some of the things Trump says himself, he would no longer be part of Y Combinator) … The way we got into a situation with Trump as a major party nominee in the first place was by not talking to people who are very different than we are … I don’t understand how 43% of the country supports Trump. But I’d like to find out, because we have to include everyone in our path forward. If our best ideas are to stop talking to or fire anyone who disagrees with us, we’ll be facing this whole situation again in 2020.
The usual criticism of nerds is that we might have narrow technical abilities, but we lack wisdom about human affairs. It’s ironic, then, that it appears to have fallen to Silicon Valley nerds to guard some of the most important human wisdom our sorry species ever came across—namely, the liberal ideals of the Enlightenment. Like Sam, I despise pretty much everything Trump stands for, and I’ve been far from silent about it: I’ve blogged, donated money, advocated vote swapping, endured anonymous comments like “kill yourself kike”—whatever seemed like it might help even infinitesimally to ensure the richly-deserved electoral thrashing that Trump mercifully seems to be headed for in a few weeks.
But I also, I confess, oppose the forces that apparently see Trump less as a global calamity to be averted, than as a golden opportunity to take down anything they don’t like that’s ever been spotted within a thousand-mile radius of Trump Tower. (Where does this Kevin Bacon game end, anyway? Do “six degrees of Trump” suffice to contaminate you?)
And not only do I not feel a shadow of a hint of a moral conflict here, but it seems to me that precisely the same liberal Enlightenment principles are behind both of these stances.
But I’d go yet further. It sort of flabbergasts me when social-justice activists don’t understand that, if we condemn not only Trump, not only his supporters, but even vociferous Trump opponents who associate with Trump supporters (!), all we’ll do is feed the narrative that got Trumpism as far as it has—namely, that of a smug, bubble-encased, virtue-signalling leftist elite subject to runaway political correctness spirals. Like, a hundred million Americans’ worldviews revolve around the fear of liberal persecution, and we’re going to change their minds by firing anyone who refuses to fire them? As a recent Washington Post story illustrates, the opposite approach is harder but can bear spectacular results.
Now, as for Peter Thiel: three years ago, he funded a small interdisciplinary workshop on the coast of France that I attended. With me there were a bunch of honest-to-goodness conservative Christians, a Freudian psychoanalyst, a novelist, a right-wing radio host, some scientists and Silicon Valley executives, and of course Thiel himself. Each, I found, offered tons to disagree about but also some morsels to learn.
Thiel’s worldview, focused on the technological and organizational greatness that (in his view) Western civilization used to have and has subsequently lost, was a bit too dark and pessimistic for me, and I’m a pretty dark and pessimistic person. Thiel gave a complicated, meandering lecture that involved comparing modern narratives about Silicon Valley entrepreneurs against myths of gods, heroes, and martyrs throughout history, such as Romulus and Remus (the legendary founders of Rome). The talk might have made more sense to Thiel than to his listeners.
At the same time, Thiel’s range of knowledge and curiosity was pretty awesome. He avidly followed all the talks (including mine, on P vs. NP and quantum complexity theory) and asked pertinent questions. When the conversation turned to D-Wave, and Thiel’s own decision not to invest in it, he laid out the conclusions he’d come to from an extremely quick look at the question, then quizzed me as to whether he’d gotten anything wrong. He hadn’t.
From that conversation among others, I formed the impression that Thiel’s success as an investor is, at least in part, down neither to luck nor to connections, but to a module in his brain that most people lack, which makes blazingly fast and accurate judgments about tech startups. No wonder Y Combinator would want to keep him as an adviser.
But, OK, I’m so used to the same person being spectacularly right on some things and spectacularly wrong on others, that it no longer causes even slight cognitive dissonance. You just take the issues one by one.
I was happy, on balance, when it came out that Thiel had financed the lawsuit that brought down Gawker Media. Gawker really had used its power to bully the innocent, and it had broken the law to do it. And if it’s an unaccountable, anti-egalitarian, billionaire Godzilla against a vicious, privacy-violating, nerd-baiting King Kong—well then, I guess I’m with Godzilla.
More recently, I was appalled when Thiel spoke at the Republican convention, pandering to the crowd with Fox-News-style attack lines that were unworthy of a mind of his caliber. I lost a lot of respect for Thiel that day. But that’s the thing: unlike with literally every other speaker at the GOP convention, my respect for Thiel had started from a point that made a decrease possible.
I reject huge parts of Thiel’s worldview. I also reject any worldview that would threaten me with ostracism for talking to Thiel, attending a workshop he sponsors, or saying anything good about him. This is not actually a difficult balance.
Today, when it sometimes seems like much of the world has united in salivating for a cataclysmic showdown between whites and non-whites, Christians and Muslims, “dudebros” and feminists, etc., and that the salivators differ mostly just in who they want to see victorious in the coming battle and who humiliated, it can feel lonely to stick up for naïve, outdated values like the free exchange of ideas, friendly disagreement, the presumption of innocence, and the primacy of the individual over the tribe. But those are the values that took us all the way from a bronze spear through the enemy’s heart to a snarky rebuttal on the arXiv, and they’ll continue to build anything worth building.
And now to watch the third debate (I’ll check the comments afterward)…
Update (Oct. 20): See also this post from a blog called TheMoneyIllusion. My favorite excerpt:
So let’s see. Not only should Trump be shunned for his appalling political views, an otherwise highly respected Silicon Valley entrepreneur who just happens to support Trump (along with 80 million other Americans) should also be shunned. And a person who despises Trump and works against him but who defends Thiel’s right to his own political views should also resign. Does that mean I should be shunned too? After all, I’m a guy who hates Trump, writing a post that defends a guy who hates Trump, who wrote a post defending a guy’s freedom to support Trump, who in turn supports Trump. And suppose my mother sticks up for me? Should she also be shunned?
It’s almost enough to make me vote . . . no, just kidding.
Question … Which people on the left are beyond the pale? Suppose Thiel had supported Hugo Chavez? How about Castro? Mao? Pol Pot? Perhaps the degrees of separation could be calibrated to the awfulness of the left-winger:
Chavez: One degree of separation. (Corbyn, Sean Penn, etc.)
Castro: Two degrees of separation is still toxic.
Lenin: Three degrees of separation.
Mao: Four degrees of separation.
Pol Pot: Five degrees of separation.
Updates: Commenter JT informs me that there’s already a vote-swapping site available: MakeMineCount.org. (I particularly like their motto: “Everybody wins. Except Trump.”) I still think there’s a need for more sites, particularly ones that would interface with Facebook, but this is a great beginning. I’ve signed up for it myself.
Also, Toby Ord, a philosopher I know at Oxford, points me to a neat academic paper he wrote that analyzes vote-swapping as an example of “moral trade,” and that mentions the Porter v. Bowen decision holding vote-swapping to be legal in the US.
Also, if we find two Gary Johnson supporters in swing states willing to trade, I’ve been contacted by a fellow Austinite who’d be happy to accept the second trade.
As regular readers might know, my first appearance in the public eye (for a loose definition of “public eye”) had nothing to do with D-Wave, Gödel’s Theorem, the computational complexity of quantum gravity, Australian printer ads, or—god forbid—social justice shaming campaigns. Instead it centered on NaderTrading: the valiant but doomed effort, in the weeks leading up to the 2000 US Presidential election, to stop George W. Bush’s rise to power by encouraging Ralph Nader supporters in swing states (such as Florida) to vote for Al Gore, while pairing themselves off over the Internet with Gore supporters in safe states (such as Texas or California) who would vote for Nader on their behalf. That way, Nader’s vote share (and his chance of reaching 5% of the popular vote, which would’ve qualified him for federal funds in 2004) wouldn’t be jeopardized, but neither would Gore’s chance of winning the election.
Here’s what I thought at the time:
- The election would be razor-close (though I never could’ve guessed how close).
- Bush was a malignant doofus who would be a disaster for the US and the world (though I certainly didn’t know how—recall that, at the time, Bush was running as an isolationist).
- Many Nader supporters, including the ones who I met at Berkeley, prioritized personal virtue so completely over real-world consequences that they might actually throw the election to Bush.
NaderTrading, as proposed by law professor Jamin Raskin and others, seemed like one of the clearest ways for nerds who knew these points, but who lacked political skills, to throw themselves onto the gears of history and do something good for the world.
So, as a 19-year-old grad student, I created a website called “In Defense of NaderTrading” (archived version), which didn’t arrange vote swaps themselves—other sites did that—but which explored some of the game theory behind the concept and answered some common objections to it. (See also here.) Within days of creating the site, I’d somehow become an “expert” on the topic, and was fielding hundreds of emails as well as requests for print, radio, and TV interviews.
Alas, the one question everyone wanted to ask me was the one that I, as a CS nerd, was the least qualified to answer: is NaderTrading legal? isn’t it kind of like … buying and selling votes?
I could only reply that, to my mind, NaderTrading obviously ought to be legal, because:
- Members of Congress and state legislatures trade votes all the time.
- A private agreement between two friends to each vote for the other’s preferred candidate seems self-evidently legal, so why should it be any different if a website is involved?
- The whole point of NaderTrading is to exercise your voting power more fully—pretty much the opposite of bartering it away for private gain.
- While the election laws vary by state, the ones I read very specifically banned trading votes for tangible goods—they never even mentioned trading votes for other votes, even though they easily could’ve done so had legislators intended to ban that.
But—and here was the fatal problem—I could only address principles and arguments, rather than politics and power. I couldn’t honestly assure the people who wanted to vote-swap, or to set up vote-swapping sites, that they wouldn’t be prosecuted for it.
As it happened, the main vote-swapping site, voteswap2000.com, was shut down by California’s Republican attorney general, Bill Jones, only four days after it opened. A second vote-swapping site, votexchange.com, was never directly threatened but also ceased operations because of what happened to voteswap2000. Many legal scholars felt confident that these shutdowns wouldn’t hold up in court, but with just a few weeks until the election, there was no time to fight it.
Before it was shut down, voteswap2000 had brokered 5,041 vote-swaps, including hundreds in Florida. Had that and similar sites been allowed to continue operating, it’s entirely plausible that they would’ve changed the outcome of the election. No Iraq war, no 2008 financial meltdown: we would’ve been living in a different world. Note that, of the 100,000 Floridians who ultimately voted for Nader, we would’ve needed to convince fewer than 1% of them.
Today, we face something I didn’t expect to face in my lifetime: namely, a serious prospect of a takeover of the United States by a nativist demagogue with open contempt for democratic norms and legendarily poor impulse control. Meanwhile, there are two third-party candidates—Gary Johnson and Jill Stein—who together command 10% of the vote. A couple months ago, I’d expressed hopes that Johnson might help Hillary, by splitting the Republican vote. But it now looks clear that, on balance, not only Stein but also Johnson are helping Trump, by splitting up that part of the American vote that’s not driven by racial resentment.
So recently a friend—the philanthropist and rationalist Holden Karnofsky—posed a question to me: should we revive the vote-swapping idea from 2000? And presumably this time around, enhance the idea with 21st-century bells and whistles like mobile apps and Facebook, to make it all the easier for Johnson/Stein supporters in swing states and Hillary supporters in safe states to find each other and trade votes?
Just like so many well-meaning people back in 2000, Holden was worried about one thing: is vote-swapping against the law? If someone created a mobile vote-swapping app, could that person be thrown in jail?
At first, I had no idea: I assumed that vote-swapping simply remained in the legal Twilight Zone where it was last spotted in 2000. But then I did something radical: I looked it up. And when I did, I discovered a decade-old piece of news that changes everything.
On August 6, 2007, the Ninth Circuit Court of Appeals finally ruled on a case, Porter v. Bowen, stemming from the California attorney general’s shutdown of voteswap2000.com. Their ruling, which is worth reading in full, was unequivocal.
Vote-swapping, it said, is protected by the First Amendment, which state election laws can’t supersede. It is fundamentally different from buying or selling votes.
Yes, the decision also granted the California attorney general immunity from prosecution, on the ground that vote-swapping’s legality hadn’t yet been established in 2000—indeed it wouldn’t be, until the Ninth Circuit’s decision itself! Nevertheless, the ruling made clear that the appellants (the creators of voteswap2000 and some others) were granted the relief they sought: namely, an assurance that vote-swapping websites would be protected from state interference in the future.
Admittedly, if vote-swapping takes off again, it’s possible that the question will be re-litigated and will end up in the Supreme Court, where the Ninth Circuit’s ruling could be reversed. For now, though, let the message be shouted from the rooftops: a court has ruled. You cannot be punished for cooperating with your fellow citizens to vote strategically, or for helping others do the same.
For those of you who oppose Donald Trump and who are good at web and app development: with just two months until the election, I think the time to set up some serious vote-swapping infrastructure is right now. Let your name be etched in history, alongside those who stood up to all the vicious demagogues of the past. And let that happen without your even needing to get up from your computer chair.
I’m not, I confess, a huge fan of either Gary Johnson or Jill Stein (especially not Stein). Nevertheless, here’s my promise: on November 8, I will cast my vote in the State of Texas for Gary Johnson, if I can find at least one Johnson supporter who lives in a swing state, who I feel I can trust, and who agrees to vote for Hillary Clinton on my behalf.
If you think you’ve got what it takes to be my vote-mate, send me an email, tell me about yourself, and let’s talk! I’m not averse to some electoral polyamory—i.e., lots of Johnson supporters in swing states casting their votes for Clinton, in exchange for the world’s most famous quantum complexity blogger voting for Johnson—but I’m willing to settle for a monogamous relationship if need be.
And as for Stein? I’d probably rather subsist on tofu than vote for her, because of her support for seemingly every pseudoscience she comes across, and especially because of her endorsement of the vile campaign to boycott Israel. Even so: if Stein supporters in swing states whose sincerity I trusted offered to trade votes with me, and Johnson supporters didn’t, I would bury my scruples and vote for Stein. Right now, the need to stop the madman takes precedence over everything else.
One last thing to get out of the way. When they learn of my history with NaderTrading, people keep pointing me a website called BalancedRebellion.com, and exclaiming “look! isn’t this exactly that vote-trading thing you were talking about?”
On examination, Balanced Rebellion turns out to be the following proposal:
- A Trump supporter in a swing state pairs off with a Hillary supporter in a swing state.
- Both of them vote for Gary Johnson, thereby helping Johnson without giving an advantage to either Hillary or Trump.
So, exercise for the reader: see if you can spot the difference between this idea and the kind of vote-swapping I’m talking about. (Here’s a hint: my version helps prevent a racist lunatic from taking command of the most powerful military on earth, rather than being neutral about that outcome.)
Not surprisingly, the “balanced rebellion” is advocated by Johnson fans.
Sorry for a post-free month. I was completely preoccupied with the logistics of the move to Texas. But now that I’m finally more-or-less settled on my 1000-acre cattle ranch, with my supply of shotguns and whiskey, I’ve decided to ease myself gently back into blogging, via Shtetl-Optimized‘s first-ever SlateStarCodex-style “Open Thread.” This is not an Ask Me Anything thread. Rather, it’s a thread for you, the readers, to ask each other whatever you want or bring up any topic on your mind. I’ll chime in occasionally, and will moderate if needed. No personal attacks or local hidden variable theories, please.