tag:blogger.com,1999:blog-3722233.post3620378567435544516..comments2024-03-27T19:58:17.387-05:00Comments on Computational Complexity: Favorite Theorems: Limited IndependenceLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-51249820328805352392014-09-04T07:37:14.379-05:002014-09-04T07:37:14.379-05:00Braverman does prove that every polylogarithmic in...Braverman does prove that every polylogarithmic independent distribution will fool poly-size constant depth circuits. I recommend reading Braverman's well-written paper, particularly the introduction, for more details.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8546993274934503172014-09-03T19:25:58.303-05:002014-09-03T19:25:58.303-05:00Adding emphasis to the previous comment for clarit...Adding emphasis to the previous comment for clarity... Based on your description of the result, is an informal description that "*any* polylogarithmic independent distribution fools polynomial-size constant-depth circuits" justified? It sounds like the result establishes the *existence* of a deceptive polylogarithmic-independent distribution.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16213146093451526572014-08-29T08:23:54.469-05:002014-08-29T08:23:54.469-05:00I haven't read the paper, but based on your de...I haven't read the paper, but based on your description of the result, is an informal description that "any polylogarithmic independent distribution fools polynomial-size constant-depth circuits" justified? It sounds like the result establishes the existence of a deceptive polylogarithmic-independent distribution.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2690997263317446992014-08-15T09:49:44.670-05:002014-08-15T09:49:44.670-05:00Bazzi has provided some information on the genesis...Bazzi has provided some information on the genesis of his paper, see http://emanueleviola.wordpress.com/2014/08/02/the-sandwich-revolution-behind-the-paper/Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86438091633518288822014-08-14T17:28:37.861-05:002014-08-14T17:28:37.861-05:00Only k\lg n random bits are needed for k-wise inde...Only k\lg n random bits are needed for k-wise independent n-bit strings, see for example Vadhan's monograph (http://people.seas.harvard.edu/~salil/pseudorandomness/ , section 3.5.5).Anonymousnoreply@blogger.com