期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2011
卷号：2011
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We study the communication complexity of symmetric XOR functions, namely functions f:01n01n01 that can be formulated as f(xy)=D(xy) for some predicate D:01n01 , where xy is the Hamming weight of the bitwise XOR of x and y. We give a public-coin randomized protocol in the Simultaneous Message Passing (SMP) model, with the communication cost matching the known lower bound for the quantum and two-way model up to a logarithm factor. As a corollary, this closes a quadratic gap between quantum lower bound and randomized upper bound for the one-way model, answering an open question raised in Shi and Zhang.
