59 citations · 376 across the 66 of their papers we have counts for
6 papers · 1 filter
Constraint Solving via Fractional Edge Covers
Martin Grohe, Dániel Marx
Many important combinatorial problems can be modeled as constraint satisfaction problems. Hence identifying polynomial-time solvable classes of constraint satisfaction problems has…
Size bounds and query plans for relational joins
Albert Atserias, Martin Grohe, Dániel Marx
Relational joins are at the core of relational algebra, which in turn is the core of the standard database query language SQL. As their evaluation is expensive and very often domin…
Learning MSO-definable hypotheses on string
Martin Grohe, Christof Löding, Martin Ritzert
We study the classification problems over string data for hypotheses specified by formulas of monadic second-order logic MSO. The goal is to design learning algorithms that run in…
First-Order Query Evaluation with Cardinality Conditions
Martin Grohe, Nicole Schweikardt
We study an extension of first-order logic that allows to express cardinality conditions in a similar way as SQL's COUNT operator. The corresponding logic FOC(P) was introduced by…
The Hardness of Embedding Grids and Walls
Yijia Chen, Martin Grohe, Bingkai Lin
The dichotomy conjecture for the parameterized embedding problem states that the problem of deciding whether a given graph from some class of "pattern graphs" can be embedd…
Learning first-order definable concepts over structures of small degree
Martin Grohe, Martin Ritzert
We consider a declarative framework for machine learning where concepts and hypotheses are defined by formulas of a logic over some background structure. We show that within this f…