Publications

2025

• Edge-Minimum Walk of Modular Length in Polynomial Time
  
  • Amarilli Antoine
  • Groz Benoit
  • Wein Nicole
  , 2025, 325, pp.5:1-5:23. We study the problem of finding, in a directed graph, an st-walk of length r mod q which is edge-minimum, i.e., uses the smallest number of distinct edges. Despite the vast literature on paths and cycles with modularity constraints, to the best of our knowledge we are the first to study this problem. Our main result is a polynomial-time algorithm that solves this task when r and q are constants. We also show how our proof technique gives an algorithm to solve a generalization of the well-known Directed Steiner Network problem, in which connections between endpoint pairs are required to satisfy modularity constraints on their length. Our algorithm is polynomial when the number of endpoint pairs and the modularity constraints on the pairs are constants. (10.4230/LIPIcs.ITCS.2025.5)
  DOI : 10.4230/LIPIcs.ITCS.2025.5
• Survey of Results on the ModPath and ModCycle Problems
  
  • Amarilli Antoine
  , 2024. This note summarizes the state of what is known about the tractability of the problem ModPath, which asks if an input undirected graph contains a simple st-path whose length satisfies modulo constraints. We also consider the problem ModCycle, which asks for the existence of a simple cycle subject to such constraints. We also discuss the status of these problems on directed graphs, and on restricted classes of graphs. We explain connections to the problem variant asking for a constant vertex-disjoint number of such paths or cycles, and discuss links to other related work.
• Somewhat homomorphic encryption based on random codes
  
  • Aguilar-Melchor Carlos
  • Dyseryn Victor
  • Gaborit Philippe
  Designs, Codes and Cryptography, Springer Verlag, 2025, 93 (6), pp.1645-1669. We present a secret-key encryption scheme based on random rank metric ideal linear codes with a simple decryption circuit. It supports unlimited homomorphic additions and plaintext multiplications (i.e. the homomorphic multiplication of a clear plaintext with a ciphertext) as well as a fixed arbitrary number of homomorphic multiplications. We study a candidate bootstrapping algorithm that requires no multiplication but additions and plaintext multiplications only. This latter operation is therefore very efficient in our scheme, whereas bootstrapping is usually the main reason which penalizes the performance of other fully homomorphic encryption schemes. However, the security reduction of our scheme restricts the number of independent ciphertexts that can be published. In particular, this prevents to securely evaluate the bootstrapping algorithm as the number of ciphertexts in the key switching material is too large. Our scheme is nonetheless the first somewhat homomorphic encryption scheme based on random ideal codes and a first step towards full homomorphism. Random ideal codes give stronger security guarantees as opposed to existing constructions based on highly structured codes. We give concrete parameters for our scheme that shows that it achieves competitive sizes and performance, with a key size of 3.7 kB and a ciphertext size of 0.9 kB when a single multiplication is allowed. (10.1007/s10623-024-01555-y)
  DOI : 10.1007/s10623-024-01555-y
• Multi-view 3D surface reconstruction from SAR images by inverse rendering
  
  • Barbier--Renard Emile
  • Tupin Florence
  • Trouvé Nicolas
  • Denis Loïc
  IEEE Geoscience and Remote Sensing Letters, IEEE - Institute of Electrical and Electronics Engineers, 2025, 22, pp.4008805. 3D reconstruction of a scene from Synthetic Aperture Radar (SAR) images mainly relies on interferometric measurements, which involve strict constraints on the acquisition process. These last years, progress in deep learning has significantly advanced 3D reconstruction from multiple views in optical imaging, mainly through reconstruction-by-synthesis approaches popularized by Neural Radiance Fields. In this paper, we propose a new inverse rendering method for 3D reconstruction from a few incoherent SAR views, drawing inspiration from optical approaches. First, we introduce a new simplified differentiable SAR rendering model, able to synthetize images from a Digital Surface Model (DSM) and a radar backscattering coefficients map. Then, we introduce a coarse-to-fine strategy to reconstruct the DSM and the map of backscattering coefficients of a SAR scene starting only from a few SAR views. We use a neural field, i.e. a continuous parametric model based on a Multi-Layer Perceptron, to represent the SAR scene. Finally, we present preliminary results of DSM reconstruction from synthetic SAR images produced by ONERA's physically-based EMPRISE simulator, supporting the potential of applying inverse rendering approaches to SAR data in order to efficiently exploit geometric disparities in future applications such as multi-sensor data fusion. (10.1109/LGRS.2025.3572303)
  DOI : 10.1109/LGRS.2025.3572303
• From the Gradient-Step Denoiser to the Proximal Denoiser and their associated convergent Plug-and-Play algorithms
  
  • Herfeld Vincent
  • de Senneville Baudouin Denis
  • Leclaire Arthur
  • Papadakis Nicolas
  , 2025. In this paper we analyze the Gradient-Step Denoiser and its usage in Plug-and-Play algorithms. The Plug-and-Play paradigm of optimization algorithms uses off the shelf denoisers to replace a proximity operator or a gradient descent operator of an image prior. Usually this image prior is implicit and cannot be expressed, but the Gradient-Step Denoiser is trained to be exactly the gradient descent operator or the proximity operator of an explicit functional while preserving state-of-the-art denoising capabilities.
• Did You Forkget It? Detecting One-Day Vulnerabilities in Open-source Forks With Global History Analysis
  
  • Lefeuvre Romain
  • Reux Charly
  • Zacchiroli Stefano
  • Barais Olivier
  • Combemale Benoit
  , 2025. Tracking vulnerabilities inherited from third-party open-source software is a well-known challenge, often addressed by tracing the threads of dependency information. However, vulnerabilities can also propagate through forking: a code repository forked after the introduction of a vulnerability, but before it is patched, may remain vulnerable long after the vulnerability has been fixed in the initial repository. History analysis approaches are used to track vulnerable software versions at scale. However, such approaches fail to track vulnerabilities in forks, leaving fork maintainers to identify them manually. This paper presents a global history analysis approach to help software developers identify one-day (known but unpatched) vulnerabilities in forked repositories. Leveraging the global graph of public code, as captured by the Software Heritage archive, our approach propagates vulnerability information at the commit level and performs automated impact analysis. Starting from 7162 repositories with vulnerable commits listed in OSV, we propagate vulnerability information to 2.2 million forks. We evaluate our approach by filtering forks with significant user bases whose latest commit is still potentially vulnerable, manually auditing the code, and contacting maintainers for confirmation and responsible disclosure. This process identified 135 high-severity one-day vulnerabilities, achieving a precision of 0.69, with 9 confirmed by maintainers.
• Extending InSAR2InSAR to Sentinel-1 Data
  
  • Geara Carla
  • Gelas Colette
  • De Vitry Louis
  • Colin Elise
  • Tupin Florence
  IEEE Geoscience and Remote Sensing Letters, IEEE - Institute of Electrical and Electronics Engineers, 2025. Interferometric SAR parameters estimation is a very important and challenging problem. The InSAR2InSAR method previously proposed is one of the few self-supervised methods that aims to estimate InSAR parameters. This method has proven to outperform state-of-the-art methods on simulated synthetic data. However, it has to be extended on real data. In this letter, we demonstrate that Sentinel-1 images acquired in the Interferometric Wide Swath mode possess the necessary properties to train and apply InSAR2InSAR effectively. In this paper, we demonstrate the ability of InSAR2InSAR to process across-track Sentinel-1 interferometric images with state-of-theart performances.
• University Rents Enabling Corporate Innovation: Mapping Academic Researcher Coding and Discursive Labour in the R Language Ecosystem
  
  • Cai Xiaolan
  • O'Neil Mathieu
  • Zacchiroli Stefano
  Journal of Quantitative Description: Digital Media, University of Zurich, 2025, 5. This article explores the role of unrecognised labour in corporate innovation systems via an analysis of researcher coding and discursive contributions to R, one of the largest statistical software ecosystems. Studies of online platforms typically focus on how platform affordances constrain participants' actions, and profit from their labour. We innovate by connecting the labour performed inside digital platforms to the professional employment of participants. Our case study analyses 8,924 R package repositories on GitHub, examining commits and communications. Our quantitative findings show that researchers, alongside non-affiliated contributors, are the most frequent owners of R package repositories and their most active contributors. Researchers are more likely to hold official roles compared to the average, and to engage in collaborative problem-solving and support work during package development. This means there is, underneath the 'recognised' category of star researchers who transition between academia and industry and secure generous funding, an 'unrecognised' category of researchers who not only create and maintain key statistical infrastructure, but also provide support to industry employees, for no remuneration. Our qualitative findings show how this unrecognised labour affects practitioners. Finally, our analysis of the ideology and practice of free, libre and open source software (FLOSS) shows how this ideology and practice legitimate the use of 'university rents' by Big Tech. (10.51685/jqd.2025.025)
  DOI : 10.51685/jqd.2025.025
