{"id":4229,"date":"2019-07-02T00:15:43","date_gmt":"2019-07-02T05:15:43","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=4229"},"modified":"2019-09-24T21:18:06","modified_gmt":"2019-09-25T02:18:06","slug":"sensitivity-conjecture-proof-by-the-book","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=4229","title":{"rendered":"Sensitivity Conjecture resolved"},"content":{"rendered":"\n

The Sensitivity Conjecture, which I blogged about here<\/a>, says that, for every Boolean function f:{0,1}n<\/sup>\u2192{0,1}, the sensitivity<\/em> of f—that is, the maximum, over all 2n<\/sup> input strings x\u2208{0,1}n<\/sup>, of the number of input bits such that flipping them changes the value of f—is at most polynomially smaller than a bunch of other complexity measures of f, including f’s block sensitivity, degree as a real polynomial, and classical and quantum query complexities. (For more, see for example this survey<\/a> by Buhrman and de Wolf. Or for quick definitions of the relevant concepts, see here<\/a>.)<\/p>\n\n\n\n

Ever since it was posed by Nisan and Szegedy in 1989, this conjecture has stood as one of the most frustrating and embarrassing open problems in all of combinatorics and theoretical computer science. It seemed so easy, and so similar to other statements that had 5-line proofs. But a lot of the best people in the field sank months into trying to prove it. For whatever it’s worth, I also sank … well, at least weeks into it.<\/p>\n\n\n\n

Now Hao Huang<\/a>, a mathematician at Emory University, has posted a 6-page preprint<\/a> on his homepage that finally proves the Sensitivity Conjecture, in the form s(f)\u2265\u221adeg(f). (I thank Ryan O’Donnell for tipping me off to this.) Within the preprint, the proof itself is about a page and a half.<\/p>\n\n\n\n

Whenever there’s an announcement like this, ~99% of the time either the proof is wrong, or at any rate it’s way too complicated for outsiders to evaluate it quickly. This is one of the remaining 1% of cases. I’m rather confident that the proof is right. Why? Because I read and understood it. It took me about half an hour. If you’re comfortable with concepts like induced subgraph<\/em> and eigenvalue<\/em>, you can do the same.<\/p>\n\n\n\n

From pioneering work by Gotsman and Linial in 1992, it was known that to prove the Sensitivity Conjecture, it suffices to prove the following even simpler combinatorial conjecture:<\/p>\n\n\n\n

Let S be any subset of the n-dimensional Boolean hypercube, {0,1}n<\/sup>, which has size 2n-1<\/sup>+1. Then there must be a point in S with at least ~nc<\/sup> neighbors in S.<\/p><\/blockquote>\n\n\n\n

Here c>0 is some constant (say 1\/2), and two points in S are “neighbors” if and only they differ in a single coordinate. Note that if S had size 2n-1<\/sup>, then the above statement would be false—as witnessed, for example, by the set of all n-bit strings with an even number of 1’s.<\/p>\n\n\n\n

Huang proceeds by proving the Gotsman-Linial Conjecture. And the way he proves Gotsman-Linial is … well, at this point maybe I should just let you read the damn preprint<\/a> yourself. I can’t say it more simply than he does.<\/p>\n\n\n\n

If I had to try anyway, I’d say: Huang constructs a 2n<\/sup>\u00d72n<\/sup> matrix, called An<\/sub>, that has 0’s where there are no edges between the corresponding vertices of the Boolean hypercube, and either 1’s or -1’s where there are<\/em> edges—with a simple, weird pattern of 1’s and -1’s that magically makes everything work. He then lets H be an induced subgraph of the Boolean hypercube of size 2n-1<\/sup>+1. He lower-bounds the maximum degree of H by the largest eigenvalue of the corresponding (2n-1<\/sup>+1)\u00d7(2n-1<\/sup>+1) submatrix of An<\/sub>. Finally, he lower-bounds that largest eigenvalue by … no, I don’t want to spoil it! Read it yourself!<\/p>\n\n\n\n

Paul Erd\u00f6s famously spoke of a book, maintained by God, in which was written the simplest, most beautiful proof of each theorem. The highest compliment Erd\u00f6s could give a proof was that it “came straight from the book.” In this case, I find it hard to imagine that even God knows how to prove the Sensitivity Conjecture in any simpler way than this.<\/p>\n\n\n\n

Indeed, the question is: how could such an elementary 1.5-page argument have been overlooked for 30 years? I don’t have a compelling answer to that, besides noting that “short” and “elementary” often have little to do with “obvious.” Once you start looking at the spectral properties of this matrix An<\/sub>, the pieces snap together in precisely the right way—but how would you know to look at that?<\/p>\n\n\n\n

By coincidence, earlier today I finished reading my first PG Wodehouse novel (Right Ho, Jeeves!<\/a><\/em>), on the gushing recommendation of a friend. I don’t know how I’d missed Wodehouse for 38 years. His defining talent is his ability to tie together five or six plot threads in a way that feels perfect and inevitable even though you didn’t see it coming. This produces a form of pleasure that’s nearly indistinguishable from the pleasure one feels in reading a “proof from the book.” So my pleasure centers are pretty overloaded today—but in such depressing times for the world, I’ll take pleasure wherever I can get it.<\/p>\n\n\n\n

Huge congratulations to Hao!<\/p>\n\n\n\n

Added thought:<\/strong> What this really is, is one of the purest illustrations I’ve seen in my career of the power and glory of the P≠NP phenomenon. We talk all the time about how proofs are easier to verify than to find. In practice, though, it can be far from obvious that that’s true. Consider your typical STOC\/FOCS paper: writing it probably took the authors several months, while fully understanding the thing from scratch would probably take … also<\/em> several months! If there’s a gap, it’s only by a factor of 4 or 5 or something. Whereas in this case, I don’t know how long Huang spent searching for the proof, but the combined search efforts of the community add up to years or decades. The ratio of the difficulty of finding to the difficulty of completely grasping is in the hundreds of thousands or millions.<\/p>\n\n\n\n

Another added thought:<\/strong> Because Hao actually proves a stronger statement than the original Sensitivity Conjecture, it has additional implications, a few of which Hao mentions in his preprint. Here’s one he didn’t mention: any randomized algorithm to guess the parity of an n-bit string, which succeeds with probability at least 2\/3 on the majority of strings, must make at least ~\u221an queries to the string, while any such quantum algorithm must make at least ~n1\/4<\/sup> queries. For more, see the paper Weak Parity<\/a> by me, Ambainis, Balodis, and Bavarian (Section 6).<\/p>\n\n\n\n

Important Update:<\/strong> Hao Huang himself has graciously visited the comment section<\/a> to satisfy readers’ curiosity by providing a detailed timeline of his work on the Sensitivity Conjecture. (tl;dr: he was introduced to the problem by Mike Saks in 2012, and had been attacking it on and off since then, until he finally had the key insight this past month while writing a grant proposal. Who knew that grant proposals could ever be useful for anything?!?)<\/p>\n\n\n\n

Another Update:<\/strong> In the comments section, my former student Shalev Ben-David points out a simplification<\/a> of Huang’s argument, which no longer uses Cauchy’s interlacing theorem. I thought there was no way this proof could possibly be made any simpler, and I was wrong!<\/p>\n","protected":false},"excerpt":{"rendered":"

The Sensitivity Conjecture, which I blogged about here, says that, for every Boolean function f:{0,1}n\u2192{0,1}, the sensitivity of f—that is, the maximum, over all 2n input strings x\u2208{0,1}n, of the number of input bits such that flipping them changes the value of f—is at most polynomially smaller than a bunch of other complexity measures of […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_seo_schema_type":"","_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],"tags":[],"class_list":["post-4229","post","type-post","status-publish","format-standard","hentry","category-complexity"],"jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/4229","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\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4229"}],"version-history":[{"count":5,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/4229\/revisions"}],"predecessor-version":[{"id":4249,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/4229\/revisions\/4249"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4229"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4229"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4229"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}