Proximity Oblivious Testing and the Role of Invariances

DOI10.1007/978-3-642-22935-0_49zbMath1343.68300OpenAlexW1591780301MaRDI QIDQ5894226

Tali Kaufman, Oded Goldreich

Publication date: 17 August 2011

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

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

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

Erasure-Resilient 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
• Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard
• 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