Complexity & Logic

Data management has been connected to logic since the advent of the relational model as main representation system for real-world data, and of first-order logic as the logical core of database querying languages 38. Since these early developments, logic has also been successfully used to capture a large variety of query modes, such as data aggregation 65, recursive queries (Datalog), or querying of XML databases 47. Logical formalisms facilitate reasoning about the expressiveness of a query language or about its complexity.

The main problem of interest in data management is that of query evaluation, i.e., computing the results of a query over a database. The complexity of this problem has far-reaching consequences. For example, it is because first-order logic is in the ${\mathrm{AC}}_0$ complexity class that evaluation of SQL queries can be parallelized efficiently. It is usual 77 in data management to distinguish data complexity, where the query is considered to be fixed, from combined complexity, where both the query and the data are considered to be part of the input. Thus, though conjunctive queries, corresponding to a simple SELECT-FROM-WHERE fragment of SQL, have PTIME data complexity, they are NP-hard in combined complexity. Making this distinction is important, because data is often far larger (up to the order of terabytes) than queries (rarely more than a few hundred bytes). Beyond simple query evaluation, a central question in data management remains that of complexity; tools from algorithm analysis, and complexity theory can be used to pinpoint the tractability frontier of data management tasks.

Automata Theory

Automata theory and formal languages arise as important components of the study of many data management tasks: in temporal databases 37, queries, expressed in temporal logics, can often by compiled to automata; in graph databases 43, queries are naturally given as automata; typical query and schema languages for XML databases such as XPath and XML Schema can be compiled to tree automata 69, or for more complex languages to data tree automata 63. Another reason of the importance of automata theory, and tree automata in particular, comes from Courcelle's results 51 that show that very expressive queries (from the language of monadic second-order language) can be evaluated as tree automata over tree decompositions of the original databases, yielding linear-time algorithms (in data complexity) for a wide variety of applications.

Verification

Complex data management also has connections to verification and static analysis. Besides query evaluation, a central problem in data management is that of deciding whether two queries are equivalent38. This is critical for query optimization, in order to determine if the rewriting of a query, maybe cheaper to evaluate, will return the same result as the original query. Equivalence can easily be seen to be an instance of the problem of (non-)satisfiability: $q\equiv q^{\text{'}}$ if and only if $(q\wedge \neg q^{\text{'}})\vee (\neg q\wedge q^{\text{'}})$ is not satisfiable. In other words, some aspects of query optimization are static analysis issues. Verification is also a critical part of any database application where it is important to ensure that some property will never (or always) arise 49.

Workflows

The orchestration of distributed activities (under the responsibility of a conductor) and their choreography (when they are fully autonomous) are complex issues that are essential for a wide range of data management applications including notably, e-commerce systems, business processes, health-care and scientific workflows. The difficulty is to guarantee consistency or more generally, quality of service, and to statically verify critical properties of the system. Different approaches to workflow specifications exist: automata-based, logic-based, or predicate-based control of function calls 35.

Probability & Provenance

To deal with the uncertainty attached to data, proper models need to be used (such as attaching provenance information to data items and viewing the whole database as being probabilistic) and practical methods and systems need to be developed to both reliably estimate the uncertainty in data items and properly manage provenance and uncertainty information throughout a long, complex system.

The simplest model of data uncertainty is the NULLs of SQL databases, also called Codd tables 38. This representation system is too basic for any complex task, and has the major inconvenient of not being closed under even simple queries or updates. A solution to this has been proposed in the form of conditional tables62 where every tuple is annotated with a Boolean formula over independent Boolean random events. This model has been recognized as foundational and extended in two different directions: to more expressive models of provenance than what Boolean functions capture, through a semiring formalism 58, and to a probabilistic formalism by assigning independent probabilities to the Boolean events 59. These two extensions form the basis of modern provenance and probability management, subsuming in a large way previous works 50, 44. Research in the past ten years has focused on a better understanding of the tractability of query answering with provenance and probabilistic annotations, in a variety of specializations of this framework 7564, 41.

Machine Learning

Statistical machine learning, and its applications to data mining and data analytics, is a major foundation of data management research. A large variety of research areas in complex data management, such as wrapper induction 71, crowdsourcing 42, focused crawling 57, or automatic database tuning 45 critically rely on machine learning techniques, such as classification 61, probabilistic models 56, or reinforcement learning 76.

Machine learning is also a rich source of complex data management problems: thus, the probabilities produced by a conditional random field 67 system result in probabilistic annotations that need to be properly modeled, stored, and queried.

Finally, complex data management also brings new twists to some classical machine learning problems. Consider for instance the area of active learning72, a subfield of machine learning concerned with how to optimally use a (costly) oracle, in an interactive manner, to label training data that will be used to build a learning model, e.g., a classifier. In most of the active learning literature, the cost model is very basic (uniform or fixed-value costs), though some works 73 consider more realistic costs. Also, oracles are usually assumed to be perfect with only a few exceptions 54. These assumptions usually break when applied to complex data management problems on real-world data, such as crowdsourcing.

6.1.1 ProvSQL

• Keywords:
  Databases, Provenance, Probability
• Functional Description:
  The goal of the ProvSQL project is to add support for (m-)semiring provenance and uncertainty management to PostgreSQL databases, in the form of a PostgreSQL extension/module/plugin.
• News of the Year:
  Merging of the in-memory storage of the provenance circuit in the main branch, including data persistence when restarting the PostgreSQL server. Support for PostgreSQL 14. Support for new version of d4. Miscellaneous enhancements and bug fixes.
• URL:
  https://­github.­com/­PierreSenellart/­provsql
• Publications:
  hal-01672566, hal-01851538
• Contact:
  Pierre Senellart
• Participants:
  Pierre Senellart, Silviu Maniu, Yann Ramusat

6.1.2 apxproof

• Keyword:
  LaTeX
• Functional Description:
  apxproof is a LaTeX package facilitating the typesetting of research articles with proofs in appendix, a common practice in database theory and theoretical computer science in general. The appendix material is written in the LaTeX code along with the main text which it naturally complements, and it is automatically deferred. The package can automatically send proofs to the appendix, can repeat in the appendix the theorem environments stated in the main text, can section the appendix automatically based on the sectioning of the main text, and supports a separate bibliography for the appendix material.
• Release Contributions:
  Compatibility fixes with xypic, fancyvrb, memoir, natbib
• News of the Year:

  1.2.2 release: compatibility with AMS document classes, avoid creating useless appendix section when files are included, fix handling of optional arguments of repeated theorems containing optional arguments

  1.2.3 release: compatibility with tocbibind, forwardlinking option

• URL:
  https://­github.­com/­PierreSenellart/­apxproof
• Contact:
  Pierre Senellart
• Participant:
  Pierre Senellart

6.1.3 TheoremKB

• Keyword:
  Information extraction
• Functional Description:
  TheoremKB is a collection of tools to extract semantic information from (mathematical) research articles.
• News of the Year:
  Add computer-vision based object detection. Add NLP-based techniques such as transformers and LSTM networks for sequence prediction.
• URL:
  https://­github.­com/­PierreSenellart/­theoremkb
• Publications:
  hal-02956526, hal-02940819, hal-03293643
• Contact:
  Pierre Senellart
• Participants:
  Pierre Senellart, Theo Delemazure, Lucas Pluvinage, Shrey Mishra

Dimensionality reduction

Non-negative matrix factorization (NMF) has become a well-established class of methods for the analysis of non-negative data. In particular, a lot of effort has been devoted to probabilistic NMF, namely estimation or inference tasks in probabilistic models describing the data, based for example on Poisson or exponential likelihoods. When dealing with time series data, several works have proposed to model the evolution of the activation coefficients as a non-negative Markov chain, most of the time in relation with the Gamma distribution, giving rise to so-called temporal NMF models. In 14, we review four Gamma Markov chains of the NMF literature, and show that they all share the same drawback: the absence of a well-defined station- ary distribution. We then introduce a fifth process, an overlooked model of the time series literature named BGAR(1), which overcomes this limitation. These temporal NMF models are then compared in a MAP framework on a prediction task, in the context of the Poisson likelihood.

Bandits

Motivated by A/B/n testing applications, we consider in 27 a finite set of distributions (called arms), one of which is treated as a control. We assume that the population is stratified into homogeneous subpopulations. At every time step, a subpopulation is sampled and an arm is chosen: the resulting observation is an independent draw from the arm conditioned on the subpopulation. The quality of each arm is assessed through a weighted combination of its subpopulation means. We propose a strategy for sequentially choosing one arm per time step so as to discover as fast as possible which arms, if any, have higher weighted expectation than the control. This strategy is shown to be asymptotically optimal in the following sense: if ${\tau }_{\delta }$ is the first time when the strategy ensures that it is able to output the correct answer with probability at least $1-\delta$, then $E\left[{\tau }_{\delta }\right]$ grows linearly with $log(1/\delta )$ at the exact optimal rate. This rate is identified in three different settings: (1) when the experimenter does not observe the subpopulation information, (2) when the subpopulation of each sample is observed but not chosen, and (3) when the experimenter can select the subpopulation from which each response is sampled. We illustrate the efficiency of the proposed strategy with numerical simulations on synthetic and real data collected from an A/B/n experiment. Contextual sequential decision problems with categorical or numerical observations are ubiquitous and Generalized Linear Bandits (GLB) offer a solid theoretical framework to address them. In contrast to the case of linear bandits, existing algorithms for GLB have two drawbacks undermining their applicability. First, they rely on excessively pessimistic concentration bounds due to the non-linear nature of the model. Second, they require either non-convex projection steps or burn-in phases to enforce boundedness of the estimators. Both of these issues are worsened when considering non-stationary models, in which the GLB parameter may vary with time. In 26, we focus on self-concordant GLB (which include logistic and Poisson regression) with forgetting achieved either by the use of a sliding window or exponential weights. We propose a novel confidence-based algorithm for the maximum-likehood estimator with forgetting and analyze its perfomance in abruptly changing environments. These results as well as the accompanying numerical simulations highlight the potential of the proposed approach to address non-stationarity in GLB.

There has been a recent surge of interest in nonparametric bandit algorithms based on subsampling. One drawback however of these approaches is the additional complexity required by random subsampling and the storage of the full history of rewards. Our first contribution in 18 is to show that a simple deterministic subsampling rule, proposed in recent work of under the name of “last-block subsampling”, is asymptotically optimal in one-parameter exponential families. In addition, we prove that these guarantees also hold when limiting the algorithm memory to a polylogarithmic function of the time horizon. These findings open up new perspectives, in particular for non-stationary scenarios in which the arm distributions evolve over time. We propose a variant of the algorithm in which only the most recent observations are used for subsampling, achieving optimal regret guarantees under the assumption of a known number of abrupt changes. Extensive numerical simulations highlight the merits of this approach, particularly when the changes are not only affecting the means of the rewards.

Auctions

First-price auctions have largely replaced traditional bidding approaches based on Vickrey auctions in programmatic advertising. As far as learning is concerned, first-price auctions are more challenging because the optimal bidding strategy does not only depend on the value of the item but also requires some knowledge of the other bids. They have already given rise to several works in sequential learning, many of which consider models for which the value of the buyer or the opponents' maximal bid is chosen in an adversarial manner. Even in the simplest settings, this gives rise to algorithms whose regret grows as $\sqrt{T}$ with respect to the time horizon $T$. Focusing on the case where the buyer plays against a stationary stochastic environment, we show in 16 how to achieve significantly lower regret: when the opponents' maximal bid distribution is known we provide an algorithm whose regret can be as low as ${log}_2\left(T\right)$; in the case where the distribution must be learnt sequentially, a generalization of this algorithm can achieve $T^{1/3+ϵ}$ regret, for any $ϵ>0$. To obtain these results, we introduce two novel ideas that can be of interest in their own right. First, by transposing results obtained in the posted price setting, we provide conditions under which the first-price biding utility is locally quadratic around its optimum. Second, we leverage the observation that, on small sub-intervals, the concentration of the variations of the empirical distribution function may be controlled more accurately than by using the classical Dvoretzky–Kiefer–Wolfowitz inequality. Numerical simulations confirm that our algorithms converge much faster than alternatives proposed in the literature for various bid distributions, including for bids collected on an actual programmatic advertising platform.

Developing efficient sequential bidding strategies for repeated auctions is an important practical challenge in various marketing tasks. In this setting, the bidding agent obtains information, on both the value of the item at sale and the behavior of the other bidders, only when she wins the auction. Standard bandit theory does not apply to this problem due to the presence of action-dependent censoring. In 15, we consider second-price auctions and propose novel, efficient UCB-like algorithms for this task. These algorithms are analyzed in the stochastic setting, assuming regularity of the distribution of the opponents' bids. We provide regret upper bounds that quantify the improvement over the baseline algorithm proposed in the literature. The improvement is particularly significant in cases when the value of the auctioned item is low, yielding a spectacular reduction in the order of the worst-case regret. We further provide the first parametric lower bound for this problem that applies to generic UCB-like strategies. As an alternative, we propose more explainable strategies which are reminiscent of the Explore Then Commit bandit algorithm. We provide a critical analysis of this class of strategies, showing both important advantages and limitations. In particular, we provide a minimax lower bound and propose a nearly minimax-optimal instance of this class.

Privacy

The calibration of noise for a privacy-preserving mechanism depends on the sensitivity of the query and the prescribed privacy level. A data steward must make the non-trivial choice of a privacy level that balances the requirements of users and the monetary constraints of the business entity. In 13, firstly, we analyze roles of the sources of randomness, namely the explicit randomness induced by the noise distribution and the implicit randomness induced by the data-generation distribution, that are involved in the design of a privacy-preserving mechanism. The finer analysis enables us to provide stronger privacy guarantees with quantifiable risks. Thus, we propose privacy at risk that is a probabilistic calibration of privacy-preserving mechanisms. We provide a composition theorem that leverages privacy at risk. We instantiate the probabilistic calibration for the Laplace mechanism by providing analytical results. Secondly, we propose a cost model that bridges the gap between the privacy level and the compensation budget estimated by a GDPR compliant business entity. The convexity of the proposed cost model leads to a unique fine-tuning of privacy level that minimizes the compensation budget. We show its effectiveness by illustrating a realistic scenario that avoids overestimation of the compensation budget by using privacy at risk for the Laplace mechanism. We quantitatively show that composition using the cost optimal privacy at risk provides stronger privacy guarantee than the classical advanced composition. Although the illustration is specific to the chosen cost model, it naturally extends to any convex cost model. We also provide realistic illustrations of how a data steward uses privacy at risk to balance the trade-off between utility and privacy.

Data provenance

In 25, we investigate the efficient computation of the provenance of rich queries over graph databases. We show that semiring-based provenance annotations enrich the expressiveness of routing queries over graphs. Several algorithms have previously been proposed for provenance computation over graphs, each yielding a trade-off between time complexity and generality. Here, we address the limitations of these algorithms and propose a new one, partially bridging a complexity and expressiveness gap and adding to the algorithmic toolkit for solving this problem. Importantly, we provide a comprehensive taxonomy of semirings and corresponding algorithms, establishing which practical approaches are needed in different cases. We implement and comprehensively evaluate several practical applications of the problem (e.g., shortest distances, top-shortest distances, Boolean or integer path features), each corresponding to a specific semiring and algorithm, that depends on the properties of the semiring. On several real-world and synthetic graph datasets, we show that the algorithms we propose exhibit large practical benefits for processing rich graph queries.

Data streams

Mining high-dimensional data streams poses a fundamental challenge to machine learning as the presence of high numbers of attributes can remarkably degrade any mining task’s performance. In the past several years, dimension reduction (DR) approaches have been successfully applied for different purposes (e.g., visualization). Due to their high-computational costs and numerous passes overlarge data, these approaches pose a hindrance when processing infinite data streams that are potentially high-dimensional. The latter increases the resource-usage of algorithms that could suffer from the curse of dimensionality. To cope with these issues, some techniques for incremental DR have been proposed. In 17, we provide a survey on reduction approaches designed to handle data streams and highlight the key benefits of using these approaches for stream mining algorithms.

Information extraction

We propose in 24 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 based on regular expressions, we use an extension of context-free grammars, called extraction grammars, to define the new class of context-free spanners. Extraction grammars are simply context-free grammars extended with variables that capture interval positions of the document, namely spans. While regular expressions are efficient for tokenizing and tagging, context-free grammars are also efficient for capturing structural properties. Indeed, we show that context-free spanners are strictly more expressive than their regular counterparts. We reason about the expressive power of our new class and present a pushdown-automata model that captures it. We show that extraction grammars can be evaluated with polynomial data complexity. Nevertheless, as the degree of the polynomial depends on the query, we present an enumeration algorithm for unambiguous extraction grammars that, after quintic preprocessing, outputs the results sequentially, without repetitions, with a constant delay between every two consecutive ones.

Scholarly articles in mathematical fields often feature mathematical statements (theorems, propositions, etc.) and their proofs. In 23, we present preliminary work for extracting such information from PDF documents, with several types of approaches: vision (using YOLO), natural language (with transformers), and styling information (with linear conditional random fields). Our main task is to identify which parts of the paper to label as theorem-like environments and proofs. We rely on a dataset collected from arXiv, with LaTeX sources of research articles used to train the models

Sociological aspects of data science

Technology characterizes and facilitates our daily lives, but its pervasive use can result in the introduction or the exacerbation of social problems. Because of their intrinsic complexity, these issues require to be addressed from different but complementary perspectives, which are provided to us by two disciplines of very different nature: data science and sociology. Specifically, Riccardo Corona's Master thesis 33 would like to be a bridge between the technical field of data analysis and a specific category of social problems, namely that of discrimination, and, in particular, gender discrimination. To move within this context, we use an approach that has data analysis as its starting point, and which finds in sociology a useful supporting instrument, as well as a source of requirements. We investigate in depth the sociological reasons behind gender discrimination in the specific society of our interest – the American one – introducing and exploring what is commonly referred as ‘gender gap’, and we carry out several experiments on data related to U.S. employees, focusing on the economic perspective (gender pay gap) but taking into account the different other facets of the problem. The main contributions of this thesis derive from the application of preprocessing techniques and the use of tools created with the aim of detecting bias in data, with which we try to understand which design choices have the greatest impact on the so-called ‘fairness’ of the results, and of which we highlight strengths and weaknesses, emphasizing the importance of a multidisciplinary approach to problems of this kind, that is essential to obtain information on the complex context in which data are embedded.

9.1.1 Participation in other International Programs

• DesCartes
  (2021–2026) is a project managed by CNRS@CREATE, a CNRS subsidiary in Singapore and funded by Singapore's National Research Foundation, with 50 million total budget. Pierre Senellart is involved in the project as one of the French PIs. See https://­www.­cnrsatcreate.­cnrs.­fr/­descartes/.

9.1.2 Informal international partners

Valda has strong collaborations with the following international groups:

• Univ. Edinburgh, United Kingdom:
  Paolo Guagliardo, Andreas Pieris
• Univ. Oxford, United Kingdom:
  Michael Benedikt and Georg Gottlob
• TU Dresden, Germany:
  Markus Krötzsch and Sebastian Rudolph
• Dortmund University, Germany:
  Thomas Schwentick
• Bayreuth University, Germany:
  Wim Martens
• Univ. Bergen, Norway:
  Ana Ozaki
• Univ. Roma La Sapienza, Italy:
  Marco Console
• Warsaw University, Poland:
  Mikołaj Bojańczyk and Szymon Toruńczyk
• Tel Aviv University, Israel:
  Daniel Deutch and Tova Milo
• NYU, USA:
  Julia Stoyanovich
• Univ. California San Diego, USA:
  Victor Vianu
• Pontifical Catholic University of Chile:
  Marcelo Arenas, Pablo Barceló
• National University of Singapore:
  Stéphane Bressan

9.2.1 Visits of international scientists

9.3.1 Other european programs/initiatives

A bilateral French–German ANR project, entitled EQUUS – Efficient Query answering Under UpdateS has started in 2020. It involves CNRS (CRIL, CRIStAL, IMJ), Télécom Paris, HU Berlin, and Bayreuth University, in addition to Inria Valda.

9.4.1 ANR

Valda has been part of four national ANR projects in 2021:

• HEADWORK
  (2016–2021; 38 k€ for Valda, budget managed by Inria), together with IRISA (Druid, coordinator), Inria Lille (Links & Spirals), and Inria Rennes (Sumo), and two application partners: MNHN (Cesco) and FouleFactory. The topic is workflows for crowdsourcing. See http://­headwork.­gforge.­inria.­fr/.
• BioQOP
  (2017–2021; 66 k€ for Valda, budget managed by ENS), with Idemia (coordinator) and GREYC, on the optimization of queries for privacy-aware biometric data management. See http://­bioqop.­di.­ens.­fr/.
• CQFD
  (2018–2022; 19 k€ for Valda, budget managed by Inria), with Inria Sophia (GraphIK, coordinator), LaBRI, LIG, Inria Saclay (Cedar), IRISA, Inria Lille (Spirals), and Télécom ParisTech, on complex ontological queries over federated and heterogeneous data. See http://­www.­lirmm.­fr/­cqfd/.
• QUID
  (2018–2022; 49 k€ for Valda, budget managed by Inria), LIGM (coordinator), IRIF, and LaBRI, on incomplete and inconsistent data. See https://­quid.­labri.­fr/­home.­html

Camille Bourgaux has been participating in the AI Chair of Meghyn Bienvenu on INTENDED (Intelligent handling of imperfect data) since 2020.

9.4.2 Others

• Dissemin
  (2021–2024; 124€ for Valda, budget managed by ENS), sole partner, on the development of the https://­dissem.­in/ platform for open science promotion. Funded by the Fonds National Science Ouverte.

10.1.1 Scientific events: organisation

10.1.2 Scientific events: selection

10.1.3 Journal

10.1.4 Leadership within the scientific community

• Serge Abiteboul is a member of the French Academy of Sciences, of the Academia Europaea, of the scientific council of the Société Informatique de France, and an ACM Fellow.
• Leonid Libkin is a Fellow of the Royal Society of Edinburgh, a member of the Academia Europaea, of the UK Computing research committee, and an ACM Fellow.
• Pierre Senellart is a junior member of the Institut Universitaire de France.

10.1.5 Research administration

• Olivier Cappé is a scientific deputy director of CNRS division of Information Sciences and Technologies (INS2I).
• Luc Segoufin is a member of the CNHSCT of Inria.
• Pierre Senellart was a member of the board (till August 2021) and is now president (since September 2021) of section 6 of the National Committee for Scientific Research.
• Pierre Senellart is a member of the board of the conference of presidents of the national committee (CPCN) and as such a member of the coordination of managing parties of the national committee (C3N) Site d'information sous l'autorité du porte-parole de la C3N
• Pierre Senellart is deputy director of the DI ENS laboratory, joint between ENS, CNRS, and Inria.
• Pierre Senellart is a member of the board of the DIM RFSI (Réseau Francilien en Sciences Informatiques).

10.2.1 Teaching

• Licence: Algorithms, 42 heqTD, L2, CPES, PSL – Pierre Senellart

• Licence: Databases, 74 heqTD, L3, École normale supérieure – Leonid Libkin, Yann Ramusat, Michaël Thomazo

• Master: Data wrangling, Data privacy, 36 heqTD, M2, IASD – Leonid Libkin, Pierre Senellart
• Master: Anonymization, privacy, 36 heqTD, M2, IASD – Ashish Dandekar, Pierre Senellart
• Master: Knowledge graphs, description logics, reasoning on data, 36 heqTD, M2, IASD – Camille Bourgaux, Michaël Thomazo

Pierre Senellart has had various teaching responsibilities (L3 internships, M1 projects, M2 administration, entrance competition) at ENS. Leonid Libkin was responsible of the graduate program in computer science of PSL University until 2021; Leonid Libkin and Pierre Senellart are in the managing board of the graduate program. Leonid Libkin is co-responsible of the international entrance competition at ENS. Yann Ramusat was the secretary of the entrance competition at ENS for computer science. Most members of the group are also involved in tutoring ENS students, advising them on their curriculum, their internships, etc. They are also occasionally involved with reviewing internship reports, supervising student projects, etc.

10.2.2 Supervision

• PhD in progess: Juliette Achddou, Application of reinforcement learning strategies to the context of Real-Time Bidding, started in September 2018, Olivier Cappé & Aurélien Garivier; Juliette and Olivier left the group in September 2021
• PhD in progress: Anatole Dahan, Logical foundations of the polynomial hierarchy, started in October 2020, Arnaud Durand & Luc Segoufin
• PhD in progress: Baptiste Lafosse, Compiler dedicated to the evaluation of SQL queries, started in October 2021, Pierre Senellart & Jean-Marie Lagniez
• PhD in progress: Shrey Mishra, Towards a knowledge base of mathematic results, started in January 2021, Pierre Senellart
• PhD in progress: Yann Ramusat, Provenance-based routing in probabilistic graphs, started in September 2018, Silviu Maniu & Pierre Senellart
• PhD in progress: Alexandra Rogova, Query analytics in Cypher, started October 2021, Amelie Gheerbrant & Leonid Libkin
• PhD in progess: Yoan Russac, Sequential methods for robust decision making, started in December 2018, Olivier Cappé; Yoan and Olivier left the group in September 2021

10.2.3 Juries

• HdR: Stefan Mengel [reviewer], Université d'Artois,Pierre Senellart
• HdR: Federico Ulliana [reviewer], Université de Montpellier,Pierre Senellart
• PhD: Amit Kumar [president], Université Caen Normandie, Pierre Senellart
• PhD: Valentin Iovene [reviewer], Université Paris-Saclay, Pierre Senellart
• PhD: Wissam Kouadri Maamar [reviewer], Université de Paris, Pierre Senellart

10.3.1 Internal or external Inria responsibilities

• Serge Abiteboul is a member of the strategic committee of the Blaise Pascal foundation for scientific mediation.
• Pierre Senellart is a scientific expert advising the Scientific and Ethical Committee of Parcoursup, the platform for the selection of first-year higher education students.

10.3.2 Articles and contents

• Serge Abiteboul is a founding editor of the binaire blog for popularizing computer science. See https://­www.­lemonde.­fr/­blog/­binaire/.
• Serge Abiteboul has written two science popularization articles: on digital identifiers 11 and on transparency and explainability of algorithmic decisions 12.

International journals

• 11 articleS.Serge Abiteboul. Dans la jungle des identifiants numériques.Acteurs Publics2021
  HALback to text
• 12 articleS.Serge Abiteboul. Qualité, équité, transparence, vérification et explicabilité des décisions algorithmiques.Annales des Mines - Enjeux NumériquesMarch 2021
  HALback to text
• 13 articleA.Ashish Dandekar, D.Debabrota Basu and S.Stéphane Bressan. Differential Privacy at Risk: Bridging Randomness and Privacy Budget.Proceedings on Privacy Enhancing Technologies202112021, 64-84
  HALDOIback to text
• 14 articleL.Louis Filstroff, O.Olivier Gouvert, C.Cédric Févotte and O.Olivier Cappé. A Comparative Study of Gamma Markov Chains for Temporal Non-Negative Factorization.IEEE Transactions on Signal ProcessingFebruary 2021
  HALDOIback to text

International peer-reviewed conferences

• 15 inproceedingsJ.Juliette Achddou, O.Olivier Cappé and A.Aurélien Garivier. Efficient Algorithms for Stochastic Repeated Second-price Auctions.ALT 2021Paris, FranceMarch 2021
  HALback to text
• 16 inproceedingsJ.Juliette Achddou, O.Olivier Cappé and A.Aurélien Garivier. Fast Rate Learning in Stochastic First Price Bidding.ACML 2021 - Proceedings of Machine Learning Research 157, 2021SIngapore, SingaporeNovember 2021
  HALback to text
• 17 inproceedingsM.Maroua Bahri, A.Albert Bifet, S.Silviu Maniu and H. M.Heitor Murilo Gomes. Survey on Feature Transformation Techniques for Data Streams.IJCAI-PRICAI 2020 - 29th International Joint Conference on Artificial Intelligence and the 17th Pacific Rim International Conference on Artificial IntelligenceYokohama / Virtual, JapanJanuary 2021, 4796-4802
  HALDOIback to text
• 18 inproceedingsD.Dorian Baudry, Y.Yoan Russac and O.Olivier Cappé. On Limited-Memory Subsampling Strategies for Bandits.ICML 2021- International Conference on Machine LearningVienna / Virtual, AustriaJuly 2021
  HALback to text
• 19 inproceedingsM.Meghyn Bienvenu, Q.Quentin Manière and M.Michaël Thomazo. Cardinality Queries over DL-Lite Ontologies.IJCAI 2021 - 30th International Joint Conference on Artificial IntelligenceMontreal, CanadaAugust 2021
  HALback to text
• 20 inproceedingsC.Camille Bourgaux, D.David Carral, M.Markus Krötzsch, S.Sebastian Rudolph and M.Michaël Thomazo. Capturing Homomorphism-Closed Decidable Queries with Existential Rules.KR 2021 - 18th International Conference on Principles of Knowledge Representation and ReasoningVirtual, VietnamNovember 2021, 141--150
  HALback to textback to text
• 21 inproceedingsC.Camille Bourgaux, A.Ana Ozaki and J. Z.Jeff Z Pan. Geometric Models for (Temporally) Attributed Description Logics.DL 2021 - 34th International Workshop on Description LogicsDL 2021 - 34th International Workshop on Description LogicsBratislava, SlovakiaSeptember 2021
  HALback to text
• 22 inproceedingsM.Maxime Buron, M.-L.Marie-Laure Mugnier and M.Michaël Thomazo. Parallelisable Existential Rules: a Story of Pieces.KR 2021 - 18th International Conference on Principles of Knowledge Representation and ReasoningVirtual, VietnamNovember 2021
  HALback to text
• 23 inproceedingsS.Shrey Mishra, L.Lucas Pluvinage and P.Pierre Senellart. Towards Extraction of Theorems and Proofs in Scholarly Articles.DocEng '21 - 21st ACM Symposium on Document EngineeringLimerick, IrelandAugust 2021
  HALback to text
• 24 inproceedingsL.Liat Peterfreund. Grammars for Document Spanners.ICDT 2021 - 24th International Conference on Extending Database TechnologyNicosia / Virtual, CyprusMarch 2021
  HALback to text
• 25 inproceedingsY.Yann Ramusat, S.Silviu Maniu and P.Pierre Senellart. Provenance-Based Algorithms for Rich Queries over Graph Databases.EDBT 2021 - 24th International Conference on Extending Database TechnologyNicosia / Virtual, CyprusMarch 2021
  HALback to text
• 26 inproceedingsY.Yoan Russac, L.Louis Faury, O.Olivier Cappé and A.Aurélien Garivier. Self-Concordant Analysis of Generalized Linear Bandits with Forgetting.AISTATS 2021 - International Conference on Artificial Intelligence and StatisticsSan Diego / Virtual, United StatesApril 2021
  HALback to text
• 27 inproceedingsY.Yoan Russac, C.Christina Katsimerou, D.Dennis Bohle, O.Olivier Cappé, A.Aurélien Garivier and W. M.Wouter M Koolen. A/B/n Testing with Control in the Presence of Subpopulations.NeurIPS 2021 - Thirty-fifth Conference on Neural Information Processing SystemsVirtual, FranceDecember 2021
  HALback to text
• 28 inproceedingsV.Victor Vianu. Datalog Unchained.SIGMOD/PODS '21- International Conference on Management of DataXi'an, Shaanxi / Virtual Event China, ChinaACMJune 2021, 57-69
  HALDOIback to text

Reports & preprints

• 29 miscD. D.Dominik D Freydenberger and L.Liat Peterfreund. The theory of concatenation over finite models.January 2021
  HAL
• 30 miscN.Nathan Grosshans, P.Pierre McKenzie and L.Luc Segoufin. Tameness and the power of programs over monoids in DA.January 2022
  HAL
• 31 miscL.Leonid Libkin and L.Liat Peterfreund. Handling SQL Nulls with Two-Valued Logic.January 2021
  HAL
• 32 miscY.Yann Ramusat, S.Silviu Maniu and P.Pierre Senellart. A Practical Dynamic Programming Approach to Datalog Provenance Computation.December 2021
  HAL

Other scientific publications

• 33 thesisR.Riccardo Corona. Gender Discrimination in Data Analysis: a Socio-Technical Approach.Politecnico di Milano. Dipartimento di elettronica, informazione e bioingegneria (Milano, Italie)October 2021
  HALback to text