中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 软件所图书馆  > 会议论文
题名:
on the derandomization of the graph test for homomorphism over groups
作者: Tang Linqing
会议文集: Theoretical Computer Science
出版日期: 2011
关键词: Codes (symbols) ; Random processes ; Testing
出版地: Netherlands
收录类别: ei
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
语种: 英语
Citation statistics:
内容类型: 会议论文
URI标识: http://ir.iscas.ac.cn/handle/311060/14257
Appears in Collections:软件所图书馆_会议论文

Files in This Item:
File Name/ File Size Content Type Version Access License
on the derandomization of the graph test for homomorphism over groups.pdf(275KB)----限制开放-- 联系获取全文

Recommended Citation:
Tang Linqing. on the derandomization of the graph test for homomorphism over groups[C]. 见:.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[Tang Linqing]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[Tang Linqing]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace