A unified framework for testing linear‐invariant properties

DOI10.1002/rsa.20507zbMath1309.62039arXiv1010.5016OpenAlexW2048325432MaRDI QIDQ4982614

Elena Grigorescu, Arnab Bhattacharyya, Asaf Shapira

Publication date: 9 April 2015

Published in: Random Structures & Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

property testinglinear invariancesubspace-hereditary properties

Mathematics Subject Classification ID

Parametric hypothesis testing (62F03) Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Randomized algorithms (68W20)

Related Items

Induced arithmetic removal: complexity 1 patterns over finite fields, Testing list \(H\)-homomorphisms, An Algebraic Characterization of Testable Boolean CSPs, A polynomial bound for the arithmetic \(k\)-cycle removal lemma in vector spaces, A tight bound for Green's arithmetic triangle removal lemma in vector spaces, Sunflowers and testing triangle-freeness of functions, Testing Linear-Invariant Properties, A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification, Local-vs-global combinatorics, Unnamed Item, Sparse affine-invariant linear codes are locally testable, Testing Linear-Invariant Non-linear Properties: A Short Report, A characterization of constant‐sample testable properties, Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition, Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity, Partially Symmetric Functions Are Efficiently Isomorphism Testable

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Testing juntas
• Non-deterministic exponential time has two-prover interactive protocols
• The Ramsey number of a graph with bounded maximum degree
• A separation theorem in property testing
• Linear equations in primes
• Generalizations of the removal lemma
• A combinatorial proof of the removal lemma for groups
• Self-testing/correcting with applications to numerical problems
• A removal lemma for systems of linear equations over finite fields
• 2-transitivity is insufficient for local testability
• A Szemerédi-type regularity lemma in abelian groups, with applications
• Tight Lower Bounds for Testing Linear Isomorphism
• Testing Halfspaces
• Testability and repair of hereditary hypergraph properties
• Property testing and its connection to learning and approximation
• Testing Reed–Muller Codes
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• Three theorems regarding testing graph properties
• Projective Geometry over  1 and the Gaussian Binomial Coefficients
• Testing Basic Boolean Formulae
• Robust Characterizations of Polynomials with Applications to Program Testing
• Succinct Representation of Codes with Applications to Testing
• Invariance in Property Testing
• Testing juntas nearly optimally
• Green's conjecture and testing linear-invariant properties
• The symmetry preserving removal lemma
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• The Difficulty of Testing for Isomorphism against a Graph That Is Given in Advance
• Every locally characterized affine-invariant property is testable
• Some 3CNF Properties Are Hard to Test
• Testing Fourier Dimensionality and Sparsity
• Efficient testing of large graphs
• A new proof of Szemerédi's theorem