{"id":407,"date":"2009-06-11T17:33:20","date_gmt":"2009-06-11T21:33:20","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=407"},"modified":"2009-06-11T17:33:20","modified_gmt":"2009-06-11T21:33:20","slug":"my-long-complexity-theoretic-journey","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=407","title":{"rendered":"My long, complexity-theoretic journey"},"content":{"rendered":"

So, what was I doing these past few weeks that could possibly<\/em> take precedence over writing ill-considered blog entries that I’d probably regret for the rest of my life?<\/p>\n

1. On the gracious invitation of Renato Renner, I visited one of Al Einstein’s old stomping-grounds: ETH Z\u00fcrich.\u00a0 There I gave a physics colloquium called How Much Information Is In A Quantum State?<\/a>, as well as a talk on my paper Quantum Copy-Protection and Quantum Money<\/a>, which has been more than three years in the procrastinating.\u00a0 Though I was only in Switzerland for three days, I found enough time to go hiking in the Swiss Alps, if by “Swiss Alps” you mean a 200-foot hill outside the theoretical physics building.\u00a0 I’m quite proud of having made it through this entire trip—my first to Switzerland—without once yodeling or erupting into cries of “Riiiiiiicola!”\u00a0 On the other hand, what with the beautiful architecture, excellent public transportation, and wonderful hosts, it was a struggle to maintain my neutrality.<\/p>\n

2. On the plane to and from Switzerland, I had the pleasure of perusing Computational Complexity: A Modern Approach<\/a>, by Sanjeev Arora and Boaz Barak, which has just been published after floating around the interweb for many years.\u00a0 If you’re a hardcore complexity lover, I can recommend buying a copy in the strongest terms.\u00a0 The book lives up to its subtitle, concentrating almost entirely on developments within the last twenty years.\u00a0 Classical complexity theorists should pay particular attention to the excellent quantum computing chapter, neither of whose authors has the slightest background in the subject.\u00a0 You see, people, getting quantum right isn’t that<\/em> hard, is it?\u00a0 The book’s only flaw, an abundance of typos, is one that can and should be easily fixed in the next edition.<\/p>\n

3. I then visited the National Institute of Standards and Technology—proud keepers of the meter and the kilogram—at their headquarters in Gaithersburg, MD.\u00a0 There I gave my talk on Quantum Complexity and Fundamental Physics<\/a>, a version of the shtick I did at the QIS workshop in Virginia.\u00a0 Afterwards, I got to tour some of the most badass experimental facilities I’ve seen in a while.\u00a0 (Setting standards and making precision measurements: is there anything else that sounds so boring but turns out to so not be?)\u00a0 A highlight was the Center for Neutron Research<\/a>, which houses what’s apparently the largest research reactor still operating in the US.\u00a0 This thing has been operating since 1967, and it shoots large numbers of slow-moving neutrons in all directions so that archaeologists, chemists, physicists, etc. can feed off the trough and do their experiments.\u00a0 The basic physics that’s been done there recently has included setting bounds on possible nonlinearities in the Schr\u00f6dinger equation (even though any<\/em> nonlinearity, no matter how small, could be used to send superluminal signals and solve NP-complete problems in polynomial time), as well as observing the photons that the Standard Model apparently predicts are emitted 2% of the time when a neutron decays.\u00a0 I also got to see one of the world’s least jittery floors: using dynamical feedback, they apparently managed to make this floor ~107<\/sup> times less jittery than a normal floor, good enough that they can run a double-slit experiment with slow neutrons on top of it and see the interference pattern.\u00a0 (Before you ask: yes, I wanted<\/em> to jump on the floor, but I didn’t.\u00a0 Apparently I would’ve messed it up for a day.)<\/p>\n

I have to add: the few times I’ve toured a nuclear facility, I felt profoundly depressed by the “retro” feel of everything around me: analog dials, safety signs from the 60s…\u00a0\u00a0 Why are no new reactors being built in the US, even while their value as stabilization wedges<\/a> becomes increasingly hard to ignore?\u00a0 Why are we unwilling to reprocess spent fuel rods like France does?\u00a0 Why do people pin their hopes on the remote prospect of controlled fusion, ignoring the controlled fission we’ve had for half a century?\u00a0 Why, like some horror-movie character unwilling to confront an evil from the past, have we decided that a major technology possibly crucial to the planet’s survival must remain a museum piece, part of civilization’s past and not its future?\u00a0 Of course, these are rhetorical questions.\u00a0 While you can be exposed to more radiation flying cross-country than working at a nuclear reactor for months, while preventing a Chernobyl is as easy as using shielding and leaving on the emergency cooling system, human nature is often a more powerful force than physics.<\/p>\n

4. Next I went to STOC’2009<\/a> in Bethesda, MD.\u00a0 Let me say something about a few talks that are impossible not<\/em> to say something about.\u00a0 First, in what might or might not turn out to be the biggest cryptographic breakthrough in decades, Craig Gentry has proposed a fully homomorphic encryption scheme<\/a> based on ideal lattices: that is, a scheme that lets you perform arbitrary computations on encrypted data without decrypting it.\u00a0 Currently, Gentry’s scheme is not known to be breakable even by quantum computers—despite a 2002 result<\/a> of van Dam, Hallgren, and Ip, which said that if<\/em> a fully homomorphic encryption scheme existed, then it could be broken by a quantum computer.\u00a0 (The catch?\u00a0 Van Dam et al.’s result applied to deterministic encryption schemes; Gentry’s is probabilistic.)<\/p>\n

Second, Chris Peikert (co-winner of the Best Paper Award) announced a public-key cryptosystem<\/a> based on the classical<\/em> worst-case hardness of the Shortest Vector Problem.\u00a0 Previously, Regev had given such a cryptosystem<\/a> based on the assumption that there’s no efficient quantum<\/em> algorithm for SVP (see also here<\/a> for a survey).\u00a0 The latter was a striking result: even though Regev’s cryptosystem is purely classical, his reduction from SVP to breaking the cryptosystem was a quantum reduction.\u00a0 What Peikert has now done is to “dequantize” Regev’s security argument by thinking very hard about it.\u00a0 Of course, one interpretation of Peikert’s result is that classical crypto people no longer have to learn quantum mechanics—but a better interpretation is that they do<\/em> have to learn QM, if only to get rid of it!\u00a0 I eagerly await Oded Goldreich<\/a>‘s first paper on quantum computing (using it purely as an intellectual tool, of course).<\/p>\n

Third, Robin Moser (co-winner of the Best Paper Award and<\/em> winner of the Best Student Paper Award) gave a mindblowing algorithmic version<\/a> of the Lov\u00e1sz Local Lemma<\/a>.\u00a0 Or to put it differently, Moser gave a polynomial-time algorithm that finds a satisfying assignment for a k-SAT formula, assuming that each clause intersects at most 2k-2<\/sup> other clauses.\u00a0 (It follows from the Local Lemma that such an assignment exists<\/em>.)\u00a0 Moser’s algorithm is absurdly simple: basically, you repeatedly pick an unsatisfied clause, and randomly set its variables so that it’s satisfied.\u00a0 Then, if doing that has made any of the neighboring clauses unsatisfied, you randomly set their variables so that they’re<\/em> satisfied, and so on, recursing until all the damage you’ve caused has also been fixed.\u00a0 The proof that this algorithm actually halts in polynomial time uses a communication argument that, while simple, seemed so completely out of left field that when it was finished, the audience of theorists sort of let out a collective gasp, as if a giant black “QED” box were hovering in the air.<\/p>\n

Fourth, Babai, Beals, and Seress<\/a> showed that if G is a matrix group over a finite field of odd order, then the membership problem for G can be solved in polynomial time, assuming an oracle for the discrete logarithm problem.\u00a0 This represents the culmination of about 25 years of work in computational group theory.\u00a0 I was all pumped to announce an important consequence of this result not noted in the abstract—that the problem is therefore solvable in quantum<\/em> polynomial time, because of Shor’s discrete log algorithm—but Laci, alas, scooped me on this highly nontrivial corollary in his talk.<\/p>\n

5. Finally, I took the train up to Princeton, for a workshop on “Cryptography and Complexity: Status of Impagliazzo’s Worlds”<\/a>.\u00a0 (For the insufficiently nerdy: the worlds<\/a> are Algorithmica, where P=NP; Heuristica, where P\u2260NP but the hard instances of NP-complete problems are hard to find; Pessiland, where the hard instances are easy to find but none of them can be used for cryptographic one-way functions; Minicrypt, where one-way functions do exist, enabling private-key cryptography, but not the trapdoor<\/em> one-way functions needed for public-key cryptography; and Cryptomania, where trapdoor one-way functions exist, and cryptography can do pretty anything you could ask.)\u00a0 I gave a talk on Impagliazzo’s worlds in arithmetic complexity<\/a>, based on ongoing join work with Andy Drucker (where “ongoing” means we’re pretty sure more of our results are correct than would be expected by random guessing).<\/p>\n

Tell you what: since it’s been a long time, feel free to ask whatever you feel like in the comments section, whether related to my journeys or not.\u00a0 I’ll try to answer at least a constant fraction of questions.<\/p>\n


\n <\/p>\n","protected":false},"excerpt":{"rendered":"

So, what was I doing these past few weeks that could possibly take precedence over writing ill-considered blog entries that I’d probably regret for the rest of my life? 1. On the gracious invitation of Renato Renner, I visited one of Al Einstein’s old stomping-grounds: ETH Z\u00fcrich.\u00a0 There I gave a physics colloquium called How […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false},"categories":[10,5,30],"tags":[],"class_list":["post-407","post","type-post","status-publish","format-standard","hentry","category-adventures-in-meatspace","category-complexity","category-mirrored-on-csail-blog"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/407","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=407"}],"version-history":[{"count":0,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/407\/revisions"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=407"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=407"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=407"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}