{"id":452,"date":"2010-07-11T01:02:52","date_gmt":"2010-07-11T05:02:52","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=452"},"modified":"2010-07-11T01:02:52","modified_gmt":"2010-07-11T05:02:52","slug":"the-generalized-linial-nisan-conjecture-is-false","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=452","title":{"rendered":"The Generalized Linial-Nisan Conjecture is false"},"content":{"rendered":"

In a post<\/a> a year and a half ago, I offered a prize of $200 for proving something called the Generalized Linial-Nisan Conjecture, which basically said that almost k-wise independent distributions fool AC0<\/sup> circuits.\u00a0 (Go over to that post if you want to know what that means and why I cared about it.)<\/p>\n

Well, I’m pleased to report that that’s a particular $200 I’ll never have to pay.\u00a0 I just uploaded a new preprint to ECCC, entitled A Counterexample to the Generalized Linial-Nisan Conjecture<\/a>.\u00a0 (That’s the great thing about research: no matter what happens, you get a paper out of it.)<\/p>\n

A couple friends commented that it was wise to name the ill-fated conjecture after other people rather than myself.\u00a0 (Then again, who the hell names a conjecture after themselves?)<\/p>\n

If you don’t feel like downloading the ECCC preprint<\/a>, but do feel like scrolling down, here’s the abstract (with a few links inserted):<\/p>\n

In earlier work<\/a>, we gave an oracle separating the relational versions of BQP and the polynomial hierarchy, and showed that an oracle separating the decision versions would follow from what we called the Generalized Linial-Nisan (GLN) Conjecture<\/em>: that “almost k-wise independent” distributions are indistinguishable from the uniform distribution by constant-depth circuits. The original Linial-Nisan Conjecture was recently proved by Braverman<\/a>; we offered a $200 prize for the generalized version. In this paper, we save ourselves $200 by showing that the GLN Conjecture is false, at least for circuits of depth 3 and higher.
\nAs a byproduct, our counterexample also implies that \u03a02<\/sub>p<\/sup>\u2284PNP<\/sup> relative to a random oracle with probability 1. It has been conjectured since the 1980s that PH is infinite relative to a random oracle, but the best previous result was NP\u2260coNP relative to a random oracle.
\nFinally, our counterexample implies that the famous results<\/a> of Linial, Mansour, and Nisan, on the structure of AC0<\/sup> functions, cannot be improved in several interesting respects.<\/p><\/blockquote>\n

To dispel any confusion, the $200 prize still stands for the original problem that the GLN Conjecture was meant to solve: namely, giving an oracle relative to which BQP is not in PH.\u00a0 As I say in the paper, I remain optimistic about the prospects for solving that<\/em> problem by a different approach, such as an elegant one recently proposed<\/a> by Bill Fefferman and Chris Umans.\u00a0 Also, it’s still possible that the GLN Conjecture is true for depth-two<\/em> AC0<\/sup> circuits (i.e., DNF formulas).\u00a0 If so, that would imply the existence of an oracle relative to which BQP is not in AM—already a 17-year-old open problem—and net a respectable $100.<\/p>\n","protected":false},"excerpt":{"rendered":"

In a post a year and a half ago, I offered a prize of $200 for proving something called the Generalized Linial-Nisan Conjecture, which basically said that almost k-wise independent distributions fool AC0 circuits.\u00a0 (Go over to that post if you want to know what that means and why I cared about it.) Well, I’m […]<\/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":"","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,18,9],"tags":[],"class_list":["post-452","post","type-post","status-publish","format-standard","hentry","category-complexity","category-embarrassing-myself","category-mistake-of-the-week"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/452","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=452"}],"version-history":[{"count":0,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/452\/revisions"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=452"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=452"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=452"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}