Testing Low Complexity Affine-Invariant Properties
Testing Low Complexity Affine-Invariant Properties
复制标题
测试低复杂度仿射不变属性
DOI：
10.1137/1.9781611973105.97
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Shachar Lovett
中科院分区：
文献类型：
--
作者：
Arnab Bhattacharyya;E. Fischer;Shachar Lovett
阶数d < p的@p是可测试的，其论证不使用关于多项式的详细代数信息，除了通过与仿射映射的组合来保留低阶。
@p of degree d < p is testable, with an argument that uses no detailed algebraic information about polynomials, except that having low degree is preserved by composition with affine maps.
The complexity of an affine-invariant property P refers to the maximum complexity, as defined by Green and Tao (Ann. Math. 2008), of the sets of linear forms used to characterize P. A more precise statement of our main result is that for any fixed prime p ≥ 2 and fixed integer R ≥ 2, any affine-invariant property P of functions f: