Institutional Repository
| on the derandomization of the graph test for homomorphism over groups | |
| Tang Linqing | |
| 2011 | |
| Source | Theoretical Computer Science |
| Pages | 1718-1728 |
| Indexed Type | ei |
| Publish Place | Netherlands |
| ISSN | 3043975 |
| Department | (1) Institute of Software, Chinese Academy of Sciences, P.O. Box 8718, Beijing, 100080, China; (2) Graduate University, Chinese Academy of Sciences, Beijing, China |
| English Abstract | 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 |
| Keyword | Codes (Symbols) Random Processes Testing |
| Language | 英语 |
| WOS ID | WOS:000288931500008 |
| Citation statistics | |
| Content Type | 会议论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/14257 |
| Collection | 中国科学院软件研究所 |
| Recommended Citation GB/T 7714 | Tang Linqing. on the derandomization of the graph test for homomorphism over groups[C]. Netherlands,2011:1718-1728. |
| Files in This Item: | ||||||
| File Name/Size | DocType | Version | Access | License | ||
| on the derandomizati（275KB） | 开放获取 | -- | Application Full Text | |||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment