{"id":272,"date":"2007-09-16T15:07:54","date_gmt":"2007-09-16T19:07:54","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=272"},"modified":"2007-09-16T15:07:54","modified_gmt":"2007-09-16T19:07:54","slug":"barriers-to-proving-pnp-and-moving-this-blog","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=272","title":{"rendered":"Barriers to proving P!=NP and moving this blog"},"content":{"rendered":"

Thanks, everyone, for your patience, and your numerous complaints<\/a> about the Technology Review<\/em> site! Currently, the folks at TR<\/em> say they can do all the minor things people asked for, like adding permalinks to the titles and letting people include their URL’s with their comments. On the other hand, they can’t make it so you can post comments without logging in, and they can’t decrease the size of the ad bar. (I suggested that they at least turn my sidebar into drop-down menus, thereby increasing the screen width available for the entries; they said they’d look into that.) Also, they can’t provide the full text in RSS (since God forbid, that might let people read the blog without seeing ads), although they can<\/em> give the first 150 words or so.<\/p>\n

As you can imagine, TR’s response has put me in a difficult position. From their perspective, they’ve been bending over backwards to accommodate me; from my perspective (and I gather from most readers’), their offer still falls short of acceptable. When I originally agreed to let them host me, I imagined that the blog would look just as it does now, with maybe a few unobtrusive ads here or there. I didn’t even think to ask about the RSS feed or the screen width available for entries.<\/p>\n

And so, after weeks of introspection (well, mostly being tied up with other work), I’ve reached a decision: I will continue to host my blog right here, on Bluehost, until TR comes up with something that both parties can live with.<\/em> I like<\/em> the TR people and appreciate their interest, but I’m not in any particular hurry to move, especially if it means crippling this blog so that no will read it. It’s true that Bluehost sucks<\/a>, and that I no longer have time to be a webmaster — but once I get grant money, maybe I can pay someone to take care of these things for me.<\/p>\n

Finally, since all this self-referentiality gets tiresome, here are the PowerPoint slides<\/a> for a talk I gave at MIT last week, about recent joint work with Avi Wigderson on a new barrier to proving P\u2260NP. (Note: The day before the talk, PowerPoint trashed my file, and I had to recreate the entire presentation from memory. Always make backup copies! Excellent advice, in my opinion.)<\/font><\/p>\n

Abstract:<\/p>\n

Algebrization: A New Barrier in Complexity Theory<\/strong><\/p>\n

Any proof of P\u2260NP will have to overcome two barriers: relativization and natural proofs. Yet over the last decade, we have seen circuit lower bounds (for example, that PP does not have linear-size circuits) that overcome both barriers simultaneously. So the question arises of whether there is a third barrier to progress on the central questions in complexity theory.<\/p>\n

In this talk we present such a barrier, which we call “algebraic relativization” or “algebrization.” The idea is that, when we relativize some complexity class inclusion, we should give the simulating machine access not only to an oracle A, but also to the low-degree extension of A over a finite field or ring.<\/p>\n

We systematically go through basic results and open problems in complexity theory to delineate the power of the new algebrization barrier. We first show that all known non-relativizing results — both inclusions such as IP=PSPACE and MIP=NEXP, and separations such as MAEXP<\/sub>\u2284P\/poly — do indeed algebrize. We next show that most open problems — including P versus NP, P versus BPP, and NEXP versus P\/poly — will require non-algebrizing techniques, of which we currently have not a single example. In some cases algebrization seems to explain exactly why progress stopped where it did: for example, why we have superlinear circuit lower bounds for PromiseMA but not for NP.<\/p>\n

We also exhibit a surprising connection between algebrization and communication complexity. Using this connection, we give an MA-protocol for the Inner Product function with O(\u221an log(n)) communication (essentially matching a lower bound of Klauck), and describe a pure communication complexity conjecture whose truth would imply P\u2260NP.<\/p><\/blockquote>\n

Comments welcome. We’ll hopefully have a writeup soon.<\/p>\n","protected":false},"excerpt":{"rendered":"

Thanks, everyone, for your patience, and your numerous complaints about the Technology Review site! Currently, the folks at TR say they can do all the minor things people asked for, like adding permalinks to the titles and letting people include their URL’s with their comments. On the other hand, they can’t make it so you […]<\/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_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"{title}\n\n{excerpt}\n\n{url}","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,"jetpack_post_was_ever_published":false},"categories":[5,7],"tags":[],"class_list":["post-272","post","type-post","status-publish","format-standard","hentry","category-complexity","category-self-referential"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/272","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=272"}],"version-history":[{"count":0,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/272\/revisions"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=272"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=272"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=272"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}