tag:blogger.com,1999:blog-3722233.post2510350973453894628..comments2022-09-29T21:14:57.878-05:00Comments on Computational Complexity: The Communication Complexity of MAX: Open problemLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger15125tag:blogger.com,1999:blog-3722233.post-88627942735123697322008-09-29T19:33:00.000-05:002008-09-29T19:33:00.000-05:00The Greater Than problem can be solved with polylo...The Greater Than problem can be solved with polylog(n) bits of communication, by a randomized protocol (binary search for the longest common prefix). <BR/><A HREF="http://www.wx-sd.com/cp18.htm" REL="nofollow" TITLE="蒸馏塔">蒸馏塔</A><BR/><A HREF="http://www.cctvaa.com/cp22.htm" REL="nofollow" TITLE="种子罐">种子罐</A>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10463251516964278392008-09-23T20:58:00.000-05:002008-09-23T20:58:00.000-05:00Hm, I guess reading comprehension would be useful ...Hm, I guess reading comprehension would be useful *before* I post!sep332https://www.blogger.com/profile/15089674288837329342noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76939313782462183342008-09-23T04:36:00.000-05:002008-09-23T04:36:00.000-05:00I was interested to see the e-egg problem describe...I was interested to see the e-egg problem described as it is also the basis of many of the modern improvements in computational pattern matching. For example, pattern matching under the Hamming, L_1 norm etc. (typically the complexity you get is something like O(n sqrt{m log m}). The basic technique is normally attributed, in that field at least, to both Abrahamson's "Generalized string matching", SIAM journal on Computing, 16:(6) pages 1039--1051, 1987 and an unpublished manuscript called "Efficient string matching" by S. R. Kosaraju in the same year. <BR/><BR/>However, it is worth mentioning that these techniques were not widely understood until a series of talks and papers by Amihood Amir emerged.Unknownhttps://www.blogger.com/profile/03477220667684902066noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74872366077175186882008-09-22T23:57:00.000-05:002008-09-22T23:57:00.000-05:00pkughost wrote: This protocol only need n+2 bits. ...<I>pkughost wrote: This protocol only need n+2 bits. Is there anything wrong?</I><BR/><BR/>A requirement of communication protocols is that after each bit is sent, the player to communicate the next bit is determined by the communication so far. Your protocol does not have the required property.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14502368752824263502008-09-22T19:28:00.000-05:002008-09-22T19:28:00.000-05:00The egg problem is mentioned in Peter Winkler's M...The egg problem is mentioned in Peter Winkler's <A HREF="http://www.amazon.com/Mathematical-Mind-Benders-Peter-Winkler/dp/1568813368" REL="nofollow"> Mathematical mind-benders </A>. He refers to Konhauser, Velleman and Wagon, <A HREF="http://www.amazon.com/Which-Way-Did-Bicycle-Mathematical/dp/0883853256" REL="nofollow"> Which way did the bicycle go? </A>.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30890806207679678622008-09-22T19:04:00.000-05:002008-09-22T19:04:00.000-05:00This protocol only need n+2 bits. Is there anythin...This protocol only need n+2 bits. Is there anything wrong?<BR/><BR/>1.Alice sends first two bits of x.<BR/>2.Bob sends 1) 0, if x is bigger.<BR/> 2)y, if y is bigger.<BR/> 3)next two bits of y, if the first two bits is the same.<BR/>3.Alice makes the similar choice like Bob (swap x and y), except in the second condition Alice sends all but first two bits of x. And the following steps are all like this.<BR/>4.Make some special rules of the last one or two bits.Heng Guohttps://www.blogger.com/profile/09901594686031906876noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31471895101149749742008-09-22T17:18:00.000-05:002008-09-22T17:18:00.000-05:00sep332, if Bob's number is greater, Alice still do...sep332, if Bob's number is greater, Alice still doesn't know what the greater number is.<BR/><BR/>And to the anonymous before liad, it seems like the number of passes required by this algorithm will not be O(1); I believe that an n+O(logn) bound might exist (viz. liad's post), but it is not clear that this algorithm reaches it (indeed, you haven't supplied a mechanism for Alice or Bob to use this data to determine which number is greater at all...).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65263722695310857522008-09-22T17:17:00.000-05:002008-09-22T17:17:00.000-05:00sep332, you missed the "both" part: "They want to ...sep332, you missed the "both" part: "They want to both know max(x,y)"Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80732052582880579322008-09-22T14:15:00.000-05:002008-09-22T14:15:00.000-05:00n + 2 bits.Alice sends x to Bob. Bob sends 11 if g...n + 2 bits.<BR/><BR/>Alice sends x to Bob. Bob sends 11 if greater, 00 if less, 01 if equal.sep332https://www.blogger.com/profile/15089674288837329342noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8660865241143285192008-09-22T13:12:00.000-05:002008-09-22T13:12:00.000-05:00An n+O(log(n)) upper bound was recently given by B...An n+O(log(n)) upper bound was recently given by <A HREF="http://portal.acm.org/citation.cfm?id=1386790.1386807&coll=GUIDE&dl=GUIDE" REL="nofollow">Babaioff, Blumrosen, M. Naor and Schapira</A> in EC'08 (Thm 3.2).<BR/><BR/>It was given in the context of the communication overhead for computing payments in auctions. This problem is equivalent to solving a two player second-price auction (the price paid is the minimal value of the two).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33472193340629110212008-09-22T12:13:00.000-05:002008-09-22T12:13:00.000-05:00Here's a protocol that requires only n + O(log n) ...Here's a protocol that requires only n + O(log n) bits.<BR/><BR/>Alice finds two (log n)-bit strings a_small and a_large that do not<BR/>appear in x and sends them to Bob. Bob finds two (log n)-bit strings<BR/>b_small and b_large that do not appear in y and sends them to Alice.<BR/>Alice and Bob take turns exchanging log n bit chunks of x and y.<BR/>If either one discovers that their number is larger or smaller,<BR/>they substitute the appropriate codeword, and the party with the<BR/>larger number sends the rest.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13758053849882041112008-09-22T11:34:00.000-05:002008-09-22T11:34:00.000-05:00The Greater-Than problem is the following: Alice r...The Greater-Than problem is the following: Alice receives x, an n-bit number; Bob receives y, an n-bit number; they want to determine whether x>y.<BR/><BR/>Your problem's bit complexity is n + complexity of GT.<BR/><BR/>The Greater Than problem can be solved with polylog(n) bits of communication, by a randomized protocol (binary search for the longest common prefix). <BR/><BR/>So there's your improvement, unless your really wanted deterministic protocols. If you want deterministic, you can't go via this routa (GT requires linear complexity, like equality).Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16839839665852022122008-09-22T11:30:00.000-05:002008-09-22T11:30:00.000-05:00This comment has been removed by the author.Anatoly Vorobeyhttps://www.blogger.com/profile/15075147858952180578noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84146599496408680632008-09-22T10:54:00.000-05:002008-09-22T10:54:00.000-05:00Alas, the problems with working with bothdiscrete ...Alas, the problems with working with both<BR/>discrete and continous math.<BR/>e is an integer.<BR/>e is not 2.718...GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67136055826879743702008-09-22T10:30:00.000-05:002008-09-22T10:30:00.000-05:00Does e eggs mean 2.718281828... eggs? Making those...Does e eggs mean 2.718281828... eggs? Making those not broken is problematic, unless they have already been mapped into an omelette.Anonymousnoreply@blogger.com