5 papers
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…
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…
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…
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…