Invariance in property testing
From MaRDI portal
Recommendations
Cites work
- 2-transitivity is insufficient for local testability
- A combinatorial characterization of the testable graph properties, it's all about regularity
- A combinatorial proof of the removal lemma for groups
- A Szemerédi-type regularity lemma in abelian groups, with applications
- Algebraic property testing: the role of invariance
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Graph limits and parameter testing
- Green's conjecture and testing linear-invariant properties
- scientific article; zbMATH DE number 5485485 (Why is no real title available?)
- scientific article; zbMATH DE number 5485550 (Why is no real title available?)
- scientific article; zbMATH DE number 1418269 (Why is no real title available?)
- Limits on the Rate of Locally Testable Affine-Invariant Codes
- Locally Testable Cyclic Codes
- Lower bounds for testing triangle-freeness in Boolean functions
- Non-deterministic exponential time has two-prover interactive protocols
- On proximity oblivious testing
- On testing expansion in bounded-degree graphs
- On the Randomness Complexity of Property Testing
- On the Robustness of Functional Equations
- Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing
- Proof verification and the hardness of approximation problems
- Property testing and its connection to learning and approximation
- Property testing in bounded degree graphs
- Proximity oblivious testing and the role of invariances
- Robust Characterizations of Polynomials with Applications to Program Testing
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Self-testing/correcting with applications to numerical problems
- Some 3CNF Properties Are Hard to Test
- Spot-checkers
- Strong lower bounds for approximating distribution support size and the distinct elements problem
- Sublinear algorithms for testing monotone and unimodal distributions
- Succinct Representation of Codes with Applications to Testing
- Symmetric LDPC codes and local testing
- Testing Basic Boolean Formulae
- Testing Fourier Dimensionality and Sparsity
- Testing juntas
- Testing juntas nearly optimally
- Testing linear-invariant non-linear properties
- Testing low-degree polynomials over prime fields
- Testing monotone high‐dimensional distributions
- Testing monotonicity
- Testing Polynomials over General Fields
- Testing Reed–Muller Codes
- The Complexity of Approximating the Entropy
Cited in
(9)- Efficient removal lemmas for matrices
- On Sums of Locally Testable Affine Invariant Properties
- Testing Odd-Cycle-Freeness in Boolean Functions
- Algebraic property testing: the role of invariance
- A unified framework for testing linear-invariant properties
- Simple doubly-efficient interactive proof systems for locally-characterizable sets
- Efficient removal lemmas for matrices
- A characterization of constant-sample testable properties
- Proximity oblivious testing and the role of invariances
This page was built for publication: Invariance in property testing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4933370)
