On Proximity-Oblivious Testing

DOI10.1137/100789646zbMath1223.68045OpenAlexW2055587090MaRDI QIDQ3020015

Oded Goldreich, Dana Ron

Publication date: 29 July 2011

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/100789646

zbMATH Keywords

graph propertiesproperty testingdetection probabilityproximity oblivious testsproximity parameter

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (20)

Testing graphs against an unknown distribution ⋮ Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs ⋮ Parameterized property testing of functions ⋮ Proofs of proximity for context-free languages and read-once branching programs ⋮ Testing Linear-Invariant Properties ⋮ On the Effect of the Proximity Parameter on Property Testers ⋮ Testing linear inequalities of subgraph statistics ⋮ Unnamed Item ⋮ Erasure-Resilient Property Testing ⋮ Unnamed Item ⋮ Efficient Testing without Efficient Regularity ⋮ Non-interactive proofs of proximity ⋮ A non-extendibility certificate for submodularity and applications ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Two-sided error proximity oblivious testing ⋮ On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs ⋮ Every Set in P Is Strongly Testable Under a Suitable Encoding ⋮ Unnamed Item ⋮ An explicit construction of graphs of bounded degree that are far from being Hamiltonian

This page was built for publication: On Proximity-Oblivious Testing