INRIA a CCSD electronic archive server
Not a member yet
122212 research outputs found
Sort by
Toughness Properties of Arbitrarily Partitionable Graphs
No full textInternational audienceDrawing inspiration from a well-known conjecture of Chv\'atal on a toughness threshold guaranteeing graph Hamiltonicity, we investigate toughness properties of so-called arbitrarily partitionable (AP) graphs, which are those graphs that can be partitioned into arbitrarily many connected graphs with arbitrary orders, and can be perceived as a weakening of Hamiltonian and traceable graphs. In particular, we provide constructions of non-AP graphs with toughness about , \textit{i.e.}, in which, when removing the vertices of any cut-set , the number of resulting connected components is at most about . We also consider side related questions on graphs that can be partitioned arbitrarily into only a few connected graphs (with arbitrary orders). Among other things, we prove that not all -tough graphs can always be partitioned into four connected graphs this way. As going along, we also raise several other questions and problems of interest on the topic
Yggdrasil: An Artifact-Based Framework for Hypermedia Multi-Agent Systems
No full textInternational audienceRecent years have brought renewed interest in Web-based Multi-agent Systems (MAS), primarily motivated by progress in the Web of Things, Distributed Knowledge Graphs, and Generative AI. Central to these developments is the flexible, autonomous use of hypermedia—for example, to discover knowledge, invoke device functionality, or use tools. However, existing frameworks for Web-based MAS typically lack support for working with hypermedia abstractions and controls. To fill this gap, this chapter presents a model and framework for hypermedia-based MAS. Our specific focus is on the environment as a first-class abstraction in MAS: agents are situated and embodied in a distributed hypermedia environment that (i) provides them with a uniform abstraction of the system and (ii) is instrumented with tools and resources they can discover and use to achieve their goals. Given a single entry point into the hypermedia environment, agents are enabled to “arrive-and-operate”: they use their prior knowledge and experience to achieve their goals by browsing hypermedia and exploiting action possibilities discovered at run time—mimicking how humans are supported by well-designed hypermedia environments today. We illustrate our approach through a demonstrator and discuss its benefits and drawbacks against an equivalent implementation without hypermedia
Diffusion-based Frameworks for Unsupervised Speech Enhancement
No full textThis paper addresses unsupervised diffusion-based single-channel speech enhancement (SE). Prior work in this direction combines a score-based diffusion model trained on clean speech with a Gaussian noise model whose covariance is structured by non-negative matrix factorization (NMF). This combination is used within an iterative expectation–maximization (EM) scheme, in which a diffusion-based posterior-sampling E-step estimates the clean speech. We first revisit this framework and propose to explicitly model both speech and acoustic noise as latent variables, jointly sampling them in the E-step instead of sampling speech alone as in previous approaches. We then introduce a new unsupervised SE framework that replaces the NMF noise prior with a diffusion-based noise model, learned jointly with the speech prior in a single conditional score model. Within this framework, we derive two variants: one that implicitly accounts for noise and one that explicitly treats noise as a latent variable. Experiments on WSJ0–QUT and VoiceBank–DEMAND show that explicit noise modeling systematically improves SE performance for both NMF-based and diffusion-based noise priors. Under matched conditions, the diffusion-based noise model attains the best overall quality and intelligibility among unsupervised methods, while under mismatched conditions the proposed NMF-based explicit-noise framework is more robust and suffers less degradation than several supervised baselines. Our code will be publicly available at https://github.com/jeaneudesAyilo/enudiffuse
Illustrator's Depth: Monocular Layer Index Prediction for Image Decomposition
No full textWe introduce Illustrator's Depth, a novel definition of depth that addresses a key challenge in digital content creation: decomposing flat images into editable, ordered layers. Inspired by an artist's compositional process, illustrator's depth infers a layer index to each pixel, forming an interpretable image decomposition through a discrete, globally consistent ordering of elements optimized for editability. We also propose and train a neural network using a curated dataset of layered vector graphics to predict layering directly from raster inputs. Our layer index inference unlocks a range of powerful downstream applications. In particular, it significantly outperforms state-of-the-art baselines for image vectorization while also enabling high-fidelity text-to-vector-graphics generation, automatic 3D relief generation from 2D images, and intuitive depth-aware editing. By reframing depth from a physical quantity to a creative abstraction, illustrator's depth prediction offers a new foundation for editable image decomposition
Geometric theory of constrained Schrödinger dynamics with application to time-dependent density-functional theory on a finite lattice
No full textTime-dependent density-functional theory (TDDFT) is a central tool for studying the dynamical electronic structure of molecules and solids, yet aspects of its mathematical foundations remain insufficiently understood. In this work, we revisit the foundations of TDDFT within a finite-dimensional setting by developing a general geometric framework for Schrödinger dynamics subject to prescribed expectation values of selected observables. We show that multiple natural definitions of such constrained dynamics arise from the underlying geometry of the state manifold. The conventional TDDFT formulation emerges from demanding stationarity of the action functional, while an alternative, purely geometric construction leads to a distinct form of constrained Schrödinger evolution that has not been previously explored. This alternative dynamics may provide a more mathematically robust route to TDDFT and may suggest new strategies for constructing nonadiabatic approximations. Applying the theory to interacting fermions on finite lattices, we derive novel Kohn--Sham schemes in which the density constraint is enforced via an imaginary potential or, equivalently, a nonlocal Hermitian operator. Numerical illustrations for the Hubbard dimer demonstrate the behavior of these new approaches
Leveraging Cryptographic Simulator Synthesis for Formally Verifying the FOO E-Voting Protocol
No full textInternational audienceCryptographic proofs proceed in large part by reductions to cryptographic assumptions expressed as games. These reductions rely on simulators which are often tedious to write and involve a significant amount of trivial code. Thus, simulators are only sketched in pen-and-paper proofs, which is error-prone. Mechanized cryptographic proofs remove the risk of errors, but requiring users to explicitly write simulators is an unreasonable burden.In this paper, we consider the problem of simulator synthesis in Squirrel, where cryptographic simulation is expressed as bi-deduction. Although the seminal work on bi-deduction provides a proof system and a simple proof-search procedure for it, we show that it suffers from systematic failures when working with games such as IND-CCA2. We provide a significantly improved procedure, that can re-use oracle calls across recursive iterations, and generates precise invariants to justify it. We implement this procedure in Squirrel and validate it in a proof of ballot privacy for the FOO e-voting protocol, which is the first computational mechanized proof for FOO, and the most complex Squirrel proof to date
Mind the Brain Age: How Segmentation and Template Selection Reshape Structural Connectomes
No full textDiffusion-weighted MRI samples the directional diffusion of water in vivo, and tractography uses this information to reconstruct brain fiber pathways. Mapping streamlines to an anatomical parcellation yields structural connectomes. However, in older adults, where white matter alterations and atrophy are common, the choice of reference template and tissue segmentation could be particularly consequential for obtaining accurate, interpretable structural connectomes. Using a conventional pipeline, we evaluated how these two factors, the normalization template and the segmentation used to constrain anatomically guided tractography, affect connectome estimates in cognitively healthy elderly participants. These methodological choices produced systematic and significant differences in network topology and their relationships with clinically relevant variables across standard connectome measures, particularly in patients with white matter hyperintensities. Age-appropriate normalization and lesion-aware anatomically constrained tractography yielded networks with more plausible anatomy and more consistent relationships with cognition and imaging measures, whereas unconstrained tracking inflated density without improving interpretability. These findings demonstrate that structural connectome outcomes are contingent upon templateand segmentation selection. We therefore advocate for explicit reporting of these methodological parameters and recommend the use of age-appropriate templates combined with white matter lesion-aware segmentation incorporating anatomically informed constraints
Metric analysis for spatial semantic segmentation of sound scenes
No full textInternational audienceSpatial semantic segmentation of sound scenes (S5) consists of jointly performing audio source separation and sound event classification from a multichannel audio mixture. To evaluate S5 systems, one can consider two individual metrics, i.e., one for source separation and another for sound event classification, but this approach makes it challenging to compare S5 systems. Thus, a joint classaware signal-to-distortion ratio (CA-SDR) metric was proposed to evaluate S5 systems. In this work, we first compare the CA-SDR with the classical SDR on scenarios with only classification errors.We then analyze the cases where the metric might not allow proper comparison of the systems. To address this problem, we propose a modified version of the CA-SDR which first focuses on classagnostic SDR and then accounts for the wrongly labeled sources.We also analyze the performance of the two metrics under crosscontamination between separated audio sources. Finally, we propose a first set of penalties in an attempt to make the metric more reflective of the labeling and separation errors.5 pages; content+bibliograph
Gaussian entropic optimal transport: Schrödinger bridges and the Sinkhorn algorithm
No full textEntropic optimal transport problems are regularized versions of optimal transport problems. These models play an increasingly important role in machine learning and generative modelling. For finite spaces, these problems are commonly solved using Sinkhorn algorithm (a.k.a. iterative proportional fitting procedure). However, in more general settings the Sinkhorn iterations are based on nonlinear conditional/conjugate transformations and exact finite-dimensional solutions cannot be computed. This article presents a finite-dimensional recursive formulation of the iterative proportional fitting procedure for general Gaussian multivariate models. As expected, this recursive formulation is closely related to the celebrated Kalman filter and related Riccati matrix difference equations, and it yields algorithms that can be implemented in practical settings without further approximations. We extend this filtering methodology to develop a refined and self-contained convergence analysis of Gaussian Sinkhorn algorithms, including closed form expressions of entropic transport maps and Schrödinger bridges