tag:blogger.com,1999:blog-3722233.post109992787172664870..comments2007-04-19T22:22:55.144-05:00Lancehttp://www.blogger.com/profile/06752030912874378610lance@fortnow.comBlogger2125tag:blogger.com,1999:blog-3722233.post-1100031347542009522004-11-09T14:15:00.000-06:002004-11-09T14:15:00.000-06:00Jain, Radhakrishnan, and Sen have also shown an Omega(n/k^2) quantum c.c. lower bound for the set disjointness problem when the protocols are restricted to be k rounds. This result, on the one hand, is more general than Razborov's, but on the other, yields only an Omega(n^{1/3}) l.b. for arbitrary-round q.c.c. for set disjointness. See http://www.iqc.ca/conferences/qip/presentations/radhakrishnan.pdf for Jaikumar Radhakrishnan's presentation of this work, and http://portal.acm.org/citation.cfm?id=946243.946331 for the FOCS abstract.<br /><br />SivaAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1100003554853590652004-11-09T06:32:00.000-06:002004-11-09T06:32:00.000-06:00Actually the hybrid method is due to Bennett, Bernstein, Brassard, and Vazirani; it was a predecessor of Andris's quantum adversary method.Scotthttp://www.blogger.com/profile/09428022255536654006noreply@blogger.com