• Long-time asymptotics of noisy SVGD outside the population limit
  
  • Priser Victor
  • Bianchi Pascal
  • Salim Adil
  ICLR International Conference on Learning Representations, 2025. Stein Variational Gradient Descent (SVGD) is a widely used sampling algorithm that has been successfully applied in several areas of Machine Learning. SVGD operates by iteratively moving a set of interacting particles (which represent the samples) to approximate the target distribution. Despite recent studies on the complexity of SVGD and its variants, their long-time asymptotic behavior (i.e., after numerous iterations ) is still not understood in the finite number of particles regime. We study the long-time asymptotic behavior of a noisy variant of SVGD. First, we establish that the limit set of noisy SVGD for large is well-defined. We then characterize this limit set, showing that it approaches the target distribution as increases. In particular, noisy SVGD provably avoids the variance collapse observed for SVGD. Our approach involves demonstrating that the trajectories of noisy SVGD closely resemble those described by a McKean-Vlasov process.
• Mathematical Foundations for Side-Channel Analysis of Cryptographic Systems
  
  • Cheng Wei
  • Guilley Sylvain
  • Rioul Olivier
  , 2025, pp.X-411. This book offers the reader a formalization, characterization and quantification of the real threat level posed by side-channel leaks from devices implementing cryptography. It exploits the best mathematical tools for quantifying information leakage and characterizing leakage-based attacks. The two possible approaches are described in detail. This includes the optimal attack strategy that can be derived (in specific contexts) or generic bounds regarding data complexity that can be computed. The tone of this book is essentially mathematical. It aims to establish formal foundations for techniques that are otherwise used as engineering recipes in industrial laboratories or empirical intuitions for deriving security levels from practical implementations. It is a systematization of knowledge and a compilation of relevant tools relating to the practice of side-channel analysis on embedded systems. This book provides an up-to-date and improved analysis and understanding of embedded devices that conceal secrets that can be extracted by an attacker. Typical attacks involve measuring the device's power consumption or radiated electromagnetic field. As a source of noisy information, this correlates it with secrets and enabling these secrets to be retrieved. The attacker in some cases, can purchase a blank device from the same series and learn about its leakage, particularly how it relates to the secrets. This book also covers how such information can enhance hardware attacks deployed on another device. Researchers and engineers working in the field of side-channel security for embedded systems and related countermeasures as well as hardware and software engineers focused on implementing cryptographic functionalities will want to purchase this book as a reference. Advanced-level students majoring in computer science and electrical engineering will find this book valuable as a secondary textbook. (10.1007/978-3-031-64399-6)
  DOI : 10.1007/978-3-031-64399-6
• Réélaboration des règles de sécurité en contextes interpersonnels : le cas du toucher en temps de Covid‑19
  
  • Héron Robin
  • Safin Stéphane
  • Baker Michael J
  • Zhang Zhuoming
  • Alvina Jessalyn
  • Lecolinet Éric
  • Détienne Françoise
  Activités, Association Recherches et Pratiques sur les ACTivités, 2025, 22-1, pp.1-33. In this article, we study how the health safety rules relating to social touching, established during the pandemic, have been redefined with regard to interpersonal interactions. According to the adaptative safety framework, rules are theorised as resources, which are adapted in context. To better understand the processes for the re-elaboration of safety rules in interpersonal contexts, we conducted a study consisting of an online questionnaire on social touching habits before and after the lockdown, followed by in-depth interviews with selected participants. Our results highlight (1) reduced touching practices, especially for semi-intimate relationships such as colleagues, casual friends, close friends, and extended family; (2) two processes of re-elaborating pandemic-related safety rules: explicit deliberation, behavioural alignment, as well as reflexive processes; and (3) two dimensions of justifications given for the re-elaboration of those rules, preserving physical health/vulnerability concerns and maintaining social relations, and their relative weight according to the relationships (family versus friends) between the interactants. While recommended health and safety rules were mostly followed leading to large decrease in touching behaviours, it appears that people re-elaborate the rule depending on the relationship they share with one another. Through the re-elaboration of the official health and safety rules people strike a balance between safety measures in order to preserve their wellbeing and/or the relationship. (10.4000/13ra9)
  DOI : 10.4000/13ra9
