On the Parameterized Complexity of Learning First-Order Logic
Steffen van Bergerem, Martin Grohe, Martin Ritzert · 2022
We analyse the complexity of learning first-order queries in a model-theoretic framework for supervised learning introduced by (Grohe and Turán, TOCS 2004). Previous research on the complexity of learning in this framework focussed on the question of when learning is possible in time sublinear in the background structure.