Register
 ALL Title Author Keyword Sponsors Type Publication date Submitted Time Subject Conference Name Source Categories KOS Subject Advisor ORCID Advanced
 ISCAS OpenIR  > 计算机科学国家重点实验室  > 会议论文
 Title: characterizations of locally testable linear- and affine-invariant families Author: Li Angsheng ; Pan Yicheng Source: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Conference Name: 17th Annual International Computing and Combinatorics Conference, COCOON 2011 Conference Date: August 14, Issued Date: 2011 Conference Place: Dallas, TX, United states Keyword: Algebra ; Boolean functions ; Characterization ; Codes (symbols) ; Combinatorial mathematics ; Finite element method Publish Place: Germany ISSN: 3029743 ISBN: 9783642226847 Department: (1) State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, China English Abstract: The linear- or affine-invariance is the property of a function family that is closed under linear- or affine- transformations on the domain, and closed under linear combinations of functions, respectively. Both the linear- and affine-invariant families of functions are generalizations of many symmetric families, for instance, the low degree polynomials. Kaufman and Sudan [21] started the study of algebraic properties test by introducing the notions of “constraint” and “ characterization” to characterize the locally testable affine- and linear-invariant families of functions over finite fields of constant size. In this article, it is shown that, for any finite field of size q and characteristic p , and its arbitrary extension field of size Q , if an affine-invariant family has a k -local constraint, then it is k ′-locally testable for ; and that if a linear-invariant family has a k -local characterization, then it is k ′-locally testable for . Consequently, for any prime field of size q , any positive integer k , we have that for any affine-invariant family over field , the four notions of “the constraint”, “the characterization”, “the formal characterization” and “the local testability” are equivalent modulo a poly( k , q ) of the corresponding localities; and that for any linear-invariant family, the notions of “the characterization”, “the formal characterization” and “the local testability” are equivalent modulo a poly( k , q ) of the corresponding localities. The results significantly improve, and are in contrast to the characterizations in [21], which have locality exponential in Q , even if the field is prime. In the research above, a missing result is a characterization of linear-invariant function families by the more natural notion of constraint. For this, we show that a single strong local constraint is sufficient to characterize the local testability of a linear-invariant Boolean function family, and that for any finite field of size q greater than 2, there exists a linear-invariant function family over such that it has a strong 2-local constraint, but is not -locally testable. The proof for this result provides an appealing approach towards more negative results in the theme of characterization of locally testable algebraic properties, which is rare, and of course, significant. Content Type: 会议论文 URI: http://ir.iscas.ac.cn/handle/311060/14351 Appears in Collections: 计算机科学国家重点实验室 _会议论文

 Files in This Item:
File Name/ File Size Content Type Version Access License
characterizations of locally testable linear- and affine-invariant families.pdf（254KB）----限制开放-- 联系获取全文

 Recommended Citation: Li Angsheng,Pan Yicheng. characterizations of locally testable linear- and affine-invariant families[C]. 见:17th Annual International Computing and Combinatorics Conference, COCOON 2011. Dallas, TX, United states. August 14,.
 Service Recommend this item Sava as my favorate item Show this item's statistics Export Endnote File Google Scholar Similar articles in Google Scholar [Li Angsheng]'s Articles [Pan Yicheng]'s Articles CSDL cross search Similar articles in CSDL Cross Search [Li Angsheng]‘s Articles [Pan Yicheng]‘s Articles Related Copyright Policies Null Social Bookmarking

 您对该条目有什么异议，请填写以下表单，管理员会尽快联系您。 `内 容：` Email： * 单位： 验证码： 刷新
 您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。 `标 题：` * `内 容：` Email： * 验证码： 刷新