Important Announcement: I don’t in any way endorse voting for Jill Stein, or any other third-party candidate. But if you are a Green Party supporter who lives in a swing state, then please at least vote for Harris, and use SwapYourVote.org to arrange for two (!) people in safe states to vote for Jill Stein […]
I was sure my next post would be about the election—the sword of Damocles hanging over the United States and civilization as a whole. Instead, I have sad news, but also news that brings memories of warmth, humor, and complexity-theoretic insight. Steven Rudich—professor at Carnegie Mellon, central figure of theoretical computer science since the...
Yes, he’s the guy from The Elegant Universe book and TV series. Our conversation is 1 hour 40 minutes; as usual I strongly recommend listening at 2x speed. The topics, chosen by Brian, include quantum computing (algorithms, hardware, error-correction … the works), my childhood, the interpretation of quantum mechanics, the current state of AI, the...
In nearly twenty years of blogging, I’ve unfortunately felt more and more isolated and embattled. It now feels like anything I post earns severe blowback, from ridicule on Twitter, to pseudonymous comment trolls, to scary and aggressive email bullying campaigns. Reflecting on this, though, I came to see that such strong reactions are an...
For weeks I agonized over what, if anything, this post should say. How does one commemorate a tragedy that isn’t over for millions of innocents on either side? How do I add to what friend-of-the-blog Boaz Barak and countless others have already written? Do I review the grisly details of Black Shabbat, tell the stories […]
The other night I spoke at a quantum computing event and was asked—for the hundredth time? the thousandth?—whether I agreed that the quantum algorithm called QAOA was poised revolutionize industries by finding better solutions to NP-hard optimization problems. I replied that while serious, worthwhile research on that algorithm continues, alas, so...
Many of you will have seen the news that Governor Gavin Newsom has vetoed SB 1047, the groundbreaking AI safety bill that passed the California legislature. Newsom gave a disingenuous explanation (which no one on either side of the debate took seriously), that he vetoed the bill only because it didn’t go far enough (!!) […]
Today is the day I became radicalized in my Jewish and Zionist identities. Uhhh, you thought that had already happened? Like maybe in the aftermath of October 7, or well before then? Hahahaha no. You haven’t seen nothin’ yet. See, a couple days ago, I was consoling myself on Facebook that, even as the arts […]
So, back in June the White House announced that UCLA would host a binational US/India workshop, for national security officials from both countries to learn about the current status of quantum computing and post-quantum cryptography. It fell to me my friend and colleague Rafail Ostrovsky to organize the workshop, which ended up being held last […]
In the comments of my last post—on a podcast conversation between me and Dan Fagella—I asked whether readers wanted me to use AI to prepare a clean written transcript of the conversation, and several people said yes. I’ve finally gotten around to doing that, using GPT-4o. The main thing I learned from the experience is […]
Dan Faggella recorded an unusual podcast with me that’s now online. He introduces me as a “quantum physicist,” which is something that I never call myself (I’m a theoretical computer scientist) but have sort of given up on not being called by others. But the ensuing 85-minute conversation has virtually nothing to do with physics, […]
Between roughly 2001 and 2018, I’ve happy to have done some nice things in quantum computing theory, from the quantum lower bound for the collision problem to the invention of shadow tomography. I hope that’s not the end of it. QC research brought me about as much pleasure as anything in life did. So I […]
I’ve finished my two-year leave at OpenAI, and returned to being just a normal (normal?) professor, quantum complexity theorist, and blogger. Despite the huge drama at OpenAI that coincided with my time there, including the departures of most of the people I worked with, I’m incredibly grateful to OpenAI for giving me an opportunity to […]
Pedro Domingos is a computer scientist at the University of Washington. I’ve known him for years as a guy who’d confidently explain to me why I was wrong about everything from physics to CS to politics … but then, for some reason, ask to meet with me again. Over the past 6 or 7 years, […]
This morning I was pondering one of the anti-Israel protesters’ favorite phrases—I promise, out of broad philosophical curiosity rather than just parochial concern for my extended family’s survival. “We’re on the right side of history. Don’t put yourself on the wrong side by opposing us.” Why do the protesters believe they shouldn’t face legal or...
Want some honesty about how I (mis)spend my time? These days, my daily routine includes reading all of the following: Many of these materials contain lists of links to other articles, or tweet threads, some of which then take me hours to read in themselves. This is not counting podcasts or movies or TV shows. […]
Back in May, I had the honor (nay, honour) to speak at HowTheLightGetsIn, an ideas festival held annually in Hay-on-Wye on the English/Welsh border. It was my first time in that part of the UK, and I loved it. There was an immense amount of mud due to rain on the festival ground, and many […]
Q1: Who will you be voting for in November? A: Kamala Harris (and mainstream Democrats all down the ballot), of course. Q2: Of course? A: If the alternative is Trump, I would’ve voted for Biden’s rotting corpse. Or for Hunter Biden. Or for… Q3: Why can’t you see this is just your Trump Derangement Syndrome […]
Update (July 24): Remember the quest that Adam Yedidia and I started in 2016, to find the smallest n such that the value of the nth Busy Beaver number can be proven independent of the axioms of ZF set theory? We managed to show that BB(8000) was independent. This was later improved to BB(745) by […]
It is the duty of good people, always and everywhere, to condemn, reject, and disavow the use of political violence. Even or especially when evildoers would celebrate the use of political violence against us. It is our duty always to tell the truth, always to play by the rules — even when evil triumphs by […]
Perhaps like the poor current President of the United States, I can feel myself fading, my memory and verbal facility and attention to detail failing me, even while there’s so much left to do to battle the nonsense in the world. I started my career on an accelerated schedule—going to college at 15, finishing my […]
In Michael Sipser’s Introduction to the Theory of Computation textbook, he has one Platonically perfect homework exercise, so perfect that I can reconstruct it from memory despite not having opened the book for over a decade. It goes like this: The correct answer is that yes, f is computable. Why? Because the constant 1 function […]
The news these days feels apocalyptic to me—as if we’re living through, if not the last days of humanity, then surely the last days of liberal democracy on earth. All the more reason to ignore all of that, then, and blog instead about the notorious Busy Beaver function! Because holy moly, what news have I […]
Dana, the kids, and I got back to the US last week after a month spent in England and then Israel. We decided to visit Israel because … uhh, we heard there’s never been a better time. We normally go every year to visit Dana’s family and our many friends there, and to give talks. […]
(See here for Boaz Barak’s obituary, and here for Lance Fortnow’s—they cover different aspects of Luca’s legacy from each other and from this post. Also, click here to register for a free online TCS4All talk that Luca was scheduled to give, and that will now be given in his memory, this Monday at 3:30pm Eastern […]