{"id":3054,"date":"2016-12-13T20:07:09","date_gmt":"2016-12-14T01:07:09","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=3054"},"modified":"2017-01-12T09:09:36","modified_gmt":"2017-01-12T14:09:36","slug":"the-teaser","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=3054","title":{"rendered":"The teaser"},"content":{"rendered":"

Tomorrow, I’ll have something big<\/strong> to announce here. \u00a0So, 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.<\/p>\n

\n

(1) My former student Leonid Grinberg points me to an astonishing\u00a0art form, which I somehow hadn’t known about: namely, music videos generated by executable files\u00a0that fit in only 4K of memory. \u00a0Some of these videos have to be seen to be believed<\/a>. \u00a0(See also this one<\/a>.) \u00a0Much like, let’s say, a\u00a0small Turing machine whose behavior is independent of set theory<\/a>, these videos represent exercises\u00a0in applied (or, OK, recreational) Kolmogorov complexity<\/a>: how\u00a0far out do you need to go in the space of all computer programs before you find\u00a0beauty and humor and adaptability\u00a0and surprise?<\/p>\n

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). \u00a0This makes the programs’ existence merely<\/em>\u00a0extremely impressive, rather than a sign of alien superintelligence.<\/p>\n

In some sense, all the programming enthusiasts over the decades who’ve burned their free time and processor\u00a0cycles on Conway’s Game of Life<\/a> and the Mandelbrot set<\/a> and so forth were captivated by the same eerie beauty showcased by the videos: that of data compression,\u00a0of the vast unfolding of a simple deterministic rule. \u00a0But I also feel like the videos add a bit\u00a0extra: the 3D rendering, the music, the panning across natural or manmade-looking dreamscapes. \u00a0What we have here is a wonderful resource for either an acid trip or\u00a0an undergrad computability and complexity course.<\/p>\n

\n

(2) A week ago Igor Oliveira, together with my longtime friend Rahul Santhanam, released a striking paper entitled\u00a0Pseudodeterministic Constructions in Subexponential Time<\/a>. \u00a0To understand what this paper does, let’s start with Terry Tao’s 2009 polymath challenge<\/a>: namely, to find\u00a0a fast, deterministic method that provably generates large prime numbers<\/em>. \u00a0Tao’s challenge still stands today:\u00a0one of the most basic, simplest-to-state\u00a0unsolved problems in\u00a0algorithms and number theory.<\/p>\n

To be clear, we already have a fast deterministic method to decide whether a given<\/em> number is prime: that was the 2002 breakthrough by\u00a0Agrawal, Kayal, and Saxena<\/a>. \u00a0We also have a fast probabilistic<\/em> method to\u00a0generate<\/em> large primes: namely, just keep picking n-digit numbers at random, test each one, and stop when you find one that’s prime! \u00a0And those methods can be made deterministic assuming far-reaching conjectures in number theory, such as Cramer’s Conjecture<\/a> (though note that even the Riemann Hypothesis<\/a> wouldn’t lead to\u00a0a polynomial-time algorithm, but “merely” a faster exponential-time one).<\/p>\n

But, OK, what if you want a 5000-digit prime number, and you want it now<\/em>: provably, deterministically, and fast? \u00a0That was Tao’s challenge. \u00a0The new paper by Oliveira and Santhanam doesn’t quite\u00a0solve it, but it makes some exciting progress. \u00a0Specifically, it gives a deterministic algorithm to generate n-digit prime numbers, with merely the following four caveats:<\/p>\n