2 papers
cs.DS2023
The Complexity of Homomorphism Reconstructibility
Jan Böker, Louis Härtel, Nina Runde +2
Representing graphs by their homomorphism counts has led to the beautiful theory of homomorphism indistinguishability in recent years. Moreover, homomorphism counts have promising…
cs.LO2023
The Parameterized Complexity of Learning Monadic Second-Order Logic
Steffen van Bergerem, Martin Grohe, Nina Runde
Within the model-theoretic framework for supervised learning introduced by Grohe and Turán (TOCS 2004), we study the parameterized complexity of learning concepts definable in mona…