### Stuff That’s Happened

Sunday, October 9th, 2016Hi from FOCS’2016 in scenic New Brunswick, NJ! (I just got here from Avi Wigderson’s 60th birthday conference, to which I’ll devote another post.)

In the few weeks since I last overcame the activation barrier to blog, here are some things that happened.

**Politics**

Friday’s revelation, of Trump boasting on tape to George W. Bush’s cousin about his crotch-grabbing escapades, did not increase my opposition to Trump, for a very simple reason: because I’d already opposed Trump by the maximum amount that’s possible. Nevertheless, I’ll be gratified if this news brings Trump down, and leads to the landslide defeat he’s deserved from the beginning for 10^{1000} reasons.

Still, history (including the history of this election) teaches us not to take things for granted. So if you’re *still* thinking of voting for Trump, let me recommend Scott Alexander’s endorsement of “anyone but Trump.” I’d go even further than my fellow Scott A. in much of what he says, but his post is nevertheless a masterful document, demonstrating how someone who *nobody* could accuse of being a statist social-justice warrior, but who “merely” has a sense for science and history and Enlightenment ideals and the ironic and absurd, can reach the conclusion that Trump had better be stopped, and with huge argumentative margin to spare.

See also an interview with me on *Huffington Post* about TrumpTrading, conducted by Linchuan Zhang. If you live in a swing state and support Johnson, or in a safe state and support Hillary, I still recommend signing up, since even a 13% probability of a Trump win is too high. I’ve found a partner in Ohio, a libertarian-leaning professor. The only way I can foresee not going through with the swap, is if the bus tape causes Trump’s popularity to drop so precipitously that *Texas* becomes competitive.

In the meantime, it’s also important that we remain vigilant about the integrity of the election—not about in-person voter fraud, which statistically doesn’t exist, but about intimidation at the polls and the purging of eligible voters and tampering with electronic voting machines. As I’ve mentioned before on this blog, my childhood friend Alex Halderman, now a CS professor at the University of Michigan, has been at the forefront of demonstrating the security problems with electronic voting machines, and advocating for paper trails. Alex and his colleagues have actually succeeded in influencing how elections are conducted in many states—but not in all of them. If you want to learn more, check out an in-depth profile of Alex in the latest issue of *Playboy*. (There’s no longer nudity in *Playboy*, so you can even read the thing at work…)

**Now On To SCIENCE**

As some of you probably saw, Mohammad Bavarian, Giulio Gueltrini, and I put out a new paper about computability theory in a universe with closed timelike curves. This complements my and John Watrous’s earlier work about *complexity* theory in a CTC universe, where we showed that finding a fixed-point of a bounded superoperator is a PSPACE-complete problem. In the new work, we show that finding a fixed-point of an *un*bounded superoperator has the same difficulty as the halting problem.

Some of you will also have seen that folks from the Machine Intelligence Research Institute (MIRI)—Scott Garrabrant, Tsvi Benson-Tilsen, Andrew Critch, Nate Soares, and Jessica Taylor—recently put out a major 130-page paper entitled “Logical Induction”. (See also their blog announcement.) This paper takes direct aim at a question that’s come up repeatedly in the comments section of this blog: namely, how can we sensibly assign probabilities to mathematical statements, such as “the 10^{10^1000}th decimal digit of π is a 3″? The paper proposes an essentially *economic* framework for that question, involving a marketplace for “mathematical truth futures,” in which new mathematical truths get revealed one by one, and one doesn’t want any polynomial-time traders to be able to make an infinite amount of money by finding patterns in the truths that the prices haven’t already factored in. I won’t be able to do justice to the work in this paragraph (or even come close), but I hope this sophisticated paper gets the attention it deserves from mathematicians, logicians, CS theorists, AI people, economists, and anyone else who’s ever wondered how a “Bayesian” could sleep at night after betting on (say) the truth or falsehood of Goldbach’s Conjecture. Feel free to discuss in the comments section.

My PhD student Adam Bouland and former visiting student Lijie Chen, along with Dhiraj Holden, Justin Thaler, and Prashant Vasudevan, have put out a new paper that achieves an oracle separation between the complexity classes SZK and PP (among many other things)—thereby substantially generalizing my quantum lower bound for the collision problem, and solving an open problem that I’d thought about without success since 2002. Huge relativized congratulations to them!

A new paper by my PhD student Shalev Ben-David and Or Sattath, about using ideas from quantum money to create signed quantum tokens, has been making the rounds on social media. Why? Read the abstract and see for yourself! (My only “contribution” was to tell them not to change a word.)

Several people wrote in to tell me about a recent paper by Henry Lin and Max Tegmark, which tries to use physics analogies and intuitions to explain why deep learning works as well as it does. To my inexpert eyes, the paper seemed to contain a lot of standard insights from computational learning theory (for example, the need to exploit symmetries and regularities in the world to get polynomial-size representations), but expressed in a different language. What confused me most was the paper’s claim to prove “no-flattening theorems” showing the necessity of large-depth neural networks—since in the sense I would mean, such a theorem couldn’t possibly be proved without a major breakthrough in computational complexity (e.g., separating the levels of the class TC^{0}). Again, anyone who understands what’s going on is welcome to share in the comments section.

Sevag Gharibian asked me to advertise that the Call for Papers for the 2017 Conference on Computational Complexity, to be held July 6-9 in Riga, Latvia, is now up.