QQ客服 官方微博 反馈留言

	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).

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。