Showing 1–40 of 40 results for author: Laurent, M

Fairis: Fairness-Aware Aggregation with Provable Influence Containment against Fairness Poisoning Attacks in Collaborative Machine Learning

Authors: Devharsh Trivedi, Nesrine Kaaniche, Nikos Triandopoulos, Maryline Laurent, Jackson Walters

Abstract: Collaborative machine learning among financial institutions must be both group-fair and robust against deliberate adversarial manipulation. Existing fairness-aware aggregation methods remain formally vulnerable to fairness poisoning: a malicious client maximizing group disparity while preserving accuracy evades accuracy-based Byzantine defenses, and in our threat model FairFed's gap-based weightin… ▽ More Collaborative machine learning among financial institutions must be both group-fair and robust against deliberate adversarial manipulation. Existing fairness-aware aggregation methods remain formally vulnerable to fairness poisoning: a malicious client maximizing group disparity while preserving accuracy evades accuracy-based Byzantine defenses, and in our threat model FairFed's gap-based weighting can be gamed by an adversary who observes the global fairness score. We present Fairis, a server-side reweighting scheme in which each client's update receives the normalized weight $ω_k = \bar{w}_k / \sum_j \bar{w}_j$ built from the unnormalized score $\bar{w}_k = η- \mathcal{F}_k$, with $\mathcal{F}_k \in [0,1]$ the local Equal Opportunity Difference and $η> 1$ a security parameter. We prove three properties, Monotone Weight Reduction (MWR), Demographic Participation, and Non-Gamesmanship, extend MWR to colluding minority coalitions, and show that combining MWR with server-side norm clipping bounds the adversary's displacement of the global model by $ω_0 C$, strictly decreasing in its own reported disparity. Assuming honest score reporting, an assumption this paper does not discharge, Fairis is the only rule evaluated that guarantees every client strictly positive weight while provably reducing an adversary's weight monotonically in its bias; clipped FairFed can reach a lower weight but guarantees nothing and zeroes a client outright on Taiwan Credit. Against an adversary stealthy enough to evade accuracy-based defenses, within 0.04 accuracy of benign, Fairis cuts its weight by 41 to 54% below a size-blind control on Taiwan. On routine non-IID partitions no rule dominates, and a uniform-weighting ablation shows that containment tracks how far the adversary's score separates from the honest mean, providing none when the honest population is already unfair. △ Less

Submitted 6 August, 2026; originally announced August 2026.

Comments: 37 pages, 6 figures. Extended version, adding a size-weighted variant, a clipping-based influence bound, and machine-checked proofs of the main results

ACM Class: I.2.11; I.2.6; K.4.2

Deanonymizable Scoped Linkable Ring Signatures

Authors: Montassar Naghmouchi, Maryline Laurent

Abstract: Ring signatures offer highly desirable privacy features like anonymity and ad-hoc group formation with high autonomy, but partially lack linkability and accountability features required for strict use-cases like consent management in healthcare. Existing signature schemes fail to natively integrate scoped linkability with decentralized accountability defined here on-demand unconditional deanonymiz… ▽ More Ring signatures offer highly desirable privacy features like anonymity and ad-hoc group formation with high autonomy, but partially lack linkability and accountability features required for strict use-cases like consent management in healthcare. Existing signature schemes fail to natively integrate scoped linkability with decentralized accountability defined here on-demand unconditional deanonymization of signers without reliance on a trusted party (opener) or a separate cryptographic commitment. We introduce Deanonymizable Scoped Linkable Ring Signatures (DSLRS) to address this gap. DSLRS builds on previous linkable and accountable signature schemes and their cryptographic primitives to construct a new signature scheme that natively implement both privacy and trust features. Scoped linkability in DSLRS is achieved using "scopes" (context identifiers) and dynamic key images, effectively providing ring-independent scoped linkability and unlinkability across different scopes. DSLRS relies on k-of-N decentralized deanonymization network nodes to extract the signer's public key (identity) from ElGamal components built in the signature, achieving ring-independent decentralized accountability. The full DSLRS algorithms, formal property definitions and proofs, signature evaluation and experimental results from an implementation, and a blockchain-based instantiation and application of our scheme in consent management for clinical trials are provided. DSLRS is proved under the ECDLP and DDH hardness assumptions in the Random Oracle Model (ROM). △ Less

Submitted 2 July, 2026; v1 submitted 12 May, 2026; originally announced May 2026.

Comments: v2.0

LABBench2: An Improved Benchmark for AI Systems Performing Biology Research

Authors: Jon M Laurent, Albert Bou, Michael Pieler, Conor Igoe, Alex Andonian, Siddharth Narayanan, James Braza, Alexandros Sanchez Vassopoulos, Jacob L Steenwyk, Blake Lash, Andrew D White, Samuel G Rodriques

Abstract: Optimism for accelerating scientific discovery with AI continues to grow. Current applications of AI in scientific research range from training dedicated foundation models on scientific data to agentic autonomous hypothesis generation systems to AI-driven autonomous labs. The need to measure progress of AI systems in scientific domains correspondingly must not only accelerate, but increasingly shi… ▽ More Optimism for accelerating scientific discovery with AI continues to grow. Current applications of AI in scientific research range from training dedicated foundation models on scientific data to agentic autonomous hypothesis generation systems to AI-driven autonomous labs. The need to measure progress of AI systems in scientific domains correspondingly must not only accelerate, but increasingly shift focus to more real-world capabilities. Beyond rote knowledge and even just reasoning to actually measuring the ability to perform meaningful work. Prior work introduced the Language Agent Biology Benchmark LAB-Bench as an initial attempt at measuring these abilities. Here we introduce an evolution of that benchmark, LABBench2, for measuring real-world capabilities of AI systems performing useful scientific tasks. LABBench2 comprises nearly 1,900 tasks and is, for the most part, a continuation of LAB-Bench, measuring similar capabilities but in more realistic contexts. We evaluate performance of current frontier models, and show that while abilities measured by LAB-Bench and LABBench2 have improved substantially, LABBench2 provides a meaningful jump in difficulty (model-specific accuracy differences range from -26% to -46% across subtasks) and underscores continued room for performance improvement. LABBench2 continues the legacy of LAB-Bench as a de facto benchmark for AI scientific research capabilities and we hope that it continues to help advance development of AI tools for these core research functions. To facilitate community use and development, we provide the task dataset at https://huggingface.co/datasets/futurehouse/labbench2 and a public eval harness at https://github.com/EdisonScientific/labbench2. △ Less

Submitted 5 May, 2026; v1 submitted 4 February, 2026; originally announced April 2026.

Uncovering Memorization in Timeseries Imputation models: LBRM Membership Inference and its link to attribute Leakage

Authors: Faiz Taleb, Ivan Gazeau, Maryline Laurent

Abstract: Deep learning models for time series imputation are now essential in fields such as healthcare, the Internet of Things (IoT), and finance. However, their deployment raises critical privacy concerns. Beyond the well-known issue of unintended memorization, which has been extensively studied in generative models, we demonstrate that time series models are vulnerable to inference attacks in a black-bo… ▽ More Deep learning models for time series imputation are now essential in fields such as healthcare, the Internet of Things (IoT), and finance. However, their deployment raises critical privacy concerns. Beyond the well-known issue of unintended memorization, which has been extensively studied in generative models, we demonstrate that time series models are vulnerable to inference attacks in a black-box setting. In this work, we introduce a two-stage attack framework comprising: (1) a novel membership inference attack based on a reference model that improves detection accuracy, even for models robust to overfitting-based attacks, and (2) the first attribute inference attack that predicts sensitive characteristics of the training data for timeseries imputation model. We evaluate these attacks on attention-based and autoencoder architectures in two scenarios: models that are trained from scratch, and fine-tuned models where the adversary has access to the initial weights. Our experimental results demonstrate that the proposed membership attack retrieves a significant portion of the training data with a tpr@top25% score significantly higher than a naive attack baseline. We show that our membership attack also provides a good insight of whether attribute inference will work (with a precision of 90% instead of 78% in the genral case). △ Less

Submitted 25 March, 2026; originally announced March 2026.

Enabling Multi-Client Authorization in Dynamic SSE

Authors: Seydina Ousmane Diallo, Maryline Laurent, Nesrine Kaaniche

Abstract: Outsourcing encrypted data to the cloud creates a fundamental tension between data privacy and functional searchability. Current Searchable Symmetric Encryption (SSE) solutions frequently have significant limitations, such as excessive metadata leakage, or a lack of fine-grained access control. These issues restrict the scalability of secure searches in real-world applications where multiple clien… ▽ More Outsourcing encrypted data to the cloud creates a fundamental tension between data privacy and functional searchability. Current Searchable Symmetric Encryption (SSE) solutions frequently have significant limitations, such as excessive metadata leakage, or a lack of fine-grained access control. These issues restrict the scalability of secure searches in real-world applications where multiple clients require different levels of authorization. Our paper proposes MASSE, a dynamic multi-client SSE scheme incorporating attribute-based access control, which expands the OXT framework. With MASSE, clients are restricted sto searching for keywords authorized by their specific attribute sets, and the server remains unaware of the keywords and attributes. MASSE supports practical dynamic updates to documents, and client authorizations, including revocation, without requiring reencryption of the database or indices, or a large number of interactions. We formally prove the security of MASSE, that is, forward and backward privacy under a well-defined leakage profile, and token unforgeability. An experimental evaluation in a database containing 100 keywords, each associated with 150 documents, demonstrates the practical efficiency of MASSE. It takes less than two seconds to generate 10 to 100 keyword queries and 14 seconds to retrieve 50 matching documents. Theoretical results show that MASSE outperforms competing solutions, including OXT, and can be scaled to large encrypted databases. MASSE is also suitable for dynamic cloud deployments. Keywords: Searchable Encryption, SSE, Multi-Client, Attribute Based SSE, Access Control, Revocation, OXT △ Less

Submitted 10 March, 2026; originally announced March 2026.

Comments: 16 pages, 4 figures

ACM Class: E.3; H.2.0

ClinConNet: A Blockchain-based Dynamic Consent Management Platform for Clinical Research

Authors: Montassar Naghmouchi, Maryline Laurent

Abstract: Consent is an ethical cornerstone of clinical research and healthcare in general. Although the ethical principles of consent - providing information, ensuring comprehension, and ensuring voluntariness - are well-defined, the technological infrastructure remains outdated. Clinicians are responsible for obtaining informed consent from research subjects or patients, and for managing it before, during… ▽ More Consent is an ethical cornerstone of clinical research and healthcare in general. Although the ethical principles of consent - providing information, ensuring comprehension, and ensuring voluntariness - are well-defined, the technological infrastructure remains outdated. Clinicians are responsible for obtaining informed consent from research subjects or patients, and for managing it before, during, and after clinical trials or care, which is a burden for them. The voluntary nature of participating in clinical research or undergoing medical treatment implies the need for a participant-centric consent management system. However, this is not reflected in most established systems. Not only do most healthcare information systems not follow a user-centric model, but they also create data silos, which significantly reduce the mobility of patient data between different healthcare institutions and impact personalized medicine. Furthermore, consent management tools are outdated. We propose ClinConNet (Clinical Consent Network), a platform that connects researchers and participants based on clinical research projects. ClinConNet is powered by a dynamic consent model based on blockchain and take advantage of dynamic consent interfaces, as well as blockchain and Self-Sovereign Identity systems. ClinConNet is user-centric and provides important privacy features for patients, such as unlinkability, confidentiality, and ownership of identity data. It is also compatible with the right to be forgotten, as defined in many personal data protection regulations, such as the GDPR. We provide a detailed privacy and security analysis in an adversarial model, as well as a Proof of Concept implementation with detailed performance measures that demonstrate the feasibility of our blockchain-based consent management system with a median end-to-end consent establishment time of under 200ms and a throughput of 250TPS. △ Less

Submitted 2 February, 2026; originally announced February 2026.

Comments: 19 pages, 8 figures, 6 tables, 5 code repositories on Github included

Kosmos: An AI Scientist for Autonomous Discovery

Authors: Ludovico Mitchener, Angela Yiu, Benjamin Chang, Mathieu Bourdenx, Tyler Nadolski, Arvis Sulovari, Eric C. Landsness, Daniel L. Barabasi, Siddharth Narayanan, Nicky Evans, Shriya Reddy, Martha Foiani, Aizad Kamal, Leah P. Shriver, Fang Cao, Asmamaw T. Wassie, Jon M. Laurent, Edwin Melville-Green, Mayk Caldas, Albert Bou, Kaleigh F. Roberts, Sladjana Zagorac, Timothy C. Orr, Miranda E. Orr, Kevin J. Zwezdaryk , et al. (12 additional authors not shown)

Abstract: Data-driven scientific discovery requires iterative cycles of literature search, hypothesis generation, and data analysis. Substantial progress has been made towards AI agents that can automate scientific research, but all such agents remain limited in the number of actions they can take before losing coherence, thus limiting the depth of their findings. Here we present Kosmos, an AI scientist tha… ▽ More Data-driven scientific discovery requires iterative cycles of literature search, hypothesis generation, and data analysis. Substantial progress has been made towards AI agents that can automate scientific research, but all such agents remain limited in the number of actions they can take before losing coherence, thus limiting the depth of their findings. Here we present Kosmos, an AI scientist that automates data-driven discovery. Given an open-ended objective and a dataset, Kosmos runs for up to 12 hours performing cycles of parallel data analysis, literature search, and hypothesis generation before synthesizing discoveries into scientific reports. Unlike prior systems, Kosmos uses a structured world model to share information between a data analysis agent and a literature search agent. The world model enables Kosmos to coherently pursue the specified objective over 200 agent rollouts, collectively executing an average of 42,000 lines of code and reading 1,500 papers per run. Kosmos cites all statements in its reports with code or primary literature, ensuring its reasoning is traceable. Independent scientists found 79.4% of statements in Kosmos reports to be accurate, and collaborators reported that a single 20-cycle Kosmos run performed the equivalent of 6 months of their own research time on average. Furthermore, collaborators reported that the number of valuable scientific findings generated scales linearly with Kosmos cycles (tested up to 20 cycles). We highlight seven discoveries made by Kosmos that span metabolomics, materials science, neuroscience, and statistical genetics. Three discoveries independently reproduce findings from preprinted or unpublished manuscripts that were not accessed by Kosmos at runtime, while four make novel contributions to the scientific literature. △ Less

Submitted 5 November, 2025; v1 submitted 4 November, 2025; originally announced November 2025.

Comments: Revision: figure layout changes and minor text edits

Benchmarking and Evaluation of AI Models in Biology: Outcomes and Recommendations from the CZI Virtual Cells Workshop

Authors: Elizabeth Fahsbender, Alma Andersson, Jeremy Ash, Polina Binder, Daniel Burkhardt, Benjamin Chang, Georg K. Gerber, Anthony Gitter, Patrick Godau, Ankit Gupta, Genevieve Haliburton, Siyu He, Trey Ideker, Ivana Jelic, Aly Khan, Yang-Joon Kim, Aditi Krishnapriyan, Jon M. Laurent, Tianyu Liu, Emma Lundberg, Shalin B. Mehta, Rob Moccia, Angela Oliveira Pisco, Katherine S. Pollard, Suresh Ramani , et al. (10 additional authors not shown)

Abstract: Artificial intelligence holds immense promise for transforming biology, yet a lack of standardized, cross domain, benchmarks undermines our ability to build robust, trustworthy models. Here, we present insights from a recent workshop that convened machine learning and computational biology experts across imaging, transcriptomics, proteomics, and genomics to tackle this gap. We identify major techn… ▽ More Artificial intelligence holds immense promise for transforming biology, yet a lack of standardized, cross domain, benchmarks undermines our ability to build robust, trustworthy models. Here, we present insights from a recent workshop that convened machine learning and computational biology experts across imaging, transcriptomics, proteomics, and genomics to tackle this gap. We identify major technical and systemic bottlenecks such as data heterogeneity and noise, reproducibility challenges, biases, and the fragmented ecosystem of publicly available resources and propose a set of recommendations for building benchmarking frameworks that can efficiently compare ML models of biological systems across tasks and data modalities. By promoting high quality data curation, standardized tooling, comprehensive evaluation metrics, and open, collaborative platforms, we aim to accelerate the development of robust benchmarks for AI driven Virtual Cells. These benchmarks are crucial for ensuring rigor, reproducibility, and biological relevance, and will ultimately advance the field toward integrated models that drive new discoveries, therapeutic insights, and a deeper understanding of cellular systems. △ Less

