On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing

Isolde Adler, Noleen Köhler, Pan Peng

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…