on the derandomization of the graph test for homomorphism over groups

ISCAS OpenIR

	on the derandomization of the graph test for homomorphism over groups
	Tang Linqing
	2011
会议录名称	Theoretical Computer Science
页码	1718-1728
收录类别	ei
出版地	Netherlands
ISSN	3043975
部门归属	(1) Institute of Software, Chinese Academy of Sciences, P.O. Box 8718, Beijing, 100080, China; (2) Graduate University, Chinese Academy of Sciences, Beijing, China
摘要	In this article, we study the randomness-efficient graph tests for homomorphism over arbitrary groups (which can be used in locally testing the Hadamard code and PCP construction). We try to optimize both the amortized query complexity and the randomness complexity of the homomorphism test simultaneously. For abelian groups G=Zpm, Γ=Zp and function f:G→Γ, by using a λ-biased set S of size poly(log\|G\|), we show that, on any given bipartite graph H=(V1,V2;E), there exists a graph test for linearity over G with randomness complexity \|V1\|log\|G\|+\|V2\|O(loglog\|G\|), query complexity \|V1\|+\|V2\|+\|E\| and if the test accepts f:G→Γ with probability at least p-\|E\|+(1-p-\|E\|)δ, then f has agreement
关键词	Codes (Symbols) Random Processes Testing
语种	英语
WOS记录号	WOS:000288931500008
引用统计
内容类型	会议论文
URI标识	http://ir.iscas.ac.cn/handle/311060/14257
专题	中国科学院软件研究所
推荐引用方式 GB/T 7714	Tang Linqing. on the derandomization of the graph test for homomorphism over groups[C]. Netherlands,2011:1718-1728.