Algorithmic Meta-Theorems in Bounded-Degree Property Testing

Speaker: Isolde Adler (University of Leeds)

Abstract: Property testing (for a property P) asks for a given graph, whether it has property P, or is "structurally 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 thought of as "extremely efficient", making them relevant in the context of large data sets.

In this talk I will present recent positive and negative results about testability of properties definable in first-order logic and monadic second-order logic on classes of bounded-degree graphs.

This talk is based on joint work with Polly Fahey, Frederik Harwath, Noleen Köhler and Pan Peng.

Date and time: 12/11/2020 at 15:00 (Paris time)

Link to the talk: