characterizations of locally testable linear- and affine-invariant families
文献类型：期刊论文
| 作者 | Angsheng Li ; Yicheng Pan |
| 刊名 | Theoretical Computer Science
 |
| 出版日期 | 2011 |
| 卷号 | 414期号:1页码:55-75 |
| 关键词 | Error correcting codes Locally testable codes (Algebraic) property tests |
| ISSN号 | 0304-3975 |
| 中文摘要 | 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. |
| 英文摘要 | 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. |
| 学科主题 | Computer Science |
| 收录类别 | SCIENCEDIRECT ; EI |
| 资助信息 | NSFC 60325206; Chinese Academy of Sciences; Institute of software, Chinese Academy of Sciences |
| 语种 | 英语 |
| 公开日期 | 2013-10-08 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/16019]  |
| 专题 | 软件研究所_软件所图书馆_期刊论文 |
| 推荐引用方式 GB/T 7714 | Angsheng Li,Yicheng Pan. characterizations of locally testable linear- and affine-invariant families[J]. Theoretical Computer Science,2011,414(1):55-75. |
| APA | Angsheng Li,&Yicheng Pan.(2011).characterizations of locally testable linear- and affine-invariant families.Theoretical Computer Science,414(1),55-75. |
| MLA | Angsheng Li,et al."characterizations of locally testable linear- and affine-invariant families".Theoretical Computer Science 414.1(2011):55-75. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。