INRIA a CCSD electronic archive server
Not a member yet
122212 research outputs found
Sort by
Integrating ethical, societal and environmental issues into algorithm design courses
No full textThis document, intended for computer science teachers, describes a case study that puts into practice a questioning of ethical, societal and environmental issues when designing or implementing a decision support system. This study is based on a very popular application, namely road navigation software that informs users of real-time traffic conditions and suggests routes between a starting point and a destination, taking these conditions into account (such as Waze). The approach proposes to intertwine technical considerations (optimal path algorithms, data needed for location, etc.) with a broader view of the ethical, environmental and societal issues raised by the tools studied. Based on the authors' experience conducting sessions with students over several years, this document discusses the context of such a study, suggests teaching resources for implementing it, describes ways to structure discussions, and shares scenarios in different teaching contexts
Des descriptions textuelles au code : une approche de filtrage pour localiser les règles métier
No full textInternational audienceBusiness rules form the backbone of enterprise applications, capturing organizational policies, legal constraints, and the decision logic that governs business processes. In legacy systems, these rules are often hidden in poorly documented code, scattered across multiple modules, and entangled with technical details. When changes are needed, developers must locate and update the relevant code fragments, a process that is time-consuming and error-prone. In this paper, we propose a fully automated approach designed to assist developers in selecting the portions of code that need to be modified following a change in a business rule. The approach reduces the search space of candidate methods likely to implement the affected rule. Starting from a textual description of the rule, our approach combines natural language processing with code analysis to filter methods and retain those relevant for implementing the necessary modifications. We evaluate our solution on a real-world codebase and demonstrate its usefulness in guiding developers during software evolution tasks
Nonlinear compressive reduced basis approximation : when Taylor meets Kolmogorov
No full textThis paper investigates a class of model reduction methods for efficiently approximating the solution of parameter-dependent partial differential equations, where the parameter is a multi-parameter vector µ ∈ R p . In classical settings where the Kolmogorov N -width decays sufficiently fast, it is effective to approximate the solution as a sum of N separable terms, each being the product of a parameter-dependent coefficient and a space-(or space-time-) dependent function. This leads to reduced-order models with N degrees of freedom and computational complexity of order O(N 3 ). However, when the Kolmogorov N -width decays slowly, N must be large to achieve acceptable accuracy, and such cubic complexity becomes prohibitive. The linear complexity measure in terms of Kolmogorov N -width has to be replaced by a more involved width: the Gelfand width for instance with its associated notion of sensing number. Recent nonlinear reduction approaches based on this notion have proposed to decompose the N coordinates into two groups: n free variables and n dependent variables, where the latter are expressed as nonlinear functions of the former and N = n + n. Several works have focused on the case where these n functions are homogeneous quadratic forms of the n main variables, with optimization strategies for choosing n given a target accuracy. The main contribution of this paper is a rigorous analysis of the local sensing number, showing that the optimal choice n = p is appropriate when the parameter variations remain locally concentrated around a reference point. In practical scenarios involving wide parameter ranges, the condition p ≤ n ≤ p + k (with k small) is valid and more robust from continuity arguments. Additionally, the assumption of a quadratic mapping, also justified in a local sense, becomes insufficient. More expressive nonlinear mappingsincluding those learned from data using machine learning -become necessary. This work contributes a theoretical foundation for such nonlinear reduction strategies and highlights the need for further investigations into their reliability, interpretability, and safeguards, particularly in order to apply this type of approach and push back the Kolmogorov Barrier
LAD2025, A constraint-based solver for the subgraph isomorphism problem
No full textInternational audienceThe Subgraph Isomorphism Problem (SIP) is an N P-complete problem that aims at finding a copy of a pattern graph in a target graph. It may be modelled as a constraint satisfaction problem in a very straightforward way, and exact approaches for solving SIPs usually propagate constraints to reduce the search space. In particular, PathLAD is a solver introduced in 2016 that combines Locally All Different (LAD) constraints with path-based supplemental constraints. In this paper, we introduce LAD2025, which combines a complete refactoring of PathLAD with new features: new supplemental constraints, a weight-based variable ordering heuristic, random restarts with nogood recording, a new value ordering heuristic and a rule for selecting the level of filtering
Lifting a CSS code via its handlebody realization
No full textWe present a topological approach to lifting a quantum CSS code. In previous work, we proposed lifting a CSS code by constructing covering spaces over its 2D simplicial complex representation, known as the Tanner cone-complex. This idea was inspired by the work of Freedman and Hastings, which associates CSS codes with handlebodies. In this paper, we show how the handlebody realization of a code can also be used to perform code lifting, and we provide a more detailed discussion of why this is essentially equivalent to the Tanner cone-complex approach. As an application, we classify lifts of hypergraph-product codes via their handlebody realization
Exploring Bell nonlocality with extremal non-signaling boxes
No full textExtremal non-signaling (ENS) boxes are correlations that correspond to vertices of the non-signaling polytope of a Bell scenario. Neither quantum theory nor any theory for ideal measurements allows for ENS boxes. That is, according to quantum theory, ENS boxes are nonphysical. Still, ENS boxes are crucial for addressing a number of problems in Bell nonlocality. Here, we obtain ENS boxes in arbitrary bipartite Bell scenarios and present the complete list of ENS boxes for several unexplored scenarios. Equipped with the boxes, we revisit several foundational questions. We find that already two copies of any ENS box violate the exclusivity (or local orthogonality) and Specker's principles. We provide the minimal decomposition of the magic square correlation-the simplest known perfect correlation in nature-in terms of ENS boxes. We identify the minimal scenario in which a dit of communication (with d ⩽ 5) is insufficient to simulate ENS boxes. Our results show that the ENS boxes approach leads to new results and opens new avenues for research
Self-Defense: Optimal QIF Solutions and Application to Website Fingerprinting
No full textInternational audienceQuantitative Information Flow (QIF) provides a robust information-theoretical framework for designing secure systems with minimal information leakage. While previous research has addressed the design of such systems under hard constraints (e.g. application limitations) and soft constraints (e.g. utility), scenarios often arise where the core system's behavior is considered fixed. In such cases, the challenge is to design a new component for the existing system that minimizes leakage without altering the original system. In this work we address this problem by proposing optimal solutions for constructing a new row, in a known and unmodifiable information-theoretic channel, aiming at minimizing the leakage. We first model two types of adversaries: an exact-guessing adversary, aiming to guess the secret in one try, and a s-distinguishing one, which tries to distinguish the secret s from all the other secrets.Then, we discuss design strategies for both fixed and unknown priors by offering, for each adversary, an optimal solution under linear constraints, using Linear Programming.We apply our approach to the problem of website fingerprinting defense, considering a scenario where a site administrator can modify their own site but not others. We experimentally evaluate our proposed solutions against other natural approaches. First, we sample real-world news websites and then, for both adversaries, we demonstrate that the proposed solutions are effective in achieving the least leakage. Finally, we simulate an actual attack by training an ML classifier for the s-distinguishing adversary and show that our approach decreases the accuracy of the attacker
Event Detection in Time Series
No full textInternational audienceThis book is dedicated to exploring and explaining time series event detection in databases. The focus is on events, which are pervasive in time series applications where significant changes in behavior are observed at specific points or time intervals. Event detection is a basic function in surveillance and monitoring systems and has been extensively explored over the years, but this book provides a unified overview of the major types of time series events with which researchers should be familiar: anomalies, change points, and motifs. The book starts with basic concepts of time series and presents a general taxonomy for event detection. This taxonomy includes (i) granularity of events (punctual, contextual, and collective), (ii) general strategies (regression, classification, clustering, model-based), (iii) methods (theory-driven, data-driven), (iv) machine learning processing (supervised, semi-supervised, unsupervised), and (v) data management (ETL process). This taxonomy is weaved throughout chapters dedicated to the specific event types: anomaly detection, change-point, and motif discovery. The book discusses state-of-the-art metric evaluations for event detection methods and also provides a dedicated chapter on online event detection, including the challenges and general approaches (static versus dynamic), including incremental and adaptive learning. This book will be of interested to graduate or undergraduate students of different fields with a basic introduction to data science or data analytics
Cluster globally, Reduce locally: Scalable efficient dictionary compression for magnetic resonance fingerprinting
No full textInternational audienceWith the rapid advancements in medical data acquisition and production, increasingly richer representations exist to characterize medical information. However, such large-scale data do not usually meet computing resource constraints or algorithmic complexity, and can only be processed after compression or reduction, at the potential loss of information. In this work, we consider specific Gaussian mixture models (HD-GMM), tailored to deal with high dimensional data and to limit information loss by providing component-specific lower dimensional representations. We also design anincremental algorithm to compute such representations for large data sets, overcoming hardware limitations of standard methods. Our procedure is illustrated in a magnetic resonance fingerprinting study, where it achieves a dictionary compression for faster and more accurate map reconstructions
Rationality of the invariant field for a class of representations of the real orthogonal groups
No full textInternational audienceWe give a criterion for the invariant field of a representation of SOn(R) to be rational. We define a length λ (n) on representations of SOn(R), depending on their weights. This length is at most n 2 . If a representation of SOn(R) or On(R) on V contains the standard representation R n with multiplicity greater than this length, its invariant field is rational. To prove it we construct a sequence of Seshadri slices, each reducing the problem to a repesentation of a subgroup of codimension one preserving the inequality between the multiplicity of the standard representation and the length. The case of length λ (n) (V) = 0 corresponds to the natural action of SOn(R) on matrices M n,k (R), for which we construct a minimal basis