8 April 2022, 10:30-11:30. ENS, S16 Capturing Homomorphism-Closed Decidable Queries with Existential Rules Existential rules are a well studied ontology-mediated query language for which the chase represents a generic computational approach for query answering. It is straightforward that existential rule queries exhibiting chase termination are decidable and can only recognize…
Debabrota Basu, Inria Lille. 11 March 2022, 10:30-11:30. ENS S16. Verifying and Explaining Unfairness of Machine Learning Algorithms In recent years, machine learning (ML) algorithms have been deployed in safety-critical and high-stake decision-making, where the fairness or unbiasedness of algorithms bears significant importance. Fairness in ML centres on detecting bias…
Mikaël Monet, Inria Lille. 25 February 2022, 10:30-11:30. ENS, S16. Shapley Values for Relational Databases and Machine Learning The Shapley value is a game-theoretic function that can be used to distribute the wealth of a team in a cooperative game. This function has strong theoretical justifications has been applied across…
12 March 2021, 10:30-11:30 Online seminar: https://bbb.di.ens.fr/b/cam-pz6-kdj Traversal algorithms and heuristics for reasoning over logic based knowledge graphs (Davide Benedetto) Knowledge Graphs (KGs) provide a concise and intuitive abstraction for a variety of domains where edges capture the (potentially recursive) relationships between the entities. This is leading to the rise…
5 March 2021, 10:30-11:30 Online seminar: https://bbb.di.ens.fr/b/cam-pz6-kdj Grammars for Document Spanners (Liat Peterfreund) We propose a new grammar-based language for defining information-extractors from documents (text) that is built upon the well-studied framework of Document Spanners for extracting structured data from text. While previously studied formalisms for document spanners are mainly…
Meghyn Bienvenu, CNRS, University of Bordeaux 18 December 2020, 10:30-11:30 Online seminar: https://bbb.di.ens.fr/b/cam-pz6-kdj Preferred repairs over inconsistent knowledge bases and connections to argumentation A fundamental notion when reasoning over inconsistent knowledge bases is that of a repair, defined as a maximal subset of the data that is consistent w.r.t. the…
Val Tannen, University of Pennsylvania 21 February 2020, 10:00-11:00 ENS, S16 Provenance Analysis for First-order Model Checking Is a given finite structure a model of a given first-order sentence? The provenance analysis of this question determines how its answer depends on the atomic facts that determine the structure. Provenance questions…
Nofar Carmeli, Technion, Israel Institute of Technology 28 February 2020, 10:30-11:30 ENS, S16 The Complexity of Answering Unions of Conjunctive Queries We discuss the complexity of enumerating (listing) the answers to a query over a relational database. In particular, we consider three variants: arbitrary order, uniformly random order, and random…
Evgenia (Eugenia) Ternovska Associate Professor | School of Computing Science Simon Fraser University 8888 University Dr., Burnaby, B.C. V5A 1S6 13 February 2020, 10:30-11:30 ENS, S16 Logic of Information Flows: Expressing Reachability and Cardinality Properties A challenge in descriptive complexity is to identify logics with low complexity that simultaneously express…
Silviu Maniu, Université Paris-Sud 7 February 2020, 10:30-11:30 ENS, S16 An Experimental Study of the Treewidth of Real-World Data Treewidth is a parameter that measures how tree-like a data instance is, and whether it can reasonably be decomposed into a data structure resembling a tree. Many computation tasks are known…
