The teaser
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
Comment #1 December 13th, 2016 at 8:35 pm
Just a guess: taking a position in the Trump cabinet.
Comment #2 December 13th, 2016 at 8:47 pm
Hal #1: How’d you guess?? Yes, Secretary of Agriculture. But that’s not what I was planning to announce tomorrow, just an unrelated development.
Comment #3 December 13th, 2016 at 8:51 pm
Scott Aaronson to appear in Super Smash Bros. for the Nintendo Switch, you heard it here first! 😛
Comment #4 December 13th, 2016 at 9:18 pm
Is that problem reducible to factoring?
For example, is it possible to pick a polynomial-sized set of sufficiently huge integers such that at least one is guaranteed to have a factor larger than some value?
If not, isn’t that strange given that factoring is expected to be outside of P?
Comment #5 December 13th, 2016 at 9:28 pm
Now I’m even more intrigued. Looking forward to tomorrow’s announcement, Professor Secretary-Designate.
P.S. What’s the word in France? There’s a good chance they’ll soon elect their own Trump-like populist, so curious if academics are all rilled up or if it’s like “N’importe quoi.”
Comment #6 December 13th, 2016 at 9:54 pm
Quantum supremacy?
Comment #7 December 13th, 2016 at 9:58 pm
Does it have to do with lattices? (To preserve the surprise, you don’t have to answer unless the answer is “no.”)
Comment #8 December 13th, 2016 at 10:04 pm
Wait so are you saying the Oliveira and Santhanam approach will prove the existence of an algorithm generate large member of any set in NP that is dense “enough” among strings of a given length?
Are there such sets where we do know a poly time fully deterministic method of generating members? I guess sets in P but any not know to be in P? Seems like the Delta in time between a specific algorithm and the general one that exists is an interesting quantitative measure of how much we understand the set…
Comment #9 December 13th, 2016 at 10:08 pm
Hypothetically, if you were offered the position of Secretary of Energy, would you feel obligated to take it?
Comment #10 December 13th, 2016 at 11:05 pm
4k for those things is also less impressive if you ever used a Vic-20.
Comment #11 December 14th, 2016 at 12:02 am
I enjoyed easyjet when I flew with them (they let me have a carry-on, though, either because it was a few years ago or because it was a longer flight).
Number Theory thing is awesome. It falls into that weird category where proving something with more caveats is somehow more impressive (maybe because those caveats give you something on the fundamental structures involved?)
Comment #12 December 14th, 2016 at 1:15 am
https://arxiv.org/abs/1612.04208 ?
Comment #13 December 14th, 2016 at 2:31 am
Job #4: No, I don’t see any reduction from prime generation to factoring, or even a sketch of how one would work. Interesting question though.
Comment #14 December 14th, 2016 at 2:31 am
The Hungarian Wizz-air is in the same class as Ryan air, whereas Norwegian (I’ll try not to be nationalistic about it) is more nice and normal about stuff. Lowest prices are low but not extreme, and average prices are good. They also award you for doing stuff yourself – not like Wizz where the check-in app only works until 3 hours before the flight, after that there is an exorbitant fee for “check-in assistance”. Not sure about their over-all European route coverage, but they have quite a bit of US-routes too now.
Comment #15 December 14th, 2016 at 2:35 am
Hal #5: My hosts here told me that Marine Le Pen is even scarier than Trump, because she’s smarter, less buffoonish, and knows how to pretend to be reasonable. I thought to myself: “uh-oh! So unlike Trump, she actually stands a chance of getting elected…”
Comment #16 December 14th, 2016 at 2:39 am
Joe #6: No, it’s not quantum supremacy (though it is a quantum something—which I suppose doesn’t narrow things down much!).
Chris #7: No, sorry, it’s nothing to do with lattices.
Comment #17 December 14th, 2016 at 2:42 am
David Molnar:
Wait so are you saying the Oliveira and Santhanam approach will prove the existence of an algorithm generate large member of any set in NP that is dense “enough” among strings of a given length?
I think they require the set to be in P, but otherwise yes. (Note that even if the set is dense and in P, it’s still far from obvious how to deterministically find a member of it.)
Are there such sets where we do know a poly time fully deterministic method of generating members?
The set of composite numbers? 😀
Comment #18 December 14th, 2016 at 2:47 am
Daniel Seita #9:
Hypothetically, if you were offered the position of Secretary of Energy, would you feel obligated to take it?
It’s hard to say whether I’d be morally obligated to take it, or morally obligated not to. Maybe I’d take the job, but then resign as soon as I was ordered to do something horrifying, like, I dunno, compile a list of all my employees who accepted the reality of human-caused climate change so they could be harassed or fired. I probably wouldn’t make it through my first day.
Comment #19 December 14th, 2016 at 2:51 am
Luca #12: Hadn’t seen that. Obviously huge news if correct, but the prior seems pretty strongly against (do you know anything to shift the prior?). In any case, no, that’s not what I was going to announce today.
Comment #20 December 14th, 2016 at 4:06 am
Like many Europeans, I’ve often used EasyJet. I think the experience varies with the route and the specific personnel onboard, but it has always been reasonable on average (at least, not significantly worse than pricier airlines). The main difference are really the stricter rules about cabin baggage, which are a pain if you are not fully aware of them in advance. But once you get used to it, you factor them into the choice of air carrier. Also low-cost carriers often have smaller seating space (with Ryanair the smallest in my experience).
Comment #21 December 14th, 2016 at 4:24 am
European here, I totally agree with you about EasyJet. Horrible.
Comment #22 December 14th, 2016 at 5:00 am
Ah! The demoscene! This was a very nice and nerdy place back in the ’90s, when the demos routinely had better sound and graphics than the latest video games on the same hardware! Hand-optimized real-time 3D rendering code in x86 assembler on VGA cards (texture mapping, phong shading, you have it), real-time 16-channel digital sound mixing on 2-channel Soundblaster hardware, all packed in a few 100KB, while lame commercial games just ran pre-rendered videos from 600MB CD-ROMs and the only real-time 3D games in town were Wolfenstein and Doom.
But once the first 3D accelarator cards and GPUs hit the market, rendering 3D graphics became just a matter of calling DirectX instead of hand-optimization and technical sophistication. As a consequence, the scene became more artisan and less technical. What a pitty.
Things took another upswing in the early 2000’s with the renewed focus on 64K and 4K intros due to the advent of Farbrausch demos, where technical sophistication met artistic design phenomenally!
Comment #23 December 14th, 2016 at 5:19 am
Amusingly, as a European, my experience with US carriers is similar to yours with Easyjet 🙂 At least Easyjet usually has enough seats to fit all the passengers on the plane… On the other hand, my experience a few years ago trying to claim compensation for a cancelled flight from them took customer service to a whole new level (downwards). The highlight was telling them that a recent European court ruling had clearly stated they had to provide compensation, to which their reply was simply that they did not believe the ruling was correct. Hard to argue with that…
Comment #24 December 14th, 2016 at 5:40 am
Oh, well, another sleepless night then.
Comment #25 December 14th, 2016 at 5:43 am
First vid def. not recommended for people who have trouble with flashing lights. Was borderline for me….
Comment #26 December 14th, 2016 at 5:51 am
European here. Easyjet usually miles better than Ryanair, you were unlucky. Germanwings, AirBerlin consistently excellent.
Btw Lyon is the only place that I know of that has 24h proper restaurants. The experience of enjoying a Boeuf Bourguignon washed down with a bottle of Rhône at 4AM in a busy place is not to be missed, esp. if you’re jetlagged.
Comment #27 December 14th, 2016 at 6:58 am
(P =?= NP)?
–Ajit
[E&OE]
Comment #28 December 14th, 2016 at 7:26 am
Probably unrelated, but this looks like a promising sign;
Harald A. HELFGOTT Isomorphismes de graphes en temps quasi-polynomial, d’après Babai et Luks
http://www.bourbaki.ens.fr/seminaires/2017/Sem.janv17/Res-janv17.pdf
for related links, videos, texts to appear;
http://www.bourbaki.ens.fr/
Comment #29 December 14th, 2016 at 7:46 am
This is another comment in defense of budget airlines. I almost only fly European budget airlines and a lot. Yes, they definitely try to milk unknowing passengers for whatever reason, but once you follow their rules, and don’t expect lunch or compensation, they are as good as any other airlines. You can even upgrade by buying insurances, like betting on the flight getting delayed with at least an hour, which I find quite entertaining from a theoretical point of view. In my experience the staff was always nice, even when passengers angered by the unjust fees were shouting at them.
Comment #30 December 14th, 2016 at 7:46 am
I just had a decent and cheap experience flying Thomas Cook Airlines from the UK to the USA. Others above seem clearly to suggest that knowing the rules makes traveling with discount airlines bearable (presumably unless you empathize with your neighbors who haven’t learned the rules and/or you hate that cabin staff start yelling at them).
So, today you’re announcing the creation of Shtetl-optimized Airlines?
Comment #31 December 14th, 2016 at 8:30 am
Peter #30: I’ve already used this blog to announce the formation of BQP Aarlines, the airline distinguished by having stacked beds instead of seats.
Comment #32 December 14th, 2016 at 9:10 am
There was a talk about Demoscene at ICM 2006, seems like it did not get recorded, though…
Comment #33 December 14th, 2016 at 11:52 am
Regarding the fact that demoscene programs are allowed to make use of DirectX: Well, some of them actually use different techniques where they really do all the rendering themselves. For example, see this technique: https://9bitscience.blogspot.com/2013/07/raymarching-distance-fields_14.html
Comment #34 December 14th, 2016 at 12:49 pm
Prof.Aaronson,
Going from Great Britain to the continent is best accomplished via Eurostar…unless there is a strike or something 😀
It is also strangely satisfying to be on a train that is travelling under the channel. Just my two pence.
Comment #35 December 14th, 2016 at 3:04 pm
The matrix multiplication paper starts by showing how to do an inner product of two 3^n-dimensional vectors using poly(n)*2^n products. But it’s known that you cannot compute inner products with a sublinear number of multiplications, so it’s not looking very promising.
Comment #36 December 14th, 2016 at 4:46 pm
Yea, easyJet falls into the category of “budget airlines” which are actually great if you are aware of the phenomenon and plan for it. Ryanair is in fact actively worse for dumb reasons. Norwegian Airlines is also in the same category, but for cheap transatlantic flights.
Comment #37 December 14th, 2016 at 4:51 pm
Many exciting papers out there recently. There was also the baby step giant step algorithm for “discrete logs” for groups acting on sets, https://arxiv.org/abs/1612.03456 by Bach and Sandlund.
Comment #38 December 14th, 2016 at 8:24 pm
Hi Scott,
I have read your paper with Adam Yedidia, “A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory” dated April 22, 2016 several times now since you made it available. Thank you for this work.
I should note that your paper is correct, no doubt in my mind. However, if it turns out that Turing’s paper is somehow incorrect, and that we may actually be able to build a Turing machine that solves for Beta-prime, your paper is not a re-affirmation of Turing’s work, but rather a proof of the inconsistency of ZFC. We can in fact, limit the logic of set theory to not include any impredicative statements, and eliminate your specific machine and machines like it.
I hope you see what I mean by this message.
Thanks for doing that cartoon with Zack, or I might mot have seen this entry.
Best from Cambridge,
Mark, that guy you met once in 2007.
Comment #39 December 14th, 2016 at 9:14 pm
Mark #38: Wow, that would be exciting! So it’s unfortunate for me and Adam that Turing’s work is correct. 😉
Comment #40 December 14th, 2016 at 9:19 pm
Luca #35: OK, thanks!! Yeah, this morning I saw your Facebook comment about the author claiming to compute inner products with sublinear multiplications (I hadn’t made it even that far), and immediately realized that I needn’t have been so noncommital, but then I had to give my colloquium so didn’t have time to post an update here.
Comment #41 December 15th, 2016 at 2:09 am
Allowing DirectX in 4K demos looks a lot less like a cheat when you know the only thing they ever choose to do with it is draw two triangles covering the screen and implement a raytracing renderer on the GPU that chooses how those triangles are “skinned” every frame.
They’re not using many services from DirectX, they’re just built for a slightly different machine than what you’re used to program.
Comment #42 December 15th, 2016 at 3:17 am
Aur #41: Thanks very much for the clarification! That does make it yet more impressive.
Comment #43 December 15th, 2016 at 3:20 am
Scott @40
The author has a track record http://h.web.umkc.edu/hanyij/html/research/isortlln.pdf.
Comment #44 December 15th, 2016 at 5:55 am
2^(n^o(1))
That’s exponential, NOT sub-exponential!!!
I guess you can “prove” ANYTHING when your redefine operant definitions on a whim!!!!!!!!!!!
Comment #45 December 15th, 2016 at 6:04 am
Damn. I live in Lyon and just learned reading this that you are here. Apparently you’re giving a talk at ENS this afternoon but I’m at work. I’m gutted !
Comment #46 December 15th, 2016 at 7:12 am
Dumb question: how do different algorithms fare against attacks using key fragments? If you have n bits or n % of total key size of a mceliece private key, RSA private key, block cipher key, or lattice key…how does the system hold up to attack, assuming all other conditions are favorable to Eve? Does this change under a quantum regime?
The baseline expectation is that 1% of a stolen key should make an attack 1% easier, but if I had confidence in that, I would not be asking.
Comment #47 December 15th, 2016 at 7:20 am
Ugh, ate part of my comment. Does this crazy thing have any obvious cryptography implications? http://www.wired.co.uk/article/new-computer-processing-power
Comment #48 December 15th, 2016 at 9:42 am
Well, I ditched work and came to see Scott anyway. I’m glad I did, it was a great talk. I even managed to get a seat, many where standing up or seating on the floor ! Too bad I couldn’t stay for drinks, I would’ve loved to chat with you.
Comment #49 December 15th, 2016 at 11:56 am
Quarint #48: Glad you liked the talk, and I’m sorry I didn’t get a chance to meet you in person!
Comment #50 December 15th, 2016 at 11:59 am
Me not you #44: That’s pretty far out on the Pareto curve of ignorance and arrogance among all comments in the history of this blog (and you have stiff competition). 2^n^o(1) is precisely what we normally call “sub-exponential” in theoretical computer science. Note the o(1), meaning “decreasing asymptotically to 0.”
Comment #51 December 15th, 2016 at 10:32 pm
Random question: Are temporary bits necessary for universal reversible computation?
For example, is the Toffoli gate still universal if all you can do is read from the input bits and write to the output bits?
Comment #52 December 16th, 2016 at 12:16 am
Job #51: With no ancilla bits, Toffoli can only implement even permutations on n≥4 bits: when n=4, for example, it can’t swap 0000 with 0001 while leaving everything else unchanged. But one can show that even a single ancilla bit lets the Toffoli gate implement all permutations, rather than merely all even ones. This was all in Toffoli’s original paper. For a generalization to any set of reversible gates (whether universal or not)—showing that whatever those gates can do, they can do with at most O(1) ancilla bits—see The Classification of Reversible Bit Operations by me, Daniel Grier, and Luke Schaeffer.
Comment #53 December 16th, 2016 at 1:36 am
I imagine there is no finite set of reversible gates that’s universal without ancilla bits?
I’m wondering what that set of gates would look like. Is it like a sequence of AND gates, with an increasing number of control bits, or different gates? And the number of control bits, how would it increase?
Comment #54 December 16th, 2016 at 2:13 am
Job #53: Yes, that’s exactly right. Toffoli’s argument shows that no finite set of reversible gates is universal without ancillas. With an infinite set, you can certainly do it: for example, using all the generalized Toffoli gates (Controlled-NOT, Controlled-Controlled-NOT, and so on ad infinitum).
Comment #55 December 16th, 2016 at 3:09 am
Is there a known process by which a circuit can be efficiently converted to use zero ancilla bits?
My understanding is that, without ancilla bits, the order in which gates are executed is not significant – each gate is strictly reading from the immutable input and flipping output bits – which makes concurrency and synchronization alot easier.
And the concept is strange. For example, a sorting algorithm (like MergeSort) converted to use zero ancilla bits could be split up such that each operation is run in parallel? Hard to visualize.
Also, what is that like O(1) given enough processors? But parallel MergeSort, from what i remember, can’t do better than logn.
Comment #56 December 16th, 2016 at 3:27 am
Job #55: I already explained that you can’t convert an arbitrary reversible circuit into one that uses zero ancilla bits.
And I don’t know where you got the idea that the order of gates doesn’t matter in a circuit with no ancilla bits, but it clearly does (try an example and see).
My, Daniel, and Luke’s construction uses only O(1) ancilla bits, but plenty of gates, and it need not be parallelizable.
Comment #57 December 16th, 2016 at 4:47 am
Not in a context where input bits are read-only and output bits are write-only. In that case all gates operate on the original immutable input and conditionally flip output bits. The order in which output bits are flipped doesn’t matter because they’re never read.
Essentially, control bits are always connected to input bits and target bits are always connected to output bits.
I was wondering how universal a gate set under these constraints can actually be.
Comment #58 December 16th, 2016 at 8:55 am
Hey Scott, if you want more CG in the same spirit I definitely recommend checking out Shadertoy. For example this:
https://www.shadertoy.com/view/llsGW7
or this:
https://www.shadertoy.com/view/XsX3RB.
There are plenty of impressive effects, procedural landscapes etc. which most of the time are just cool math/coding tricks.
Comment #59 December 16th, 2016 at 10:19 am
Rhhif #47: Another (and IMHO better) article about this device was linked in this comment, and Scott replied in the next comment on that page. To answer your question, there certainly are no obvious implications to cryptography at the moment. That might change in the future, if tests can demonstrate that this thing can solve large NP-complete problems faster than ordinary computers, but that seems unlikely.
Comment #60 December 16th, 2016 at 11:49 am
Scott, after your “cheap flight” experience, you may enjoy this:
https://www.youtube.com/watch?v=HPyl2tOaKxM
Nick
Comment #61 December 16th, 2016 at 4:52 pm
Hm, now I’m wondering if anything is known about the possibility of “catalytic” ancilla bits, analogous to this: http://eccc.hpi-web.de/report/2014/053/ (assuming that such a thing makes sense, anyway)
Comment #62 December 17th, 2016 at 12:21 am
Sniffnoy #61: Actually, yes. My student Siyao Xu wrote her M.Eng. thesis about reversible circuits. And one of the things she did there was to draw a distinction between “ordinary” ancilla bits, which have to start in a specific state (like 0) and are then returned to that state, and “catalytic” ancilla bits (she may have used a different term), which can start in either state and are then returned to that state. Some reversible circuit constructions require ordinary ancilla bits, but others (especially those only involving affine gates) can be done with catalytic ancillas.
Comment #63 December 17th, 2016 at 1:11 am
Interesting! I might have to look that up…