• Why honor heroes? The emergence of extreme altruistic behavior as a by-product of praisers' self-promotion
  
  • Dessalles Jean-Louis
  Evolution and Human Behavior, Elsevier, 2025, 46 (1), pp.106656. Heroes are people who perform costly altruistic acts. Few people turn out to be heroes, but many spontaneously honor heroes by commenting, applauding, or enthusiastically celebrating their deeds. The existence of a praising audience leads individuals to compete to attract the crowd's admiration. The outcome is a winner-take-all situation in which only one or a few individuals engage in extreme altruistic behavior. The more difficult part is to explain the crowd's propensity to pay tribute from an individual fitness optimization perspective. The model proposed here shows how heroic behavior and its celebration by a large audience may emerge together. This situation is possible if admirers use public praise as a social signal to promote their own commitment to the values displayed by the hero. (10.1016/j.evolhumbehav.2025.106656)
  DOI : 10.1016/j.evolhumbehav.2025.106656
• White matter hyperintensities and their role in major depressive episodes: a cross-sectional study in adults under 65
  
  • Baudouin Édouard
  • Corruble Emmanuelle
  • Gori Pietro
  • Bloch Isabelle
  • Becquemont Laurent
  • Duron Emmanuelle
  • Colle Romain
  Brazilian Journal of Psychiatry, Brazilian Psychiatric Association, 2025.
• Joint despeckling and thermal noise compensation: application to Sentinel-1 images of the Arctic
  
  • Meraoumia Inès
  • Ratha Debanshu
  • Dalsasso Emanuele
  • Lohse Johannes
  • Tupin Florence
  • Marinoni Andrea
  • Denis Loïc
  IEEE Transactions on Geoscience and Remote Sensing, Institute of Electrical and Electronics Engineers, 2025, 63, pp.1-12. Synthetic Aperture Radar (SAR) images offer crucial information for studying and monitoring sea ice in the Arctic. Sentinel-1 captures images of the area using an extremely wide swath for reduced revisit time. The backscattered signal from sea ice and open water is often very weak, making it difficult to distinguish from the sensor thermal noise floor. Thermal noise impacts the images by generating a bias and increasing the fluctuations related to speckle phenomenon. Analyzing these images requires both correcting this bias and reducing fluctuations without blurring out the image content. The acquisition of several sub-swaths in a single pass using Terrain Observation with Progressive Scans (TOPS) produces images that exhibit, after compensation for antenna gains, a non-uniform thermal noise floor and strong discontinuities between sub-swaths. Denoising techniques must take these specificities into account to restore the images. This paper introduces a joint approach to remove the thermal noise offset and suppress fluctuations due to speckle and thermal noise. Compensating at once for all these effects largely reduces artifacts at the boundary between sub-swaths. We demonstrate using both numerical simulations and actual Sentinel-1 images that debiased polarimetric reflectivities can be recovered and fluctuations strongly reduced while preserving fine spatial structures. (10.1109/TGRS.2025.3610502)
  DOI : 10.1109/TGRS.2025.3610502
