research
∙
03/22/2023
Three iterations of (d-1)-WL test distinguish non isometric clouds of d-dimensional points
The Weisfeiler–Lehman (WL) test is a fundamental iterative algorithm for...
share
research
∙
02/04/2023
A Theory of Link Prediction via Relational Weisfeiler-Leman
Graph neural networks are prominent models for representation learning o...
research
∙
11/30/2022
Weisfeiler and Leman Go Relational
Knowledge graphs, modeling multi-relational data, improve numerous appli...
research
∙
11/03/2022
No Agreement Without Loss: Learning and Social Choice in Peer Review
In peer review systems, reviewers are often asked to evaluate various fe...
research
∙
06/30/2022
On Computing Probabilistic Explanations for Decision Trees
Formal XAI (explainable AI) is a growing area that focuses on computing ...
research
∙
10/05/2021
Foundations of Symbolic Languages for Model Interpretability
Several queries and scores have recently been proposed to explain indivi...
research
∙
06/12/2021
Graph Neural Networks with Local Graph Parameters
Various recent proposals increase the distinguishing power of Graph Neur...
research
∙
04/16/2021
On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results
In Machine Learning, the 𝖲𝖧𝖠𝖯-score is a version of the Shapley value th...
research
∙
11/18/2020
First-Order Rewritability of Frontier-Guarded Ontology-Mediated Queries
We focus on ontology-mediated queries (OMQs) based on (frontier-)guarded...
research
∙
11/12/2020
The Complexity of Counting Problems over Incomplete Databases
We study the complexity of various fundamental counting problems that ar...
research
∙
10/23/2020
Model Interpretability through the Lens of Computational Complexity
In spite of several claims stating that some models are more interpretab...
research
∙
03/17/2020
When is Ontology-Mediated Querying Efficient?
In ontology-mediated querying, description logic (DL) ontologies are use...
research
∙
12/28/2019
The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs
Ontology-mediated querying and querying in the presence of constraints a...
research
∙
12/23/2019
Counting Problems over Incomplete Databases
We study the complexity of various fundamental counting problems that ar...
research
∙
09/25/2019
On the Expressiveness of LARA: A Unified Language for Linear and Relational Algebra
We study the expressive power of the LARA language – a recently proposed...
research
∙
04/01/2019
A More General Theory of Static Approximations for Conjunctive Queries
Conjunctive query (CQ) evaluation is NP-complete, but becomes tractable ...
research
∙
04/01/2019
Boundedness of Conjunctive Regular Path Queries
We study the boundedness problem for unions of conjunctive regular path ...
research
∙
01/10/2019
On the Turing Completeness of Modern Neural Network Architectures
Alternatives to recurrent neural networks, in particular, architectures ...
research
∙
12/05/2017