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.
Follow