Portail HAL des publications du LIRMM
Not a member yet
13279 research outputs found
Sort by
Linguistic Signatures for Enhanced Emotion Detection
No full textInternational audienceEmotion detection is a central problem in NLP, with recent progress driven by transformer-based models trained on established datasets. However, little is known about the linguistic regularities that characterize how emotions are expressed across different corpora and labels. This study examines whether linguistic features can serve as reliable interpretable signals for emotion recognition in text. We extract emotion-specific linguistic signatures from 13 English datasets and evaluate how incorporating these features into transformer models impacts performance. Our RoBERTa-based models enriched with high level linguistic features achieve consistent performance gains of up to +2.4 macro F1 on the GoEmotions benchmark, showing that explicit lexical cues can complement neural representations and improve robustness in predicting emotion categories.</div
Handling Noisy Plaintext Checking Oracles with SPiRiT: Application to Kyber
No full textInternational audiencePost-Quantum key encapsulation mechanisms based on the re-encryption framework of Fujisaki and Okamoto have proved very sensitive to Plaintext Checking Oracle (PCO) attacks. The first theoretic works on PCO attacks were rapidly followed by practical attacks on real implementations, notably on NIST standardized ML-KEM. The actual realization of a PCO relies on side-channel leakages that are inherently noisy ; even more so if the implementation embeds side-channel countermeasures.In this paper we tackle the often overlooked complications caused by highly noisy PCOs. We demonstrate that the impact of wrong oracle answers can be very efficiently reduced with the use of the so-called Sequential Probability Ratio Test (SPRT). This test can be seen as an elegant and natural early abort strategy on top of the commonly used approaches based on majority-voting or the likelyhood ratio test. As far as we know, this is the first use of SPRT in the context of side-channel attacks. We show that it allows to divide by a factor up to 3 the attack complexity compared to the traditional approaches. By establishing new comparisons with recently published noisy PCO attacks we emphasize that SPRT should be considered as the novel baseline for all future works in this line of research
Positionnement d'un robot parallèle à câbles avec une précision supérieure à 250 μm à l'aide de systèmes de mesure par multilatération et photogrammétrie
No full textInternational audienceImproving the positioning accuracy of cable-driven parallel robots (CDPRs) is crucial for industrial applications. These robots, operating in large volumes and handling heavy loads, have an accuracy limited by several factors, such as variations in ambient temperature or changes of the load being transported, which affect the mechanical structure of the robot or the tensions in the cables. For instance, CoGiRo is a CDPR of dimensions of 11 m × 15 m × 6 m able to move a platform weighing up to 500 kg. Its resolution is a few tens of micrometres, but its positioning, estimated from the winch encoders, lacks accuracy. To accurately place the CoGiRo mobile platform in the desired position and orientation, this paper proposes to use multilateration and photogrammetric measurement systems in a collaborative way. Photogrammetry continuously measured the poses of the mobile platform with worst-case coordinate uncertainties in the depth direction moving away from the cameras, with 0.2 mm being typical for all lines of sight, dropping to 0.5 mm where lines of sight were blocked by occlusion. The photogrammetric system reported poses at 2 Hz to the multilateration system, enabling it to align its stations on the distant targets and measure static poses of the platform with an estimated uncertainty typically less than 70 µm for the position coordinates and less than 110 µrad for the orientation angles. Multilateration measurements were then used by CoGiRo to reduce its positioning errors to less than 250 µm. The technique was validated using a practical assembly of two square-shaped metallic parts equipped with 10 independent capacitive distance sensors that allowed us to demonstrate part alignment to better than 250 µm
Parameterized complexity of isometric path partition: treewidth and diameter
No full textIn the Isometric Path Partition problem, the input is a graph G with n vertices and an integer k, and the objective is to determine whether the vertices of G can be partitioned into k vertex-disjoint shortest paths. We investigate the parameterized complexity of the problem when parameterized by the treewidth (tw) of the input graph, arguably one of the most widely studied parameters. Courcelle's theorem [Information & Computation, 1990] shows that graph problems that are expressible as MSO formulas of constant size admit FPT algorithms parameterized by the treewidth of the input graph. This encompasses many natural graph problems. However, many metric-based graph problems, where the solution is defined using some metric-based property of the graph (often the distance) are not expressible as MSO formulas of constant size. These types of problems, Isometric Path Partition being one of them, require individual attention and often draw the boundary for the success story of parameterization by treewidth.We prove that Isometric Path Partition is W[1]-hard when parameterized by treewidth (in fact, even pathwidth (pw)), answering the question by Dumas et al. SIDMA, 2024], Fernau et al. [TCS, 2025], and confirming the aforementioned tendency. We complement this hardness result by designing a tailored dynamic programming algorithm running in n^{O(tw)} time. This dynamic programming approach also results in an algorithm running in time diam^{O(tw^2)} * n^{O(1)}}, where diam is the diameter of the graph. It is known that Isometric Path Partition remains NP-hard on graphs of diameter 2; hence, the combination of both parameters is necessary to obtain a tractable algorithm. Note that the dependency on treewidth is unusually high, as most problems that are FPT for treewidth admit algorithms running in time 2^{O(tw)}* n^{O(1)} or 2^{O(tw log (tw))}* n^{O(1)}. However, we rule out the possibility of a significantly faster algorithm, proving that Isometric Path Partition does not admit an algorithm running in time diam^{o(pw^2/(log^3(pw)))} * n^O(1), assuming the Randomized-ETH
Computing Weak Counterfactual Explanations for Linear Optimization: A New Class of Bilevel Models and a Tailored Penalty Alternating Direction Method
No full textInternational audienc
Dynamic programming on bipartite tree decompositions
No full textInternational audienceWe revisit a graph width parameter that we dub bipartite treewidth (btw). Bipartite treewidth can be seen as a common generalization of treewidth and the odd cycle transversal number, and is closely related to odd-minors. Intuitively, a bipartite tree decomposition is a tree decomposition whose bags induce almost bipartite graphs and whose adhesions contain at most one “bipartite” vertex, while the width of such decomposition measures the number of “non-bipartite” vertices in a bag. We provide para-NP-completeness results and develop dynamic programming techniques to solve problems on graphs of small btw. In particular, we show that -Subgraph-Cover, Weighted Independent Set, Odd Cycle Transversal, and Maximum Weighted Cut are parameterized by btw. We also provide the following dichotomy when H is a 2-connected graph: if H is bipartite, then H-{Subgraph/Induced-Subgraph/Odd-Minor/Scattered}-Packing is para-NP-complete parameterized by btw while, if H is non-bipartite, then the problem is solvable in XP-time
Algebraic Barriers to Halving Algorithmic Information Quantities in Correlated Strings
No full textA preliminary version of the paper was published in proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025), https://mfcs2025.mimuw.edu.pl/ ; DOI:10.4230/LIPIcs.MFCS.2025.84, https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.84International audienceWe study the possibility of scaling down algorithmic information quantities in tuples of correlated strings. In particular, we address a question raised by Alexander Shen: whether, for any triple of strings (a, b, c), there exists a string z such that each of the values of conditional Kolmogorov complexity C(a|z), C(b|z), C(c|z) is approximately half of the corresponding unconditional Kolmogorov complexity. We provide a negative answer to this question by constructing a triple (a, b, c) for which no such string z exists. Our construction is based on combinatorial properties of incidences in finite projective planes and relies on recent bounds on point-line incidences over prime fields. As an application, we show that this impossibility implies lower bounds on the communication complexity of secret key agreement protocols in certain settings. These results reveal algebraic obstructions to efficient information exchange and highlight a separation in the information-theoretic behavior of projective planes over fields with and without proper subfields
Vertex identification to a forest
No full textInternational audienceLet H be a graph class and k ∈ N. We say a graph G admits a k-identification to H if there is a partition P of some set X ⊆ V (G) of size at most k such that after identifying each part in P to a single vertex, the resulting graph belongs to H. The graph parameter id H is defined so that id H (G) is the minimum k such that G admits a k-identification to H, and the problem of Identification to H asks, given a graph G and k ∈ N, whether id H (G) ≤ k. If we set H to be the class F of acyclic graphs, we generate the problem Identification to Forest, which we show to be NP-complete. We prove that, when parameterized by the size k of the identification set, it admits a kernel of size 2k + 1. For our kernel we reveal a close relation of Identification to Forest with the Vertex Cover problem. We also study the combinatorics of the yes-instances of Identification to H, i.e., the class H (k) := {G | id H (G) ≤ k}, which we show to be minor-closed for every k when H is minor-closed. We prove that the minor-obstructions of F (k) are of size at most 2k + 4. We also prove that every graph G such that id F (G) is sufficiently big contains as a minor either a cycle on k vertices, or k disjoint triangles, or the k-marguerite graph, that is the graph obtained by k disjoint triangles by identifying one vertex of each of them into the same vertex
Kruskal-EDS: Edge Dynamic Stratification: A Distribution-Adaptive Minimum Spanning Tree Algorithm Inspired by Ergodic Theory
No full textKruskal-EDS: Edge Dynamic StratificationInternational audienceWe introduce Kruskal-EDS (Edge Dynamic Stratification), a distribution-adaptive variant ofKruskal’s minimum spanning tree (MST) algorithm that replaces the mandatory Θ(m log m)global sort with a three-phase√procedure inspired by Birkhoff’s ergodic theorem. In Phase 1, a sample of m edges estimates the weight distribution in O (m log m) time. In Phase 2, all m edges are assigned to k strata in O(m log k) time via binary search on quantile boundaries — no global sort. In Phase 3, strata are sorted and processed in order; execution halts as soon as n−1 MST edges are accepted. We prove an effective complexity of O(m + p · (m/k) log(m/k)), where p ≤ k is the number of strata actually processed. On sparse graphs or heavy-tailed weight distributions, p ≪ k and the algorithm achieves near-O(m) behaviour. We further derive the optimalp strata count k∗ = ⌈ m/ ln(m + 1) ⌉, balancing partition overhead against intra-stratum sortcost. An extensive benchmark on 14 graph families demonstrates correctness on 12 test casesand practical speedups reaching 10× in wall-clock time and 33× in sort operations overstandard Kruskal. A 3-dimensional TikZ visualisation of the complexity landscape illus-trates the algorithm’s adaptive behaviour as a function of graph density and weight distri-bution skewness
Assisting the early development stages of privacy-aware software: the PRIAM tooled metamodel for GDPR
No full textPart of a special issue on Regulatory compliance in software engineeringInternational audienceContext:As software systems are more tailored to users, personal data is collected and exploited more than ever before. This situation raises the issue of user privacy protection. Conforming to personal data protection regulations, such as the European General Data Protection Regulation (GDPR), has thus become a legal obligation for application providers. However, there are no widely adopted proposals to formalize, implement, and assess compliance with the personal data privacy protection required by GDPR.Objective:In order to help application developers in the early stages of the development process, our overarching objective is to propose a tooled software engineering approach to integrate personal data protection capabilities, thus contributing to the development-by-design of privacy-aware software aligned with GDPR requirements.Method:We developed a method called PRIAM (PRIvacy Assessment Method) that goes beyond a conceptual description of the regulation by incorporating concrete, actionable software artifacts. This article presents the cornerstone of this method – PRIAM metamodel – along with its companion artifacts.Results:PRIAM metamodel captures the main concepts of GDPR and is then supported by a domain-specific language, user stories, and a dedicated database schema. The comprehensiveness and relevance of PRIAM metamodel have been qualitatively evaluated by GDPR experts through a questionnaire. Complementarily, an AI-based evaluation has been conducted, using some Large Language Models (LLMs), opening perspectives for fast, iterative evaluations of metamodels that formalize regulation texts. Besides, the practicality and usefulness of PRIAM metamodel and all its companion artifacts are highlighted through the running example of a Sport center management application, where privacy enforcement features, tailored to the specific personal data of the application, are generated and integrated.Conclusion:These two elements assert the viability of our proposal as a practical solution for assisting the development of privacy-aware applications that are compliant with GDPR requirements, thanks to customizable sets of actual development artifacts, systematically derived from a validated comprehensive formalization of the regulation articles