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 (16)

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

This page was built for publication: A unified framework for testing linear‐invariant properties