A unified framework for testing linear‐invariant properties
From MaRDI portal
Publication:4982614
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
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