Submitted 15 July, 2025; v1 submitted 14 July, 2025; originally announced July 2025.

Robin: A multi-agent system for automating scientific discovery

Authors: Ali Essam Ghareeb, Benjamin Chang, Ludovico Mitchener, Angela Yiu, Caralyn J. Szostkiewicz, Jon M. Laurent, Muhammed T. Razzak, Andrew D. White, Michaela M. Hinks, Samuel G. Rodriques

Abstract: Scientific discovery is driven by the iterative process of background research, hypothesis generation, experimentation, and data analysis. Despite recent advancements in applying artificial intelligence to scientific discovery, no system has yet automated all of these stages in a single workflow. Here, we introduce Robin, the first multi-agent system capable of fully automating the key intellectua… ▽ More Scientific discovery is driven by the iterative process of background research, hypothesis generation, experimentation, and data analysis. Despite recent advancements in applying artificial intelligence to scientific discovery, no system has yet automated all of these stages in a single workflow. Here, we introduce Robin, the first multi-agent system capable of fully automating the key intellectual steps of the scientific process. By integrating literature search agents with data analysis agents, Robin can generate hypotheses, propose experiments, interpret experimental results, and generate updated hypotheses, achieving a semi-autonomous approach to scientific discovery. By applying this system, we were able to identify a novel treatment for dry age-related macular degeneration (dAMD), the major cause of blindness in the developed world. Robin proposed enhancing retinal pigment epithelium phagocytosis as a therapeutic strategy, and identified and validated a promising therapeutic candidate, ripasudil. Ripasudil is a clinically-used rho kinase (ROCK) inhibitor that has never previously been proposed for treating dAMD. To elucidate the mechanism of ripasudil-induced upregulation of phagocytosis, Robin then proposed and analyzed a follow-up RNA-seq experiment, which revealed upregulation of ABCA1, a critical lipid efflux pump and possible novel target. All hypotheses, experimental plans, data analyses, and data figures in the main text of this report were produced by Robin. As the first AI system to autonomously discover and validate a novel therapeutic candidate within an iterative lab-in-the-loop framework, Robin establishes a new paradigm for AI-driven scientific discovery. △ Less

Submitted 19 May, 2025; originally announced May 2025.

Towards Efficient Verification of Parallel Applications with Mc SimGrid

Authors: Matthieu Laurent, Thierry Jéron, Martin Quinson

Abstract: Assessing the correctness of distributed and parallel applications is notoriously difficult due to the complexity of the concurrent behaviors and the difficulty to reproduce bugs. In this context, Dynamic Partial Order Reduction (DPOR) techniques have proved successful in exploiting concurrency to verify applications without exploring all their behaviors. However, they may lack of efficiency when… ▽ More Assessing the correctness of distributed and parallel applications is notoriously difficult due to the complexity of the concurrent behaviors and the difficulty to reproduce bugs. In this context, Dynamic Partial Order Reduction (DPOR) techniques have proved successful in exploiting concurrency to verify applications without exploring all their behaviors. However, they may lack of efficiency when tracking non-systematic bugs of real size applications. In this paper, we suggest two adaptations of the Optimal Dynamic Partial Order Reduction (ODPOR) algorithm with a particular focus on bug finding and explanation. The first adaptation is an out-of-order version called RFS ODPOR which avoids being stuck in uninteresting large parts of the state space. Once a bug is found, the second adaptation takes advantage of ODPOR principles to efficiently find the origins of the bug. △ Less

Submitted 14 May, 2025; originally announced May 2025.

Journal ref: FORTE 2025 - 45th International Conference on Formal Techniques for Distributed Objects, Components, and Systems, Carla Ferreira, Claudio A. Mezzina, Jun 2025, Lille, France

A new membership inference attack that spots memorization in generative and predictive models: Loss-Based with Reference Model algorithm (LBRM)

Authors: Faiz Taleb, Ivan Gazeau, Maryline Laurent

Abstract: Generative models can unintentionally memorize training data, posing significant privacy risks. This paper addresses the memorization phenomenon in time series imputation models, introducing the Loss-Based with Reference Model (LBRM) algorithm. The LBRM method leverages a reference model to enhance the accuracy of membership inference attacks, distinguishing between training and test data. Our con… ▽ More Generative models can unintentionally memorize training data, posing significant privacy risks. This paper addresses the memorization phenomenon in time series imputation models, introducing the Loss-Based with Reference Model (LBRM) algorithm. The LBRM method leverages a reference model to enhance the accuracy of membership inference attacks, distinguishing between training and test data. Our contributions are twofold: first, we propose an innovative method to effectively extract and identify memorized training data, significantly improving detection accuracy. On average, without fine-tuning, the AUROC improved by approximately 40\%. With fine-tuning, the AUROC increased by approximately 60\%. Second, we validate our approach through membership inference attacks on two types of architectures designed for time series imputation, demonstrating the robustness and versatility of the LBRM approach in different contexts. These results highlight the significant enhancement in detection accuracy provided by the LBRM approach, addressing privacy risks in time series imputation models. △ Less

Submitted 6 May, 2025; originally announced May 2025.

GeoFINDR: Practical Approach to Verify Cloud Instances Geolocation in Multicloud

Authors: Said Ider, Maryline Laurent

Abstract: In multicloud environments, where legal obligations, technical constraints and economic interests are at stake, it is of interest to stakeholders to be able to locate cloud data or the cloud instance where data are decrypted for processing, making it particularly vulnerable. This paper proposes an original and practical delay-based approach, called GeoFINDR, to locate a cloud instance, e.g. a Virt… ▽ More In multicloud environments, where legal obligations, technical constraints and economic interests are at stake, it is of interest to stakeholders to be able to locate cloud data or the cloud instance where data are decrypted for processing, making it particularly vulnerable. This paper proposes an original and practical delay-based approach, called GeoFINDR, to locate a cloud instance, e.g. a Virtual Machine (VM), over the Internet, based on RIPE Atlas landmarks. First, the assumed threat model and assumptions are more realistic than in existing solutions, e.g. VM-scale localization in multicloud environments, a Cloud Service Provider (CSP) lying about the VM's location. Second, the originality of the approach lies in four original ideas: (1) geolocalization is performed from the VM, (2) a Greedy algorithm selects a first set LM_A of distributed audit landmarks in the vicinity of the declared area, (3) a sectorization algorithm identifies a set LM_S of other landmarks with distance delay behavior similar to that of the VM to estimate the sector of the VM, and (4) the estimated location of the VM is calculated as the barycenter position of the LM_S landmarks. An open source tool is published on GitHub and experiments show that localization accuracy can be as high as 22.1km, under unfavorable conditions where the CSP lies about the location of the VM. △ Less

Submitted 25 April, 2025; originally announced April 2025.

BixBench: a Comprehensive Benchmark for LLM-based Agents in Computational Biology

Authors: Ludovico Mitchener, Jon M Laurent, Alex Andonian, Benjamin Tenmann, Siddharth Narayanan, Geemi P Wellawatte, Andrew White, Lorenzo Sani, Samuel G Rodriques

