Invariance in Property Testing
From MaRDI portal
Publication:4933370
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
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