• Integrating Multi-Level Mixed-Criticality into MCTS for Robust Resource Management
  
  • Cordeiro Franco
  • Tardieu Samuel
  • Pautet Laurent
  Leibniz Transactions on Embedded Systems, European Design and Automation Association (EDAA) \ EMbedded Systems Special Interest Group (EMSIG) and Schloss Dagstuhl -- Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing., 2025, 2 (10), pp.Article No. 1, pp. 1:1–1:23. Managing actions with uncertain resource costs is a complex challenge, particularly in autonomous robot mission planning. Robots are often assigned multiple objectives with varying criticality levels, ranging from catastrophic to minor impacts, where failures can significantly affect system safety. Uncertainties in worst-case costs of resources, such as energy and operating time - the time it takes to carry out an action - further complicate mission planning and execution. Monte Carlo Tree Search (MCTS) is a powerful tool for online planning, yet it struggles to account for uncertainty in worst-case cost estimations. Optimistic estimates risk resource shortages, while pessimistic ones lead to inefficient allocation. The Mixed-Criticality (MC) approach, originally developed for real-time systems to schedule critical tasks by allocating processing resources under Worst-Case Execution Time (WCET) uncertainty, provides a framework of rules, models and design principles. We claim this framework can be adapted to autonomous robot mission planning, where critical objectives are met through analogous allocation of different kinds of resources such as energy and operating time despite uncertainties. We propose enhancing MCTS with MC principles to handle uncertainty in worst-case costs across multiple resources and criticality of objectives. High-critical objectives must always be completed, regardless of resource constraints, while low-critical objectives operate flexibly, consuming resources within optimistic estimates when possible or being discarded when resources become scarce. This ensures efficient resource reallocation and prioritization of high-critical objectives. To implement this, we present (MC)²TS, a novel variant of MCTS that integrates MC principles for dynamic resource management. It supports more than two criticality levels to ensure that the most critical components meet the most stringent safety and reliability requirements, while also enabling robust resource management. By enabling replanning and mode changes, (MC)²TS improves MCTS’s efficiency and enhances MC systems’ adaptability to both degrading and improving resource conditions. We evaluate (MC)²TS in an active perception scenario, where a drone retrieves data from distributed sensors under unpredictable environmental conditions. (MC)²TS outperforms MCTS by achieving more objectives, adapting plans when costs drop. It explores more objective sequences, minimizes oversizing, and enhances efficiency. Balancing safety and performance, it monitors robot battery, mission and objective resource constraints such as deadlines. Its robustness ensures low-critical objectives do not compromise high-critical objectives, making it a reliable solution for complex systems characterized by uncertain resource costs and critical objectives. (10.4230/LITES.10.2.1)
  DOI : 10.4230/LITES.10.2.1
• Certifying and learning quantum Ising Hamiltonians
  
  • Bluhm Andreas
  • Caro Matthias
  • Gutiérrez Francisco Escudero
  • Oufkir Aadil
  • Rouzé Cambyse
  , 2025. In this work, we study the problems of certifying and learning quantum Ising Hamiltonians. Our main contributions are as follows: Certification of Ising Hamiltonians. We show that certifying an Ising Hamiltonian in normalized Frobenius norm via access to its time-evolution operator requires only $\widetilde O(1/\varepsilon)$ time evolution. This matches the Heisenberg-scaling lower bound of $Ω(1/\varepsilon)$ up to logarithmic factors. To our knowledge, this is the first nearly-optimal algorithm for testing a Hamiltonian property. A key ingredient in our analysis is the Bonami Lemma from Fourier analysis. Learning Ising Gibbs states. We design an algorithm for learning Ising Gibbs states in trace norm that is sample-efficient in all parameters. In contrast, previous approaches learned the underlying Hamiltonian (which implies learning the Gibbs state) but suffered from exponential sample complexity in the inverse temperature. Certification of Ising Gibbs states. We give an algorithm for certifying Ising Gibbs states in trace norm that is both sample and time-efficient, thereby solving a question posed by Anshu (Harvard Data Science Review, 2022). Finally, we extend our results on learning and certification of Gibbs states to general $k$-local Hamiltonians for any constant $k$.
• Learning and certification of local time-dependent quantum dynamics and noise
  
  • França Daniel Stilck
  • Möbus Tim
  • Rouzé Cambyse
  • Werner Albert
  , 2025. Hamiltonian learning protocols are essential tools to benchmark quantum computers and simulators. Yet rigorous methods for time-dependent Hamiltonians and Lindbladians remain scarce despite their wide use. We close this gap by learning the time-dependent evolution of a locally interacting $n$-qubit system on a graph of effective dimension $D$ using only preparation of product Pauli eigenstates, evolution under the time-dependent generator for given times, and measurements in product Pauli bases. We assume the time-dependent parameters are well approximated by functions in a known space of dimension $m$ admitting stable interpolation, e.g. by polynomials. Our protocol outputs functions approximating these coefficients to accuracy $ε$ on an interval with success probability $1-δ$, requiring only $O\big(ε^{-2}poly(m)\log(nδ^{-1})\big)$ samples and $poly(n,m)$ pre/postprocessing. Importantly, the scaling in $m$ is polynomial, whereas naive extensions of previous methods scale exponentially. The method estimates time derivatives of observable expectations via interpolation, yielding well-conditioned linear systems for the generator's coefficients. The main difficulty in the time-dependent setting is to evaluate these coefficients at finite times while preserving a controlled link between derivatives and dynamical parameters. Our innovation is to combine Lieb-Robinson bounds, process shadows, and semidefinite programs to recover the coefficients efficiently at constant times. Along the way, we extend state-of-the-art Lieb-Robinson bounds on general graphs to time-dependent, dissipative dynamics, a contribution of independent interest. These results provide a scalable tool to verify state-preparation procedures (e.g. adiabatic protocols) and characterize time-dependent noise in quantum devices.