Abstract: Large Language Models (LLMs) and LLM-based agents show great promise in accelerating scientific research. Existing benchmarks for measuring this potential and guiding future development continue to evolve from pure recall and rote knowledge tasks, towards more practical work such as literature review and experimental planning. Bioinformatics is a domain where fully autonomous AI-driven discovery m… ▽ More Large Language Models (LLMs) and LLM-based agents show great promise in accelerating scientific research. Existing benchmarks for measuring this potential and guiding future development continue to evolve from pure recall and rote knowledge tasks, towards more practical work such as literature review and experimental planning. Bioinformatics is a domain where fully autonomous AI-driven discovery may be near, but no extensive benchmarks for measuring progress have been introduced to date. We therefore present the Bioinformatics Benchmark (BixBench), a dataset comprising over 50 real-world scenarios of practical biological data analysis with nearly 300 associated open-answer questions designed to measure the ability of LLM-based agents to explore biological datasets, perform long, multi-step analytical trajectories, and interpret the nuanced results of those analyses. We evaluate the performance of two frontier LLMs (GPT-4o and Claude 3.5 Sonnet) using a custom agent framework we open source. We find that even the latest frontier models only achieve 17% accuracy in the open-answer regime, and no better than random in a multiple-choice setting. By exposing the current limitations of frontier models, we hope BixBench can spur the development of agents capable of conducting rigorous bioinformatic analysis and accelerate scientific discovery. △ Less

Submitted 8 October, 2025; v1 submitted 28 February, 2025; originally announced March 2025.

Comments: 8 main text pages, 5 main figures

A Systematic Review and Layered Framework for Privacy-by-Design in Self-Sovereign Identity Systems

Authors: Montassar Naghmouchi, Maryline Laurent

Abstract: The use of Self-Sovereign Identity (SSI) systems for digital identity management is gaining traction and interest. Countries such as Bhutan have already implemented an SSI infrastructure to manage the identity of their citizens. The EU, thanks to the revised eIDAS regulation, is opening the door for SSI vendors to develop SSI systems for the planned EU digital identity wallet. These developments,… ▽ More The use of Self-Sovereign Identity (SSI) systems for digital identity management is gaining traction and interest. Countries such as Bhutan have already implemented an SSI infrastructure to manage the identity of their citizens. The EU, thanks to the revised eIDAS regulation, is opening the door for SSI vendors to develop SSI systems for the planned EU digital identity wallet. These developments, which fall within the sovereign domain, raise questions about individual privacy. The design of SSI systems is complex, often characterized by a large number of components and architectural choices because the current SSI communities differ on how to create identifiers, how to build and present credentials, and even how to design a user wallet. SSI stacks developed by different organizations provide different privacy features for different privacy needs. This paper performs a systematic mapping and review of SSI components and technologies into a novel four-layer privacy framework to address the design complexity of SSI systems. Based on this review, we provide an accompanying Design Assistance Dashboard (DAD). The DAD shows the interdependencies between SSI components in different layers, and maps these components to different privacy requirements and considerations, even providing a simple privacy class for each component. △ Less

Submitted 28 August, 2025; v1 submitted 4 February, 2025; originally announced February 2025.

Empower Healthcare through a Self-Sovereign Identity Infrastructure for Secure Electronic Health Data Access

Authors: Antonio López Martínez, Montassar Naghmouchi, Maryline Laurent, Joaquin Garcia-Alfaro, Manuel Gil Pérez, Antonio Ruiz Martínez, Pantaleone Nespoli

Abstract: Health data is one of the most sensitive data for people, which attracts the attention of malicious activities. We propose an open-source health data management framework, that follows a patient-centric approach. The proposed framework implements the Self-Sovereign Identity paradigm with innovative technologies such as Decentralized Identifiers and Verifiable Credentials. The framework uses Blockc… ▽ More Health data is one of the most sensitive data for people, which attracts the attention of malicious activities. We propose an open-source health data management framework, that follows a patient-centric approach. The proposed framework implements the Self-Sovereign Identity paradigm with innovative technologies such as Decentralized Identifiers and Verifiable Credentials. The framework uses Blockchain technology to provide immutability, verifiable data registry, and auditability, as well as an agent-based model to provide protection and privacy for the patient data. We also define different use cases regarding the daily patient-practitioner-laboratory interactions and specific functions to cover patient data loss, data access revocation, and emergency cases where patients are unable to give consent and access to their data. To address this design, a proof of concept is created with an interaction between patient and doctor. The most feasible technologies are selected and the created design is validated. We discuss the differences and novelties of this framework, which includes the patient-centric approach also for data storage, the designed recovery and emergency plan, the defined backup procedure, and the selected blockchain platform. △ Less

Submitted 21 January, 2025; originally announced January 2025.

Comments: 40 pages, 11 figures

Practical and Ready-to-Use Methodology to Assess the re-identification Risk in Anonymized Datasets

Authors: Louis-Philippe Sondeck, Maryline Laurent

Abstract: To prove that a dataset is sufficiently anonymized, many privacy policies suggest that a re-identification risk assessment be performed, but do not provide a precise methodology for doing so, leaving the industry alone with the problem. This paper proposes a practical and ready-to-use methodology for re-identification risk assessment, the originality of which is manifold: (1) it is the first to fo… ▽ More To prove that a dataset is sufficiently anonymized, many privacy policies suggest that a re-identification risk assessment be performed, but do not provide a precise methodology for doing so, leaving the industry alone with the problem. This paper proposes a practical and ready-to-use methodology for re-identification risk assessment, the originality of which is manifold: (1) it is the first to follow well-known risk analysis methods (e.g. EBIOS) that have been used in the cybersecurity field for years, which consider not only the ability to perform an attack, but also the impact such an attack can have on an individual; (2) it is the first to qualify attributes and values of attributes with e.g. degree of exposure, as known real-world attacks mainly target certain types of attributes and not others. △ Less

Submitted 18 January, 2025; originally announced January 2025.

Language agents achieve superhuman synthesis of scientific knowledge

Authors: Michael D. Skarlinski, Sam Cox, Jon M. Laurent, James D. Braza, Michaela Hinks, Michael J. Hammerling, Manvitha Ponnapati, Samuel G. Rodriques, Andrew D. White

Abstract: Language models are known to hallucinate incorrect information, and it is unclear if they are sufficiently accurate and reliable for use in scientific research. We developed a rigorous human-AI comparison methodology to evaluate language model agents on real-world literature search tasks covering information retrieval, summarization, and contradiction detection tasks. We show that PaperQA2, a fron… ▽ More Language models are known to hallucinate incorrect information, and it is unclear if they are sufficiently accurate and reliable for use in scientific research. We developed a rigorous human-AI comparison methodology to evaluate language model agents on real-world literature search tasks covering information retrieval, summarization, and contradiction detection tasks. We show that PaperQA2, a frontier language model agent optimized for improved factuality, matches or exceeds subject matter expert performance on three realistic literature research tasks without any restrictions on humans (i.e., full access to internet, search tools, and time). PaperQA2 writes cited, Wikipedia-style summaries of scientific topics that are significantly more accurate than existing, human-written Wikipedia articles. We also introduce a hard benchmark for scientific literature research called LitQA2 that guided design of PaperQA2, leading to it exceeding human performance. Finally, we apply PaperQA2 to identify contradictions within the scientific literature, an important scientific task that is challenging for humans. PaperQA2 identifies 2.34 +/- 1.99 contradictions per paper in a random subset of biology papers, of which 70% are validated by human experts. These results demonstrate that language model agents are now capable of exceeding domain experts across meaningful tasks on scientific literature. △ Less

Submitted 26 September, 2024; v1 submitted 10 September, 2024; originally announced September 2024.

Self-Sovereign Identity for Consented and Content-Based Access to Medical Records using Blockchain

Authors: Marie Tcholakian, Karolina Gorna, Maryline Laurent, Hella Kaffel Ben Ayed, Montassar Naghmouchi

Abstract: Electronic Health Records (EHRs) and Medical Data are classified as personal data in every privacy law, meaning that any related service that includes processing such data must come with full security, confidentiality, privacy and accountability. Solutions for health data management, as in storing it, sharing and processing it, are emerging quickly and were significantly boosted by the Covid-19 pa… ▽ More Electronic Health Records (EHRs) and Medical Data are classified as personal data in every privacy law, meaning that any related service that includes processing such data must come with full security, confidentiality, privacy and accountability. Solutions for health data management, as in storing it, sharing and processing it, are emerging quickly and were significantly boosted by the Covid-19 pandemic that created a need to move things online. EHRs makes a crucial part of digital identity data, and the same digital identity trends -- as in self sovereign identity powered by decentralized ledger technologies like Blockchain, are being researched or implemented in contexts managing digital interactions between health facilities, patients and health professionals. In this paper, we propose a blockchain-based solution enabling secure exchange of EHRs between different parties powered by a self-sovereign identity (SSI) wallet and decentralized identifiers. We also make use of a consortium IPFS network for off-chain storage and attribute-based encryption (ABE) to ensure data confidentiality and integrity. Through our solution, we grant users full control over their medical data, and enable them to securely share it in total confidentiality over secure communication channels between user wallets using encryption. We also use DIDs for better user privacy and limit any possible correlations or identification by using pairwise DIDs. Overall, combining this set of technologies guarantees secure exchange of EHRs, secure storage and management along with by-design features inherited from the technological stack. △ Less

