首页> 外文期刊>Computational complexity >SPARSE AFFINE-INVARIANT LINEAR CODES ARE LOCALLY TESTABLE
【24h】

SPARSE AFFINE-INVARIANT LINEAR CODES ARE LOCALLY TESTABLE

机译:稀疏的仿射不变线性码可局部测试

获取原文
获取原文并翻译 | 示例

摘要

We show that sparse affine-invariant linear properties over arbitrary finite fields are locally testable with a constant number of queries. Given a finite field F-q and an extension field F-q(n), a property is a set of functions mapping F-q(n) to F-q. The property is said to be affine-invariant if it is invariant under affine transformations of F-q, linear if it is an F-q-vector space, and sparse if its size is polynomial in the domain size. Our work completes a line of work initiated by Grigorescu et al. (2009) and followed by Kaufman & Lovett (2011). The latter showed such a result for the case when q was prime. Extending to non-prime cases turns out to be non-trivial, and our proof involves some detours into additive combinatorics, as well as a new calculus for building property testers for affine-invariant linear properties.
机译:我们表明,在任意有限域上的稀疏仿射不变线性属性可以通过恒定数量的查询进行局部测试。给定一个有限域F-q和一个扩展域F-q(n),一个属性是将F-q(n)映射到F-q的一组函数。如果该属性在F-q的仿射变换下不变,则称该属性是仿射不变的;如果它是F-q-向量空间,则称线性;如果其大小在域大小上是多项式,则称稀疏。我们的工作完成了Grigorescu等人发起的工作。 (2009年),其后是Kaufman&Lovett(2011年)。后者在q为素数的情况下显示了这样的结果。扩展到非主要情况并非易事,我们的证明涉及到绕开了加法组合运算的一些弯路,以及为仿射不变线性属性构建属性测试器的新演算。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号