中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 软件所图书馆  > 期刊论文
Subject: Computer Science
Title:
characterizations of locally testable linear- and affine-invariant families
Author: Angsheng Li ; Yicheng Pan
Keyword: Error correcting codes ; Locally testable codes ; (Algebraic) property tests
Source: Theoretical Computer Science
Issued Date: 2011
Volume: 414, Issue:1, Pages:55-75
Indexed Type: SCIENCEDIRECT ; EI
Department: aState Key Laboratory of Computer Science Institute of Software ChineseAcademy of Sciences China; bGraduate University of ChineseAcademy of Sciences China
Sponsorship: NSFC 60325206; Chinese Academy of Sciences; Institute of software, Chinese Academy of Sciences
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 (2007) [21] introduced 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 F of size q and characteristic p, and its arbitrary extension field K of size Q, if an affine-invariant family ⊆Kn→F has a k-local constraint, then it is k′-locally testable for k′=k2 QpQ2Qp+4; and that if a linear-invariant family ⊆Kn→F has a k-local characterization, then it is k′-locally testable for k′=2k2 QpQ4(Qp+1). Consequently, for any prime field F of size q, any positive integer k, we have that for any affine-invariant family over field F, 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 K 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 F of size q greater than 2, there exists a linear-invariant function family over F such that it has a strong 2-local constraint, but is not qdq-1-1-locally testable. The proof for this result provides an appealing approach toward more negative results in the theme of characterization of locally testable algebraic properties, which is rare, and of course, significant. © 2011 Elsevier B.V. All rights reserved.
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 (2007) [21] introduced 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 F of size q and characteristic p, and its arbitrary extension field K of size Q, if an affine-invariant family ⊆Kn→F has a k-local constraint, then it is k′-locally testable for k′=k2 QpQ2Qp+4; and that if a linear-invariant family ⊆Kn→F has a k-local characterization, then it is k′-locally testable for k′=2k2 QpQ4(Qp+1). Consequently, for any prime field F of size q, any positive integer k, we have that for any affine-invariant family over field F, 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 K 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 F of size q greater than 2, there exists a linear-invariant function family over F such that it has a strong 2-local constraint, but is not qdq-1-1-locally testable. The proof for this result provides an appealing approach toward more negative results in the theme of characterization of locally testable algebraic properties, which is rare, and of course, significant. © 2011 Elsevier B.V. All rights reserved.
Language: 英语
Content Type: 期刊论文
URI: http://ir.iscas.ac.cn/handle/311060/16019
Appears in Collections:软件所图书馆_期刊论文

Files in This Item:

There are no files associated with this item.


Recommended Citation:
Angsheng Li,Yicheng Pan. characterizations of locally testable linear- and affine-invariant families[J]. Theoretical Computer Science,2011-01-01,414(1):55-75.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[Angsheng Li]'s Articles
[Yicheng Pan]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[Angsheng Li]‘s Articles
[Yicheng Pan]‘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-2020  中国科学院软件研究所 - Feedback
Powered by CSpace