Proximity Oblivious Testing and the Role of Invariances

DOI10.1007/978-3-642-22670-0_19zbMath1343.68301OpenAlexW2177650368MaRDI QIDQ5894230

Oded Goldreich, Tali Kaufman

Publication date: 19 August 2011

Published in: Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22670-0_19

zbMATH Keywords

graph propertiesproperty testinglocally testable codeslong-codesparse linear codes

Mathematics Subject Classification ID

Other types of codes (94B60) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items

Invariance in Property Testing, On the Average-Case Complexity of Property Testing

Cites Work

• Unnamed Item
• Unnamed Item
• Self-testing/correcting with applications to numerical problems
• 2-transitivity is insufficient for local testability
• A combinatorial characterization of the testable graph properties
• Property testing and its connection to learning and approximation
• On the Query Complexity of Testing Orientations for Being Eulerian
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Three theorems regarding testing graph properties
• Testing Basic Boolean Formulae
• Robust Characterizations of Polynomials with Applications to Program Testing
• lgorithmic and Analysis Techniques in Property Testing
• Property testing in bounded degree graphs