Affine subspace hereditary properties are testable

Let pp be a prime, and let an affine-invariant property P\mathcal{P} assign to functions f:Fpn[R]f:\mathbb{F}_p^n\to [R] a property that is preserved under affine transformations. The property is affine subspace hereditary if, whenever ff satisfies P\mathcal{P}, its restriction to every affine subspace of Fpn\mathbb{F}_p^n also satisfies P\mathcal{P}. Affine subspace hereditariness conjecture. Every affine subspace hereditary property is testable with 11-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

Never refreshed

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.