Submitted 31 July, 2024; originally announced July 2024.

Comments: 13 pages, 11 figures

LAB-Bench: Measuring Capabilities of Language Models for Biology Research

Authors: Jon M. Laurent, Joseph D. Janizek, Michael Ruzo, Michaela M. Hinks, Michael J. Hammerling, Siddharth Narayanan, Manvitha Ponnapati, Andrew D. White, Samuel G. Rodriques

Abstract: There is widespread optimism that frontier Large Language Models (LLMs) and LLM-augmented systems have the potential to rapidly accelerate scientific discovery across disciplines. Today, many benchmarks exist to measure LLM knowledge and reasoning on textbook-style science questions, but few if any benchmarks are designed to evaluate language model performance on practical tasks required for scien… ▽ More There is widespread optimism that frontier Large Language Models (LLMs) and LLM-augmented systems have the potential to rapidly accelerate scientific discovery across disciplines. Today, many benchmarks exist to measure LLM knowledge and reasoning on textbook-style science questions, but few if any benchmarks are designed to evaluate language model performance on practical tasks required for scientific research, such as literature search, protocol planning, and data analysis. As a step toward building such benchmarks, we introduce the Language Agent Biology Benchmark (LAB-Bench), a broad dataset of over 2,400 multiple choice questions for evaluating AI systems on a range of practical biology research capabilities, including recall and reasoning over literature, interpretation of figures, access and navigation of databases, and comprehension and manipulation of DNA and protein sequences. Importantly, in contrast to previous scientific benchmarks, we expect that an AI system that can achieve consistently high scores on the more difficult LAB-Bench tasks would serve as a useful assistant for researchers in areas such as literature search and molecular cloning. As an initial assessment of the emergent scientific task capabilities of frontier language models, we measure performance of several against our benchmark and report results compared to human expert biology researchers. We will continue to update and expand LAB-Bench over time, and expect it to serve as a useful tool in the development of automated research systems going forward. A public subset of LAB-Bench is available for use at the following URL: https://huggingface.co/datasets/futurehouse/lab-bench △ Less

Submitted 17 July, 2024; v1 submitted 14 July, 2024; originally announced July 2024.

Comments: 40 pages, 5 main figures, 1 main table, 2 supplemental figures, 4 supplemental tables. Submitted to NeurIPS 2024 Datasets and Benchmarks track (in review)

Polymorphic Type Inference for Dynamic Languages

Authors: Giuseppe Castagna, Mickaël Laurent, Kim Nguyen

Abstract: We present a type system that combines, in a controlled way, first-order polymorphism with intersectiontypes, union types, and subtyping, and prove its safety. We then define a type reconstruction algorithm that issound and terminating. This yields a system in which unannotated functions are given polymorphic types(thanks to Hindley-Milner) that can express the overloaded behavior of the functions… ▽ More We present a type system that combines, in a controlled way, first-order polymorphism with intersectiontypes, union types, and subtyping, and prove its safety. We then define a type reconstruction algorithm that issound and terminating. This yields a system in which unannotated functions are given polymorphic types(thanks to Hindley-Milner) that can express the overloaded behavior of the functions they type (thanks tothe intersection introduction rule) and that are deduced by applying advanced techniques of type narrowing(thanks to the union elimination rule). This makes the system a prime candidate to type dynamic languages. △ Less

Submitted 17 November, 2023; originally announced November 2023.

Journal ref: Proceedings of the ACM on Programming Languages, In press, 8 (POPL), pp.40

Comparative Analysis of Technical and Legal Frameworks of Various National Digial Identity Solutions

Authors: Montassar Naghmouchi, Maryline Laurent, Claire Levallois-Barth, Nesrine Kaaniche

Abstract: National digital identity systems have become a key requirement for easy access to online public services, specially during Covid-19. While many countries have adopted a national digital identity system, many are still in the process of establishing one. Through a comparative analysis of the technological and legal dimensions of a few selected national digital identity solutions currently being us… ▽ More National digital identity systems have become a key requirement for easy access to online public services, specially during Covid-19. While many countries have adopted a national digital identity system, many are still in the process of establishing one. Through a comparative analysis of the technological and legal dimensions of a few selected national digital identity solutions currently being used in different countries, we highlight the diversity of technologies and architectures and the key role of the legal framework of a given digital identity solution. We also present several key issues related to the implementation of these solutions, how to ensure the State sovereignty over them, and how to strike the right balance between private sector and public sector needs. This position paper aims to help policy makers, software developers and concerned users understand the challenges of designing, implementing and using a national digital identity management system and establishing a legal framework for digital identity management, including personal data protection measures. The authors of this paper have a favorable position for self-sovereign identity management systems that are based on Blockchain technology, and we believe they are the most suitable for national digital identity systems. △ Less

Submitted 2 October, 2023; originally announced October 2023.

Comments: 29 pages, 4 tables, 5 labled figures, 3 figures within table 1 as illustration, 51 references

Integrating Usage Control into Distributed Ledger Technology for Internet of Things Privacy

Authors: Nathanaël Denis, Maryline Laurent, Sophie Chabridon

Abstract: The Internet of Things brings new ways to collect privacy-sensitive data from billions of devices. Well-tailored distributed ledger technologies (DLTs) can provide high transaction processing capacities to IoT devices in a decentralized fashion. However, privacy aspects are often neglected or unsatisfying, with a focus mainly on performance and security. In this paper, we introduce decentralized u… ▽ More The Internet of Things brings new ways to collect privacy-sensitive data from billions of devices. Well-tailored distributed ledger technologies (DLTs) can provide high transaction processing capacities to IoT devices in a decentralized fashion. However, privacy aspects are often neglected or unsatisfying, with a focus mainly on performance and security. In this paper, we introduce decentralized usage control mechanisms to empower IoT devices to control the data they generate. Usage control defines obligations, i.e., actions to be fulfilled to be granted access, and conditions on the system in addition to data dissemination control. The originality of this paper is to consider the usage control system as a component of distributed ledger networks, instead of an external tool. With this integration, both technologies work in synergy, benefiting their privacy, security and performance. We evaluated the performance improvements of integration using the IOTA technology, particularly suitable due to the participation of small devices in the consensus. The results of the tests on a private network show an approximate 90% decrease of the time needed for the UCS to push a transaction and make its access decision in the integrated setting, regardless of the number of nodes in the network. △ Less

Submitted 9 June, 2023; originally announced June 2023.

Journal ref: IEEE Internet of Things Journal, 2023, pp.1-1

SPOT: Secure and Privacy-preserving prOximiTy protocol for e-healthcare systems

Authors: Souha Masmoudi, Nesrine Kaaniche, Maryline Laurent

Abstract: This paper introduces SPOT, a Secure and Privacy-preserving prOximity based protocol for e-healthcare systems. It relies on a distributed proxy-based approach to preserve users' privacy and a semi-trusted computing server to ensure data consistency and integrity. The proposed protocol ensures a balance between security, privacy and scalability. As far as we know, in terms of security, SPOT is the… ▽ More This paper introduces SPOT, a Secure and Privacy-preserving prOximity based protocol for e-healthcare systems. It relies on a distributed proxy-based approach to preserve users' privacy and a semi-trusted computing server to ensure data consistency and integrity. The proposed protocol ensures a balance between security, privacy and scalability. As far as we know, in terms of security, SPOT is the first one to prevent malicious users from colluding and generating false positives. In terms of privacy, SPOT supports both anonymity of users being in proximity of infected people and unlinkability of contact information issued by the same user. A concrete construction based on structure-preserving signatures and NIWI proofs is proposed and a detailed security and privacy analysis proves that SPOT is secure under standard assumptions. In terms of scalability, SPOT's procedures and algorithms are implemented to show its efficiency and practical usability with acceptable computation and communication overhead. △ Less

