Every locally characterized affine-invariant property is testable

DOI10.1145/2488608.2488662zbMath1293.11016arXiv1212.3849OpenAlexW2079241283MaRDI QIDQ5495813

Eldar Fischer, Hamed Hatami, Arnab Bhattacharyya, Shachar Lovett, Pooya Hatami

Publication date: 7 August 2014

Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1212.3849

zbMATH Keywords

property testingGowers normnon-classical polynomialsaffine-invariant properties

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Arithmetic combinatorics; higher degree uniformity (11B30)

Related Items (13)

Induced arithmetic removal: complexity 1 patterns over finite fields ⋮ Stability and exact Turán numbers for matroids ⋮ Testing Linear-Invariant Properties ⋮ A counting lemma for binary matroids and applications to extremal problems ⋮ Unnamed Item ⋮ Limits of Boolean functions on \(\mathbb{F}_p^n\) ⋮ Property testing lower bounds via a generalization of randomized parity decision trees ⋮ Sparse affine-invariant linear codes are locally testable ⋮ Unnamed Item ⋮ General systems of linear forms: equidistribution and true complexity ⋮ A unified framework for testing linear‐invariant properties ⋮ Testing properties of functions on finite groups ⋮ Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity

This page was built for publication: Every locally characterized affine-invariant property is testable