HAL-ENS-LYON
Not a member yet
104280 research outputs found
Sort by
On the complexity of the Maker-Breaker happy vertex game
No full textGiven a c-colored graph G, a vertex of G is happy if it has the same color as all its neighbors. The notion of happy vertices was introduced by Zhang and Li to compute the homophily of a graph. Eto, et al. introduced the Maker-Maker version of the Happy vertex game, where two players compete to claim more happy vertices than their opponent. We introduce here the Maker-Breaker happy vertex game: two players, Maker and Breaker, alternately color the vertices of a graph with their respective colors. Maker aims to maximize the number of happy vertices at the end, while Breaker aims to prevent her. This game is also a scoring version of the Maker-Breaker Domination game introduced by Duchene, et al. as a happy vertex corresponds exactly to a vertex that is not dominated in the domination game. Therefore, this game is a very natural game on graphs and can be studied within the scope of scoring positional games. We initiate here the complexity study of this game, by proving that computing its score is PSPACE-complete on trees, NP-hard on caterpillars, and polynomial on subdivided stars. Finally, we provide the exact value of the score on graphs of maximum degree 2, and we provide an FPT-algorithm to compute the score on graphs of bounded neighborhood diversity. An important contribution of the paper is that, to achieve our hardness results, we introduce a new type of incidence graph called the literal-clause incidence graph for 2-SAT formulas. We prove that QMAX 2-SAT remains PSPACE-complete even if this graph is acyclic, and that MAX 2-SAT remains NP-complete, even if this graph is acyclic and has maximum degree 2, i.e. is a union of paths. We demonstrate the importance of this contribution by proving that Incidence, the scoring positional game played on a graph is also PSPACE-complete when restricted to forests
The Generation Phases of Flow Matching: a Denoising Perspective
No full textFlow matching has achieved remarkable success, yet the factors influencing the quality of its generation process remain poorly understood. In this work, we adopt a denoising perspective and design a framework to empirically probe the generation process. Laying down the formal connections between flow matching models and denoisers, we provide a common ground to compare their performances on generation and denoising. This enables the design of principled and controlled perturbations to influence sample generation: noise and drift. This leads to new insights on the distinct dynamical phases of the generative process, enabling us to precisely characterize at which stage of the generative process denoisers succeed or fail and why this matters
BiblIndex Beyond Canonical References: Using AI to Map Biblical Text Reuses in Patristic Literature
No full textInternational audienceBiblIndex, the online index of biblical text reuses in Early Christian literature, faces three challenges that artificial intelligence could address: the extensive intrabiblical intertextuality requiring many-to-many relationship mapping; the precise delineation of textual reuses beyond canonical verse systems; and establishing a robust typology distinguishing verbatim quotations from distant allusions. Neural language models could identify semantic similarities beyond exact wording, sequence tagging architectures could detect quotation boundaries at character-level precision, and machine learning classifiers could systematically categorize reuse types based on measurable linguistic features. Rather than replacing scholarly expertise, AI would augment human capabilities by processing hundreds of thousands of quotations at scale while maintaining philological rigor, transforming BiblIndex into a dynamic research environment that enables both comprehensive mapping and in-depth study of the textual relationships shaping Christian intellectual history
The LISA Astrophysics "Disc-IMRI" Code Comparison Project: Intermediate-Mass-Ratio Binaries in AGN-Like Discs
No full textInternational audienceUpcoming space-based gravitational wave detectors such as LISA, the Laser Interferometer Space Antenna, will be sensitive to extreme- and intermediate-mass-ratio inspirals (EMRIs and IMRIs). These binaries are comprised of a supermassive black hole and a stellar-mass object or intermediate-mass black hole. Their detection will probe the structure of galactic nuclei and enable tests of general relativity. As these events will be observed over thousands of orbital cycles, they will be extremely sensitive to both the underlying spacetime and astrophysical environment, demanding exquisite theoretical models on both fronts to avoid biased or even erroneous results. In particular, many (E/)IMRIs are expected to occur within accretion discs around supermassive black holes, and the nonlinearities present when modeling these systems require numerical simulations. In preparation for future modeling of LISA sources, we have conducted a comparison between eight different hydrodynamical codes and applied them to the problem of a q = 10^{-4} mass ratio binary interacting with an accretion disc. Thicker discs appear more lenient, and all codes at sufficiently high resolutions are in good agreement with each other and analytical predictions. For thinner discs, beyond the reach of analytical models, we find substantial disagreement between 2D and 3D simulations and between different codes, including both the magnitude and sign of the torque. With time and energy efficiency in mind, codes that leverage moving meshes or grid-based Lagrangian remapping seem preferable, as do codes that can leverage graphical processing units and other energy-efficient hardware
SpeckSeq enables high-throughput functional stratification of MEFV variants in autoinflammatory diseases
No full textInternational audienceVariants of uncertain significance (VUS) are a major obstacle in genetic diagnosis, particularly when involving gain-of-function (GoF) mutations that are poorly predicted in silico. MEFV, which encodes the inflammasome sensor pyrin, is mutated in two autoinflammatory diseases, familial Mediterranean fever (FMF) and pyrin-associated autoinflammation with neutrophilic dermatosis (PAAND). Here, we developed SpeckSeq, a method that combines DNA bar-coding, ASC speck–based single-cell sorting and next-generation sequencing to systematically identify hypermorphic MEFV variants in response to different stimuli. SpeckSeq identified 49 GoF mutations separated into two distinct groups containing either PAAND variants or FMF variants. SpeckSeq was validated using patients’ cells and supported a reclassification of MEFV variant pathogenicity, leading to novel diagnoses. As a large-scale mutagenesis approach, using human genetics as a guide, SpeckSeq revealed structural and functional pyrin features, including a putative ligand-accommodating cavity in the B30.2 domain. Altogether, SpeckSeq classifies VUS to refine molecular diagnostics and improve our knowledge on the pyrin inflammasome
Acceleration of implicit schemes for large systems of delay differential equations
No full textInternational audienceThe objective is to accelerate numerical implicit schemes for solving large linear or nonlinear delay differential equations. These schemes require solving large linear or nonlinear systems at each integration step, making effective initial guesses critical for rapid convergence. For nonlinear problems, an inexact Newton method is used, whose efficiency depends heavily on the quality of these initial guesses. To generate them, line search or trust-region algorithms are employed -each involving the solution of large linear systems. These linear systems are solved using a Krylov subspace method. Initial guesses are constructed via a Petrov-Galerkin process applied to low-dimensional approximation subspaces derived from previous steps. Error estimates are provided, linking the accuracy of the initial guesses to the timestep size, the scheme's order, and the subspace dimension. Numerical experiments show speedups of up to two orders of magnitude over standard predictor-based methods, when those converge
Exact Minimum Cuts in Hypergraphs at Scale
No full textInternational audienceThe hypergraph minimum cut problem aims to partition the vertices of a hypergraph into two non-empty parts while minimizing the total weight of hyperedges crossing the cut. This problem lies at the core of many tasks in network reliability, VLSI placement, and community detection. We introduce HeiCut, the first algorithm that makes exact minimum cut computation feasible for both weighted and unweighted instances at scales of hundreds of millions of vertices. HeiCut presents seven exact reduction rules that provably preserve the minimum cut, and an optional heuristic contraction based on label propagation that shrinks complex and persistent structures. When no further reductions are possible, the remaining in stance is solved exactly with a known algorithm. Our extensive evaluation on more than 500 real-world hypergraphs reveals that the exact reductions alone already expose the minimum cut (i.e., the residual collapses to a single vertex or has no hyperedges) in over 85% of instances. Across all instances, HeiCut solves over twice as many instances as the state-of-the-art within set computational limits, and is up to five orders of magnitude faster. Thus, HeiCut significantly advances hyper graph minimum cut computation in real-world, large-scale scenarios