Submitted 1 December, 2022; originally announced December 2022.

Comments: 15 pages

Journal ref: IEEE Access, vol. 10, pp. 106400-106414, 2022

Enabling Fast and Flexible Distributed Deep Learning with Programmable Switches

Authors: Heng Pan, Penglai Cui, Zhenyu li, Ru Jia, Penghao Zhang, Leilei Zhang, Ye Yang, Jiahao Wu, Jianbo Dong, Zheng Cao, Qiang Li, Hongqiang Harry Liu, Mathy Laurent, Gaogang Xie

Abstract: Deep learning has been used in a wide range of areas and made a huge breakthrough. With the ever-increasing model size and train-ing data volume, distributed deep learning emerges which utilizes a cluster to train a model in parallel. Unfortunately, the performance is often far from linear speedup due to the communication overhead between cluster nodes. To address this challenge, this paper design… ▽ More Deep learning has been used in a wide range of areas and made a huge breakthrough. With the ever-increasing model size and train-ing data volume, distributed deep learning emerges which utilizes a cluster to train a model in parallel. Unfortunately, the performance is often far from linear speedup due to the communication overhead between cluster nodes. To address this challenge, this paper designs and implements Libra, a network aggregator, that utilizes in-network computation to optimize the communication for distributed DL training in two aspects: 1) reduce active connections and 2) aggregate exchanged network packets. We implemented our Libra on Intel Tofino switches, customized a lightweight host stack and integrated it into an open-source training framework PS-lite. The experimental result shows that our Libra can achieve 1.5~4 times speedup. △ Less

Submitted 10 August, 2022; v1 submitted 10 May, 2022; originally announced May 2022.

Comments: 13 pages, 18 figures

An automatized Identity and Access Management system for IoT combining Self-Sovereign Identity and smart contracts

Authors: Montassar Naghmouchi, Hella Kaffel, Maryline Laurent

Abstract: Nowadays, open standards for self-sovereign identity and access management enable portable solutions that are following the requirements of IoT systems. This paper proposes a blockchain-based identity and access management system for IoT -- specifically smart vehicles -- as an example of use-case, showing two interoperable blockchains, Ethereum and Hyperledger Indy, and a self-sovereign identity m… ▽ More Nowadays, open standards for self-sovereign identity and access management enable portable solutions that are following the requirements of IoT systems. This paper proposes a blockchain-based identity and access management system for IoT -- specifically smart vehicles -- as an example of use-case, showing two interoperable blockchains, Ethereum and Hyperledger Indy, and a self-sovereign identity model. △ Less

Submitted 1 January, 2022; originally announced January 2022.

Comments: extended version of a paper published in The 14th International Symposium on Foundations and Practice of Security, FPS 2021, 8-10 December 2021

MSC Class: 68M14 (Primary) 68M25 (Secondary) ACM Class: C.2.2; C.2.4

Personal information self-management: A survey of technologies supporting administrative services

Authors: Paul Marillonnet, Maryline Laurent, Mikaël Ates

Abstract: This paper presents a survey of technologies for personal data self-management interfacing with administrative and territorial public service providers. It classifies a selection of scientific technologies into four categories of solutions: Personal Data Store (PDS), Identity Manager (IdM), Anonymous Certificate System and Access Control Delegation Architecture. Each category, along with its techn… ▽ More This paper presents a survey of technologies for personal data self-management interfacing with administrative and territorial public service providers. It classifies a selection of scientific technologies into four categories of solutions: Personal Data Store (PDS), Identity Manager (IdM), Anonymous Certificate System and Access Control Delegation Architecture. Each category, along with its technological approach, is analyzed thanks to eighteen identified functional criteria that encompass architectural and communication aspects, as well as user data lifecycle considerations. The originality of the survey is multifold. First, as far as we know, there is no such thorough survey covering such a panel of a dozen of existing solutions. Second, it is the first survey addressing Personally Identifiable Information (PII) management for both administrative and private service providers. Third, this paper achieves a functional comparison of solutions of very different technical natures. The outcome of this paper is the clear identification of functional gaps of each solution. As a result, this paper establishes the research directions to follow in order to fill these functional gaps. △ Less

Submitted 27 September, 2021; originally announced September 2021.

Journal ref: Journal of Computer Science and Technology, 2021

A Validated Privacy-Utility Preserving Recommendation System with Local Differential Privacy

Authors: Seryne Rahali, Maryline Laurent, Souha Masmoudi, Charles Roux, Brice Mazeau

Abstract: This paper proposes a new recommendation system preserving both privacy and utility. It relies on the local differential privacy (LDP) for the browsing user to transmit his noisy preference profile, as perturbed Bloom filters, to the service provider. The originality of the approach is multifold. First, as far as we know, the approach is the first one including at the user side two perturbation ro… ▽ More This paper proposes a new recommendation system preserving both privacy and utility. It relies on the local differential privacy (LDP) for the browsing user to transmit his noisy preference profile, as perturbed Bloom filters, to the service provider. The originality of the approach is multifold. First, as far as we know, the approach is the first one including at the user side two perturbation rounds - PRR (Permanent Randomized Response) and IRR (Instantaneous Randomized Response) - over a complete user profile. Second, a full validation experimentation chain is set up, with a machine learning decoding algorithm based on neural network or XGBoost for decoding the perturbed Bloom filters and the clustering Kmeans tool for clustering users. Third, extensive experiments show that our method achieves good utility-privacy trade-off, i.e. a 90$\%$ clustering success rate, resp. 80.3$\%$ for a value of LDP $ε= 0.8$, resp. $ε= 2$. Fourth, an experimental and theoretical analysis gives concrete results on the resistance of our approach to the plausible deniability and resistance against averaging attacks. △ Less

Submitted 23 September, 2021; originally announced September 2021.

Comments: Accepted for publication in the 15th IEEE International Conference on Big Data Science and Engineering (BigDataSE 2021)

Merit and Blame Assignment with Kind 2

Authors: Daniel Larraz, Mickaël Laurent, Cesare Tinelli

Abstract: We introduce two new major features of the open-source model checker Kind 2 which provide traceability information between specification and design elements such as assumptions, guarantees, or other behavioral constraints in synchronous reactive system models. This new version of Kind 2 can identify minimal sets of design elements, known as Minimal Inductive Validity Cores, which are sufficient to… ▽ More We introduce two new major features of the open-source model checker Kind 2 which provide traceability information between specification and design elements such as assumptions, guarantees, or other behavioral constraints in synchronous reactive system models. This new version of Kind 2 can identify minimal sets of design elements, known as Minimal Inductive Validity Cores, which are sufficient to prove a given set of safety properties, and also determine the set of MUST elements, design elements that are necessary to prove the given properties. In addition, Kind 2 is able to find minimal sets of design constraints, known as Minimal Cut Sets, whose violation leads the system to an unsafe state. The computed information can be used for several purposes, including assessing the quality of a system specification, tracking the safety impact of model changes, and analyzing the tolerance and resilience of a system against faults or cyber-attacks. We describe these new capabilities in some detail and report on an initial experimental evaluation of some of them. △ Less

Submitted 13 May, 2021; originally announced May 2021.

Recommending Podcasts for Cold-Start Users Based on Music Listening and Taste

Authors: Zahra Nazari, Christophe Charbuillet, Johan Pages, Martin Laurent, Denis Charrier, Briana Vecchione, Ben Carterette

Abstract: Recommender systems are increasingly used to predict and serve content that aligns with user taste, yet the task of matching new users with relevant content remains a challenge. We consider podcasting to be an emerging medium with rapid growth in adoption, and discuss challenges that arise when applying traditional recommendation approaches to address the cold-start problem. Using music consumptio… ▽ More Recommender systems are increasingly used to predict and serve content that aligns with user taste, yet the task of matching new users with relevant content remains a challenge. We consider podcasting to be an emerging medium with rapid growth in adoption, and discuss challenges that arise when applying traditional recommendation approaches to address the cold-start problem. Using music consumption behavior, we examine two main techniques in inferring Spotify users preferences over more than 200k podcasts. Our results show significant improvements in consumption of up to 50\% for both offline and online experiments. We provide extensive analysis on model performance and examine the degree to which music data as an input source introduces bias in recommendations. △ Less

