COMMUNICATION COMPLEXITIES OF SYMMETRIC XOR FUNCTIONS | |
Zhang, Zhiqiang ; Shi, Yaoyun | |
2010-10-12 ; 2010-10-12 | |
关键词 | communication complexity XOR functions quantum communication Computer Science, Theory & Methods Physics, Particles & Fields Physics, Mathematical |
中文摘要 | We call F : {0, 1}(n) x {0, 1}(n) {0, 1}(n) -> {0,1} symmetric XOR function if for a function S : (0, 1, ... , n} -> {0, 1), F(x, y) = S(vertical bar x circle plus y vertical bar), for any x, y is an element of {0, 1}(n), where vertical bar x circle plus y vertical bar is the Hamming weight of the bit-wise XOR of x and y. We show that for any such function, (a) the deterministic communication complexity is always circle minus(n) except for four simple functions that have a constant complexity, and (b) up to a polylog factor, both the error-bounded randomized complexity and quantum communication with entanglement. complexity are circle minus(r(0) + r(1)), where r(0) and r(1) are the minimum integers such that r(0), r(1) <= n/2 and S(k) = S(k + 2) for all k is an element of (r(0), n-r(1)). |
语种 | 英语 ; 英语 |
出版者 | RINTON PRESS, INC ; PARAMUS ; 565 EDMUND TERRACE, PARAMUS, NJ 07652 USA |
内容类型 | 期刊论文 |
源URL | [http://hdl.handle.net/123456789/82884] ![]() |
专题 | 清华大学 |
推荐引用方式 GB/T 7714 | Zhang, Zhiqiang,Shi, Yaoyun. COMMUNICATION COMPLEXITIES OF SYMMETRIC XOR FUNCTIONS[J],2010, 2010. |
APA | Zhang, Zhiqiang,&Shi, Yaoyun.(2010).COMMUNICATION COMPLEXITIES OF SYMMETRIC XOR FUNCTIONS.. |
MLA | Zhang, Zhiqiang,et al."COMMUNICATION COMPLEXITIES OF SYMMETRIC XOR FUNCTIONS".(2010). |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论