• Invertibility of functionals of the Poisson process and applications
  
  • Coutin Laure
  • Decreusefond Laurent
  The Annals of Probability, Institute of Mathematical Statistics, 2025, 53 (5). Following previous investigations by Üstünel [22] about the invertibility of some transformations on the Wiener space, we find some entropic conditions under which a random change of time is invertible on the Poisson space. As a consequence, we provide a new construction of Hawkes processes. We also establish a new variational representation of the entropy. (10.1214/24-AOP1748)
  DOI : 10.1214/24-AOP1748
• POT Python Optimal Transport
  
  • Flamary Rémi
  • Vincent-Cuaz Cédric
  • Courty Nicolas
  • Gramfort Alexandre
  • Kachaiev Oleksii
  • Quang Tran Huy
  • David Laurène
  • Bonet Clément
  • Cassereau Nathan
  • Gnassounou Theo
  • Tanguy Eloi
  • Delon Julie
  • Collas Antoine
  • Mazelet Sonia
  • Chapel Laetitia
  • Kerdoncuff Tanguy
  • Yu Xizheng
  • Feickert Matthew
  • Krzakala Paul
  • Liu Tianlin
  • Fernandes Montesuma Eduardo
  , 2025. (10.5281/ZENODO.17161062)
  DOI : 10.5281/ZENODO.17161062
• Functional analysis of multivariate max-stable distributions
  
  • Costacèque-Cecchi Bruno
  • Decreusefond Laurent
  , 2025. <div><p>We study the connections existing between max-infinitely divisible distributions and Poisson processes from the point of view of functional analysis. More precisely, we derive functional identities for the former by using well-known results of Poisson stochastic analysis. We also introduce a family of Markov semigroups whose stationary measures are the so-called multivariate max-stable distributions. Their generators thus provide a functional characterization of extreme valued distributions in any dimension. Additionally, we give a few functional identities associated to those semi-groups, namely a Poincaré identity and commutation relations. Finally, we present a stochastic process whose semigroup corresponds to the one we introduced and that can be expressed using extremal stochastic integrals.</p></div>
• Small Yet Configurable: Unveiling Null Variability in Software
  
  • Tërnava Xhevahire
  • Randrianaina Georges Aaron
  • Lesoil Luc
  • Acher Mathieu
  , 2025. Many small-scale software systems, that is, with limited codebase or binary size, are widely used in everyday tasks, yet their configurability remains largely unexplored. At the same time, studies on modern software systems show a trend toward increasing configurability, alongside growing interest in building immutable, specialized, and reproducible software. In this paper, we present the first empirical study on the extent of configurability in small-scale software systems. By analyzing 108 programs from GNU coreutils, we show that even small programs can exhibit significant compile-time and run-time variability, with up to 76 options per program. Then, there is a high correlation (0.78) between run-time variability and codebase size. Furthermore, an analysis of the 20 smallest programs across 85 releases reveals that variability tends to increase over time, primarily due to the added compile-time variability. This suggests that shifting options between run-time and compile-time, removing unnecessary run-time variability, or resolving compile-time variability early, can help reduce codebase complexity and size. We also introduce, for the first time, the concept of null-variable software system, one with no configurability beyond mandatory features. Our findings show that high configurability is not exclusive to largescale systems and that reducing unnecessary variability can lead to lightweight, smaller, and more maintainable software. We hope this effort contributes to designing new software by understanding how to balance its configurability with codebase size.