Submitted 26 July, 2020; originally announced July 2020.

Comments: SIGIR 2020

Securing Organization's Data: A Role-Based Authorized Keyword Search Scheme with Efficient Decryption

Authors: Nazatul Haque Sultan, Maryline Laurent, Vijay Varadharajan

Abstract: For better data availability and accessibility while ensuring data secrecy, organizations often tend to outsource their encrypted data to the cloud storage servers, thus bringing the challenge of keyword search over encrypted data. In this paper, we propose a novel authorized keyword search scheme using Role-Based Encryption (RBE) technique in a cloud environment. The contributions of this paper a… ▽ More For better data availability and accessibility while ensuring data secrecy, organizations often tend to outsource their encrypted data to the cloud storage servers, thus bringing the challenge of keyword search over encrypted data. In this paper, we propose a novel authorized keyword search scheme using Role-Based Encryption (RBE) technique in a cloud environment. The contributions of this paper are multi-fold. First, it presents a keyword search scheme which enables only the authorized users, having proper assigned roles, to delegate keyword-based data search capabilities over encrypted data to the cloud providers without disclosing any sensitive information. Second, it supports a multi-organization cloud environment, where the users can be associated with more than one organization. Third, the proposed scheme provides efficient decryption, conjunctive keyword search and revocation mechanisms. Fourth, the proposed scheme outsources expensive cryptographic operations in decryption to the cloud in a secure manner. Fifth, we have provided a formal security analysis to prove that the proposed scheme is semantically secure against Chosen Plaintext and Chosen Keyword Attacks. Finally, our performance analysis shows that the proposed scheme is suitable for practical applications. △ Less

Submitted 22 April, 2020; originally announced April 2020.

Report number: 11

Journal ref: EEE Transactions on Cloud Computing, 2023

Revisiting Occurrence Typing

Authors: Giuseppe Castagna, Victor Lanvin, Mickaël Laurent, Kim Nguyen

Abstract: We revisit occurrence typing, a technique to refine the type of variables occurring in type-cases and, thus, capturesome programming patterns used in untyped languages. Although occurrence typing was tied from its inceptionto set-theoretic types-union types, in particular-it never fully exploited the capabilities of these types. Here weshow how, by using set-theoretic types, it is possible to deve… ▽ More We revisit occurrence typing, a technique to refine the type of variables occurring in type-cases and, thus, capturesome programming patterns used in untyped languages. Although occurrence typing was tied from its inceptionto set-theoretic types-union types, in particular-it never fully exploited the capabilities of these types. Here weshow how, by using set-theoretic types, it is possible to develop a general typing framework that encompasses andgeneralizes several aspects of current occurrence typing proposals and that can be applied to tackle other problemssuch as the reconstruction of intersection types for unannotated or partially annotated functions and the optimizationof the compilation of gradually typed languages. △ Less

Submitted 12 February, 2022; v1 submitted 12 July, 2019; originally announced July 2019.

A data-supported history of bioinformatics tools

Authors: Levin Clément, Dynomant Emeric, Gonzalez Bruno J, Mouchard Laurent, Landsman David, Hovig Eivind, Vlahovicek Kristian

Abstract: Since the advent of next-generation sequencing in the early 2000s, the volume of bioinformatics software tools and databases has exploded and continues to grow rapidly. Documenting this evolution on a global and time-dependent scale is a challenging task, limited by the scarcity of comprehensive tool repositories. We collected data from over ~23,000 references classified in the OMICtools database,… ▽ More Since the advent of next-generation sequencing in the early 2000s, the volume of bioinformatics software tools and databases has exploded and continues to grow rapidly. Documenting this evolution on a global and time-dependent scale is a challenging task, limited by the scarcity of comprehensive tool repositories. We collected data from over ~23,000 references classified in the OMICtools database, spanning the last 26 years of bioinformatics to present a data-supported snapshot of bioinformatics software tool evolution and the current status, to shed light on future directions and opportunities in this field. The present review explores new aspects of computational biology, including country partnerships, trends in technologies and area of development, research and development (R&D) investments and coding languages. This is the most comprehensive systematic overview of the field to date and provides the community with insights and knowledge on the direction of the development and evolution of bioinformatics software tools, highlighting the increasing complexity of analysis. △ Less

Submitted 18 July, 2018; originally announced July 2018.

Comments: 9 pages

Serverless Protocols for Inventory and Tracking with a UAV

Authors: Collins Mtita, Maryline Laurent, Damien Sauveron, Raja Naeem Akram, Konstantinos Markantonakis, Serge Chaumette

Abstract: It is widely acknowledged that the proliferation of Unmanned Aerial Vehicles (UAVs) may lead to serious concerns regarding avionics safety, particularly when end-users are not adhering to air safety regulations. There are, however, domains in which UAVs may help to increase the safety of airplanes and the management of flights and airport resources that often require substantial human resources. F… ▽ More It is widely acknowledged that the proliferation of Unmanned Aerial Vehicles (UAVs) may lead to serious concerns regarding avionics safety, particularly when end-users are not adhering to air safety regulations. There are, however, domains in which UAVs may help to increase the safety of airplanes and the management of flights and airport resources that often require substantial human resources. For instance, Paris Charles de Gaulle airport (CDG) has more than 7,000 staff and supports 30,000 direct jobs for more than 60 million passengers per year (as of 2016). Indeed, these new systems can be used beneficially for several purposes, even in sensitive areas like airports. Among the considered applications are those that suggest using UAVs to enhance safety of on-ground airplanes; for instance, by collecting (once the aircraft has landed) data recorded by different systems during the flight (like the sensors of the Aircraft Data Networks - ADN) or by examining the state of airplane structure. In this paper, our proposal is to use UAVs, under the control of the airport authorities, to inventory and track various tagged assets, such as luggage, supplies required for the flights, and maintenance tools. The aim of our proposal is to make airport management systems more efficient for operations requiring inventory and tracking, along with increasing safety (sensitive assets such as refueling tanks, or sensitive pieces of luggage can be tracked), thus raising financial profit. △ Less

Submitted 17 August, 2017; originally announced August 2017.

