Affine subspace hereditary properties are testable
Let be a prime, and let an affine-invariant property assign to functions a property that is preserved under affine transformations. The property is affine subspace hereditary if, whenever satisfies , its restriction to every affine subspace of also satisfies . Affine subspace hereditariness conjecture. Every affine subspace hereditary property is testable with -sided error. This conjecture proposes that affine subspace hereditariness is the minimal structural condition needed for one-sided testability of affine-invariant properties; the paper presents progress toward it and reduces the question to testability of properties defined by induced affine constraints.
References
Primary source
Arnab Bhattacharyya, Eldar Fischer and Shachar Lovett, “Testing Low Complexity Affine-Invariant Properties”, arXiv:1201.0330 (2012).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.