Invariance in Property Testing

DOI10.1007/978-3-642-16367-8_12zbMath1309.68055OpenAlexW2128717558MaRDI QIDQ4933370

No author found.

Publication date: 12 October 2010

Published in: Property Testing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-16367-8_12

Mathematics Subject Classification ID

Randomized algorithms (68W20) General topics in the theory of data (68P01)

Related Items (7)

Testing Odd-Cycle-Freeness in Boolean Functions ⋮ Efficient Removal Lemmas for Matrices ⋮ Efficient removal lemmas for matrices ⋮ Unnamed Item ⋮ On Sums of Locally Testable Affine Invariant Properties ⋮ A unified framework for testing linear‐invariant properties ⋮ A characterization of constant‐sample testable properties

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Testing juntas
• Non-deterministic exponential time has two-prover interactive protocols
• A combinatorial proof of the removal lemma for groups
• Self-testing/correcting with applications to numerical problems
• Spot-checkers
• 2-transitivity is insufficient for local testability
• A Szemerédi-type regularity lemma in abelian groups, with applications
• A combinatorial characterization of the testable graph properties
• Graph limits and parameter testing
• Testing low-degree polynomials over prime fields
• Limits on the Rate of Locally Testable Affine-Invariant Codes
• On Testing Expansion in Bounded-Degree Graphs
• Proof verification and the hardness of approximation problems
• Property testing and its connection to learning and approximation
• Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing
• Testing Polynomials over General Fields
• Testing Reed–Muller Codes
• Locally Testable Cyclic Codes
• Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem
• Sublinear algorithms for testing monotone and unimodal distributions
• On the Randomness Complexity of Property Testing
• Testing monotone high‐dimensional distributions
• Succinct Representation of Codes with Applications to Testing
• On the Robustness of Functional Equations
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Testing Basic Boolean Formulae
• Robust Characterizations of Polynomials with Applications to Program Testing
• Symmetric LDPC Codes and Local Testing
• On proximity oblivious testing
• Testing juntas nearly optimally
• Green's conjecture and testing linear-invariant properties
• Testing Linear-Invariant Non-Linear Properties
• Some 3CNF Properties Are Hard to Test
• The Complexity of Approximating the Entropy
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
• Proximity Oblivious Testing and the Role of Invariances
• Testing Fourier Dimensionality and Sparsity
• Testing monotonicity
• Property testing in bounded degree graphs

This page was built for publication: Invariance in Property Testing