7 papers
A logical approach to concentration
Michael Benedikt, Maksim Zhukovskii
Concentration results say that a sequence of random variables becomes progressively concentrated around the mean. Such results are common in the study of functions of random graphs…
How Expressive Are Graph Neural Networks in the Presence of Node Identifiers?
Arie Soeteman, Michael Benedikt, Martin Grohe +1
Graph neural networks (GNNs) are a widely used class of machine learning models for graph-structured data, based on local aggregation over neighbors. GNNs have close connections to…
From learnable objects to learnable random objects
Aaron Anderson, Michael Benedikt
We consider the relationship between learnability of a "base class" of functions on a set , and learnability of a class of statistical functions derived from the base class. For…
Monotone Rewritability and the Analysis of Queries, Views, and Rules
Michael Benedikt, Stanislav Kikot, Johannes Marti +1
We study the interaction of views, queries, and background knowledge in the form of existential rules. The motivating questions concern monotonic determinacy of a query using views…
Revisiting the Expressiveness Landscape of Data Graph Queries
Michael Benedikt, Anthony Widjaja Lin, Di-De Yen
The study of graph queries in database theory has spanned more than three decades, resulting in a multitude of proposals for graph query languages. We can identify three main famil…
Model Equivalences
Michael Benedikt, Ehud Hrushovski
We look at equivalence relations on the set of models of a theory -- MERs, for short -- such that the class of equivalent pairs is itself an elementary class, in a language appropr…
Synthesizing nested relational queries from implicit specifications: via model theory and via proof theory
Michael Benedikt, Cécilia Pradic, Christoph Wernhard
Derived datasets can be defined implicitly or explicitly. An implicit definition (of dataset O in terms of datasets I) is a logical specification involving two distinguished sets o…