Comments: 11 pages, Conference, The 36th IEEE/AIAA Digital Avionics Systems Conference (DASC'17)

A Structural Characterization for Certifying Robinsonian Matrices

Authors: Monique Laurent, Matteo Seminaroti, Shin-ichi Tanigawa

Abstract: A symmetric matrix is Robinsonian if its rows and columns can be simultaneously reordered in such a way that entries are monotone nondecreasing in rows and columns when moving toward the diagonal. The adjacency matrix of a graph is Robinsonian precisely when the graph is a unit interval graph, so that Robinsonian matrices form a matrix analogue of the class of unit interval graphs. Here we provide… ▽ More A symmetric matrix is Robinsonian if its rows and columns can be simultaneously reordered in such a way that entries are monotone nondecreasing in rows and columns when moving toward the diagonal. The adjacency matrix of a graph is Robinsonian precisely when the graph is a unit interval graph, so that Robinsonian matrices form a matrix analogue of the class of unit interval graphs. Here we provide a structural characterization for Robinsonian matrices in terms of forbidden substructures, extending the notion of asteroidal triples to weighted graphs. This implies the known characterization of unit interval graphs and leads to an efficient algorithm for certifying that a matrix is not Robinsonian. △ Less

Submitted 3 January, 2017; originally announced January 2017.

Comments: 21 pages, 1 figure

MSC Class: 05C50; 05C75; 68R10; 68R05

Similarity-First Search: a new algorithm with application to Robinsonian matrix recognition

Authors: Monique Laurent, Matteo Seminaroti

Abstract: We present a new efficient combinatorial algorithm for recognizing if a given symmetric matrix is Robinsonian, i.e., if its rows and columns can be simultaneously reordered so that entries are monotone nondecreasing in rows and columns when moving toward the diagonal. As main ingredient we introduce a new algorithm, named Similarity-First-Search (SFS), which extends Lexicographic Breadth-First Sea… ▽ More We present a new efficient combinatorial algorithm for recognizing if a given symmetric matrix is Robinsonian, i.e., if its rows and columns can be simultaneously reordered so that entries are monotone nondecreasing in rows and columns when moving toward the diagonal. As main ingredient we introduce a new algorithm, named Similarity-First-Search (SFS), which extends Lexicographic Breadth-First Search (Lex-BFS) to weighted graphs and which we use in a multisweep algorithm to recognize Robinsonian matrices. Since Robinsonian binary matrices correspond to unit interval graphs, our algorithm can be seen as a generalization to weighted graphs of the 3-sweep Lex-BFS algorithm of Corneil for recognizing unit interval graphs. This new recognition algorithm is extremely simple and it exploits new insight on the combinatorial structure of Robinsonian matrices. For an $n\times n$ nonnegative matrix with $m$ nonzero entries, it terminates in $n-1$ SFS sweeps, with overall running time $O(n^2 +nm\log n)$. △ Less

Submitted 19 December, 2016; v1 submitted 14 January, 2016; originally announced January 2016.

Comments: 35 pages, 5 figures

A Lex-BFS-based recognition algorithm for Robinsonian matrices

Authors: Monique Laurent, Matteo Seminaroti

Abstract: Robinsonian matrices arise in the classical seriation problem and play an important role in many applications where unsorted similarity (or dissimilarity) information must be reordered. We present a new polynomial time algorithm to recognize Robinsonian matrices based on a new characterization of Robinsonian matrices in terms of straight enumerations of unit interval graphs. The algorithm is simpl… ▽ More Robinsonian matrices arise in the classical seriation problem and play an important role in many applications where unsorted similarity (or dissimilarity) information must be reordered. We present a new polynomial time algorithm to recognize Robinsonian matrices based on a new characterization of Robinsonian matrices in terms of straight enumerations of unit interval graphs. The algorithm is simple and is based essentially on lexicographic breadth-first search (Lex-BFS), using a divide-and-conquer strategy. When applied to a nonnegative symmetric $n\times n$ matrix with~$m$ nonzero entries and given as a weighted adjacency list, it runs in $O(d(n+m))$ time, where $d$ is the depth of the recursion tree, which is at most the number of distinct nonzero entries of $A$. △ Less

Submitted 19 December, 2016; v1 submitted 24 April, 2015; originally announced April 2015.

Comments: 30 pages, 7 figures

The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure

Authors: Monique Laurent, Matteo Seminaroti

Abstract: We present a new polynomially solvable case of the Quadratic Assignment Problem in Koopmans-Beckman form $QAP(A,B)$, by showing that the identity permutation is optimal when $A$ and $B$ are respectively a Robinson similarity and dissimilarity matrix and one of $A$ or $B$ is a Toeplitz matrix. A Robinson (dis)similarity matrix is a symmetric matrix whose entries (increase) decrease monotonically al… ▽ More We present a new polynomially solvable case of the Quadratic Assignment Problem in Koopmans-Beckman form $QAP(A,B)$, by showing that the identity permutation is optimal when $A$ and $B$ are respectively a Robinson similarity and dissimilarity matrix and one of $A$ or $B$ is a Toeplitz matrix. A Robinson (dis)similarity matrix is a symmetric matrix whose entries (increase) decrease monotonically along rows and columns when moving away from the diagonal, and such matrices arise in the classical seriation problem. △ Less

Submitted 13 December, 2014; v1 submitted 10 July, 2014; originally announced July 2014.

Comments: 15 pages, 2 figures

Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope

Authors: Marianna Eisenberg-Nagy, Monique Laurent, Antonios Varvitsiotis

Abstract: We study a new geometric graph parameter $\egd(G)$, defined as the smallest integer $r\ge 1$ for which any partial symmetric matrix which is completable to a correlation matrix and whose entries are specified at the positions of the edges of $G$, can be completed to a matrix in the convex hull of correlation matrices of $\rank $ at most $r$. This graph parameter is motivated by its relevance to th… ▽ More We study a new geometric graph parameter $\egd(G)$, defined as the smallest integer $r\ge 1$ for which any partial symmetric matrix which is completable to a correlation matrix and whose entries are specified at the positions of the edges of $G$, can be completed to a matrix in the convex hull of correlation matrices of $\rank $ at most $r$. This graph parameter is motivated by its relevance to the problem of finding low rank solutions to semidefinite programs over the elliptope, and also by its relevance to the bounded rank Grothendieck constant. Indeed, $\egd(G)\le r$ if and only if the rank-$r$ Grothendieck constant of $G$ is equal to 1. We show that the parameter $\egd(G)$ is minor monotone, we identify several classes of forbidden minors for $\egd(G)\le r$ and we give the full characterization for the case $r=2$. We also show an upper bound for $\egd(G)$ in terms of a new tree-width-like parameter $\sla(G)$, defined as the smallest $r$ for which $G$ is a minor of the strong product of a tree and $K_r$. We show that, for any 2-connected graph $G\ne K_{3,3}$ on at least 6 nodes, $\egd(G)\le 2$ if and only if $\sla(G)\le 2$. △ Less

Submitted 9 January, 2014; v1 submitted 9 May, 2012; originally announced May 2012.

Comments: 33 pages, 8 Figures. In its second version, the paper has been modified to accommodate the suggestions of the referees. Furthermore, the title has been changed since we feel that the new title reflects more accurately the content and the main results of the paper

A new graph parameter related to bounded rank positive semidefinite matrix completions

Authors: Monique Laurent, Antonios Varvitsiotis

Abstract: The Gram dimension $\gd(G)$ of a graph $G$ is the smallest integer $k\ge 1$ such that any partial real symmetric matrix, whose entries are specified on the diagonal and at the off-diagonal positions corresponding to edges of $G$, can be completed to a positive semidefinite matrix of rank at most $k$ (assuming a positive semidefinite completion exists). For any fixed $k$ the class of graphs satisfy… ▽ More The Gram dimension $\gd(G)$ of a graph $G$ is the smallest integer $k\ge 1$ such that any partial real symmetric matrix, whose entries are specified on the diagonal and at the off-diagonal positions corresponding to edges of $G$, can be completed to a positive semidefinite matrix of rank at most $k$ (assuming a positive semidefinite completion exists). For any fixed $k$ the class of graphs satisfying $\gd(G) \le k$ is minor closed, hence it can characterized by a finite list of forbidden minors. We show that the only minimal forbidden minor is $K_{k+1}$ for $k\le 3$ and that there are two minimal forbidden minors: $K_5$ and $K_{2,2,2}$ for $k=4$. We also show some close connections to Euclidean realizations of graphs and to the graph parameter $ν^=(G)$ of \cite{H03}. In particular, our characterization of the graphs with $\gd(G)\le 4$ implies the forbidden minor characterization of the 3-realizable graphs of Belk and Connelly \cite{Belk,BC} and of the graphs with $ν^=(G) \le 4$ of van der Holst \cite{H03}. △ Less

Submitted 3 April, 2012; originally announced April 2012.

Comments: 31 pages, 6 Figures. arXiv admin note: substantial text overlap with arXiv:1112.5960

A Sparse Flat Extension Theorem for Moment Matrices

Authors: Monique Laurent, Bernard Mourrain

Abstract: In this note we prove a generalization of the flat extension theorem of Curto and Fialkow for truncated moment matrices. It applies to moment matrices indexed by an arbitrary set of monomials and its border, assuming that this set is connected to 1. When formulated in a basis-free setting, this gives an equivalent result for truncated Hankel operators. In this note we prove a generalization of the flat extension theorem of Curto and Fialkow for truncated moment matrices. It applies to moment matrices indexed by an arbitrary set of monomials and its border, assuming that this set is connected to 1. When formulated in a basis-free setting, this gives an equivalent result for truncated Hankel operators. △ Less

Submitted 15 December, 2008; originally announced December 2008.