Affine subspace hereditary properties are testable
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.