tag:blogger.com,1999:blog-786333285568106173.post5086993394573451276..comments2022-04-03T16:08:02.581-04:00Comments on WebDiarios de Motocicleta: CC4: One-Way Communication and a PuzzleMihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-786333285568106173.post-55491073877379023942009-11-08T13:38:52.103-05:002009-11-08T13:38:52.103-05:00Here is another proof that exhibits the distributi...Here is another proof that exhibits the distribution explicitly and resorts to standard direct sum tools.<br /><br />We define a product distribution µ = µ_A x µ_B such that when (x,y) ~ µ, Pr[x,y disjoint] = 1/2.<br /><br />Partition the universe [2n^2] in n blocks of size 2n. For Alice's input select randomly single element from each block (independently). Bob's input distribution is sum of n distributions: µ_B = 1/n Σ D_i, where D_i is defined as follows: Randomly select a subset of size n of block i. Don't chose any elements from other blocks.<br /><br />Denote Alice's and Bob's inputs X=X_1...X_n and Y=Y_1...Y_n. Suppose there is an eps error protocol in which Alice's sends the message A. We have I(X : A) <= |A|. By averaging for at least half of the blocks I(X_i : A) <= 2|A|/n. Among this half there exist an i such that error on µ x D_i is smaller than 2eps. Therefore the information cost of the problem is n/4 times the information cost of a single membership problem (with universe [2n])<br />The lemma follows from IC_uniform,2eps(MEM_n) = Omega(log n).<br /><br />To Answer King of lower bounds's question: The lemma holds for any universe n^{1+eps}, eps>0.<br /><br />Does anyone know a distribution which is hard for both one way and arbitrary round protocols. (requires n log n bits for one way, n bits for arbitrary)?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-6656612127782077552009-04-09T11:11:00.000-04:002009-04-09T11:11:00.000-04:00Thanks, Mihai. I learn another lesson. Looking for...Thanks, Mihai. I learn another lesson. Looking forward to the next ...Jeremyhttps://www.blogger.com/profile/07542797422324282461noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-21212790088669869532009-04-08T08:31:00.000-04:002009-04-08T08:31:00.000-04:00Aargh, n(n-1)+a[n].There! Lots of comments to your...Aargh, n(n-1)+a[n].<BR/><BR/>There! Lots of comments to your post.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-17495970471853977812009-04-08T08:30:00.000-04:002009-04-08T08:30:00.000-04:00Oops, first set above should be {a[1],n+a[2],...(n...Oops, first set above should be {a[1],n+a[2],...(n-1)+a[n]}.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-45906957408059973662009-04-08T08:28:00.000-04:002009-04-08T08:28:00.000-04:00King of lower bounds says...SPOILER: Map Alice's (...King of lower bounds says...<BR/><BR/>SPOILER: Map Alice's (n log n)-bit string x to the set {a[1],...a[n]} where the i-th block of log n bits of x encodes a[i]. Map Bob's index to an appropriate (n/2)-sized subset of [(j-1)n+1 .. jn].<BR/><BR/>COUNTER-PUZZLE: Is n^2 the smallest universe size for which this result is possible?Anonymousnoreply@blogger.com