Affine subspace hereditary properties are testable

At least 13 years old · documented by

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.

References

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.