On Testability of First-Order Properties in Bounded-Degree Graphs
On Testability of First-Order Properties in Bounded-Degree Graphs
We study property testing of properties that are definable in first-order logic (FO) in the bounded-degree graph and relational structure models. We show that any FO property that is defined by a formula with quantifier prefix ∃∗∀∗ is testable (i.e., testable with constant query complexity), while there exists an FO …