Property Testing for Structures of Bounded Degree

Property testing (for a property P) asks for a given input, whether it has property P, or is "far" from having that property. A "testing algorithm" is a probabilistic algorithm that answers this question with high probability correctly, by only looking at small parts of the input.  Testing algorithms are extremely efficient, making them relevant in the context of big data. We study property testing of logically defined properties in the bounded degree model, and we show that every property definable in first-order logic is testable with a constant number of queries in constant time.

This is joint work with Frederik Harwath.