• Resilience for Regular Path Queries: Towards a Complexity Classification
  
  • Amarilli Antoine
  • Gatterbauer Wolfgang
  • Makhija Neha
  • Monet Mikaël
  Proceedings of the ACM on Management of Data, ACM, 2025, 3 (2), pp.1-18. The resilience problem for a query and an input set or bag database is to compute the minimum number of facts to remove from the database to make the query false. In this paper, we study how to compute the resilience of Regular Path Queries (RPQs) over graph databases. Our goal is to characterize the regular languages $L$ for which it is tractable to compute the resilience of the existentially-quantified RPQ built from $L$. We show that computing the resilience in this sense is tractable (even in combined complexity) for all RPQs defined from so-called local languages. By contrast, we show hardness in data complexity for RPQs defined from the following language classes (after reducing the languages to eliminate redundant words): all finite languages featuring a word containing a repeated letter, and all languages featuring a specific kind of counterexample to being local (which we call four-legged languages). The latter include in particular all languages that are not star-free. Our results also imply hardness for all non-local languages with a so-called neutral letter. We also highlight some remaining obstacles towards a full dichotomy. In particular, for the RPQ $abc|be$, resilience is tractable but the only PTIME algorithm that we know uses submodular function optimization. (10.1145/3725245)
  DOI : 10.1145/3725245
• On regression in extreme regions
  
  • Clémençon Stéphan
  • Huet Nathan
  • Sabourin Anne
  Electronic Journal of Statistics, Shaker Heights, OH : Institute of Mathematical Statistics, 2025, 19 (2), pp.4784–4828. We establish a statistical learning theoretical framework aimed at extrapolation, or out-of-domain generalization, on the unobserved tails of covariates in continuous regression problems. Our strategy involves performing statistical regression on a subsample of observations with continuous labels that are the furthest away from the origin, focusing specifically on their angular components. The underlying assumptions of our approach are grounded in the theory of multivariate regular variation, a cornerstone of extreme value theory. We address the stylized problem of nonparametric least squares regression with predictors chosen from a Vapnik-Chervonenkis class.This work contributes to a broader initiative to develop statistical learning theoretical foundations for supervised learning strategies that enhance performance on the supposedly heavy tails of covariates. Previous efforts in this area have focused exclusively on binary classification on extreme covariates. Although the continuous target setting necessitates different techniques and regularity assumptions, our main results echo findings from earlier studies. We quantify the predictive performance on tail regions in terms of excess risk, presenting it as a finite sample risk bound with a clear bias-variance decomposition. Numerical experiments with simulated and real data illustrate our theoretical findings. (10.1214/25-EJS2441)
  DOI : 10.1214/25-EJS2441
• Device Independent Quantum Key Activation
  
  • Ulu Bora
  • Brunner Nicolas
  • Weilenmann Mirjam
  Physical Review Letters, American Physical Society, 2025, 135 (19), pp.190801. Device-independent quantum key distribution (DIQKD) allows two distant parties to establish a secret key, based only on the observed Bell nonlocal distribution. It remains however, unclear what the minimal resources for enabling DIQKD are and how to maximize the key rate from a given distribution. In the present work, we consider a scenario where several copies of a given quantum distribution are jointly processed via a local and classical wiring operation. We find that, under few assumptions, it is possible to activate device-independent key. That is, starting from a distribution that is useless in a DIQKD protocol, we obtain a positive key rate by wiring several copies together. We coin this effect device-independent key activation. Our analysis focuses on the standard DIQKD protocol with one-way post-processing, and we resort to semi-definite programming techniques for computing lower bounds on the key rate. (10.1103/f8jc-q1kg)
  DOI : 10.1103/f8jc-q1kg
• Complexity of mixed Schatten norms of quantum maps
  
  • Kochanowski Jan
  • Fawzi Omar
  • Rouzé Cambyse
  , 2025. We study the complexity of computing the mixed Schatten $\|Φ\|_{q\to p}$ norms of linear maps $Φ$ between matrix spaces. When $Φ$ is completely positive, we show that $\| Φ\|_{q \to p}$ can be computed efficiently when $q \geq p$. The regime $q \geq p$ is known as the non-hypercontractive regime and is also known to be easy for the mixed vector norms $\ell_{q} \to \ell_{p}$ [Boyd, 1974]. However, even for entanglement-breaking completely-positive trace-preserving maps $Φ$, we show that computing $\| Φ\|_{1 \to p}$ is $\mathsf{NP}$-complete when $p&gt;1$. Moving beyond the completely-positive case and considering $Φ$ to be difference of entanglement breaking completely-positive trace-preserving maps, we prove that computing $\| Φ\|^+_{1 \to 1}$ is $\mathsf{NP}$-complete. In contrast, for the completely-bounded (cb) case, we describe a polynomial-time algorithm to compute $\|Φ\|_{cb,1\to p}$ and $\|Φ\|^+_{cb,1\to p}$ for any linear map $Φ$ and $p\geq1$.