HAL-Polytechnique
Not a member yet
51406 research outputs found
Sort by
Toward Numerically Exact Computation of Conductivity in the Thermodynamic Limit of Interacting Lattice Models
No full text5 pages, 3 figures + supplemental material, 13 pages, 16 figuresInternational audienc
Brochette first-passage percolation
No full textWe investigate a novel first-passage percolation model, referred to as the Brochette first-passage percolation model, where the passage times associated with edges lying on the same line are equal. First, we establish a point-to-point convergence theorem, identifying the time constant. In particular, we explore the case where the time constant vanishes and demonstrate the existence of a wide range of possible behaviours. Next, we prove a shape theorem, showing that the limiting shape is the diamond. Finally, we extend the analysis by proving a point-to-point convergence theorem in the setting where passage times are allowed to be infinite
Decoding rank metric Reed-Muller codes
No full textInternational audienceIn this article, we investigate the decoding of the rank metric Reed--Muller codes introduced by Augot, Couvreur, Lavauzelle and Neri in 2021. We propose a polynomial time algorithm that rests on the structure of Dickson matrices, works on any such code and corrects up to half the minimum distance
Refined Analysis of Federated Averaging's Bias and Federated Richardson-Romberg Extrapolation
No full textInternational audienceIn this paper, we present a novel analysis of FedAvg with constant step size, relying on the Markov property of the underlying process. We demonstrate that the global iterates of the algorithm converge to a stationary distribution and analyze its resulting bias and variance relative to the problem's solution. We provide a first-order bias expansion in both homogeneous and heterogeneous settings. Interestingly, this bias decomposes into two distinct components: one that depends solely on stochastic gradient noise and another on client heterogeneity. Finally, we introduce a new algorithm based on the Richardson-Romberg extrapolation technique to mitigate this bias
Universal complexity bounds based on value iteration for stochastic mean payoff games and entropy games
No full textInternational audienceWe develop value iteration-based algorithms to solve in a unified manner different classes of combinatorial zero-sum games with mean-payoff type rewards. These algorithms rely on an oracle, evaluating the dynamic programming operator up to a given precision. We show that the number of calls to the oracle needed to determine exact optimal (positional) strategies is, up to a factor polynomial in the dimension, of order R/sep, where the “separation” sep is defined as the minimal difference between distinct values arising from strategies, and R is a metric estimate, involving the norm of approximate sub and super-eigenvectors of the dynamic programming operator. We illustrate this method by two applications. The first one is a new proof, leading to improved complexity estimates, of a theorem of Boros, Elbassioni, Gurvich and Makino, showing that turn-based mean-payoff games with a fixed number of random positions can be solved in pseudo-polynomial time. The second one concerns entropy games, a model introduced by Asarin, Cervelle, Degorre, Dima, Horn and Kozyakin. The rank of an entropy game is defined as the maximal rank among all the ambiguity matrices determined by strategies of the two players. We show that entropy games with a fixed rank, in their original formulation, can be solved in polynomial time, and that an extension of entropy games incorporating weights can be solved in pseudo-polynomial time under the same fixed rank condition
Stationary regimes of piecewise linear dynamical systems with priorities
No full textInternational audienceDynamical systems governed by priority rules appear in the modeling of emergency organizations and road traffic. These systems can be modeled by piecewise linear time-delay dynamics, specifically using Petri nets with priority rules. A central question is to show the existence of stationary regimes (i.e., steady state solutions) -- taking the form of invariant half-lines -- from which essential performance indicators like the throughput and congestion phases can be derived. Our primary result proves the existence of stationary solutions under structural conditions involving the spectrum of the linear parts within the piecewise linear dynamics. This extends to a broader class of systems a fundamental theorem of Kohlberg (1980) dealing with nonexpansive dynamics. The proof of our result relies on topological degree theory and the notion of ``Blackwell optimality'' from the theory of Markov decision processes. Finally, we validate our findings by demonstrating that these structural conditions hold for a wide range of dynamics, especially those stemming from Petri nets with priority rules. This is illustrated on real-world examples from road traffic management and emergency call center operations
Signed Barcodes for Multi-parameter Persistence via Rank Decompositions and Rank-Exact Resolutions
No full textInternational audienceAbstract In this paper, we introduce the signed barcode, a new visual representation of the global structure of the rank invariant of a multi-parameter persistence module or, more generally, of a poset representation. Like its unsigned counterpart in one-parameter persistence, the signed barcode decomposes the rank invariant as a -linear combination of rank invariants of indicator modules supported on segments in the poset. We develop the theory behind these decompositions, both for the usual rank invariant and for its generalizations, showing under what conditions they exist and are unique. We also show that, like its unsigned counterpart, the signed barcode reflects in part the algebraic structure of the module: specifically, it derives from the terms in the minimal rank-exact resolution of the module, i.e., its minimal projective resolution relative to the class of short exact sequences on which the rank invariant is additive. To complete the picture, we show some experimental results that illustrate the contribution of the signed barcode in the exploration of multi-parameter persistence modules
Uncertainty quantification in Bayesian inverse problems with neutron and gamma time correlation measurements
No full textInternational audienceNeutron noise analysis is a predominant technique for fissile matter identification with passive methods. Quantifying the uncertainties associated with the estimated nuclear parameters is crucial for decision-making. A conservative uncertainty quantification procedure is possible by solving a Bayesian inverse problem with the help of statistical surrogate models but generally leads to large uncertainties due to the surrogate models’ errors. In this work, we develop two methods for robust uncertainty quantification in neutron and gamma noise analysis based on the resolution of Bayesian inverse problems. We show that the uncertainties can be reduced by including information on gamma correlations. The investigation of a joint analysis of the neutron and gamma observations is also conducted with the help of active learning strategies to fine-tune surrogate models. We test our methods on a model of the SILENE reactor core, using simulated and real-world measurements
Measurement of asymmetries in decays
No full textInternational audienceA search for violation in and decays is presented using the full Run 1 and Run 2 data samples of collisions collected with the LHCb detector, corresponding to an integrated luminosity of 9 at center-of-mass energies of 7, 8, and 13 TeV. For the Run 2 data sample, the -violating asymmetries are measured to be and , where the first uncertainty is statistical and the second is systematic. Following significant improvements in the evaluation of systematic uncertainties compared to the previous LHCb measurement, the Run 1 dataset is reanalyzed to update the corresponding results. When combining the Run 2 and updated Run 1 measurements, the final results are found to be and , constituting the most precise measurements of these asymmetries to date
On the approximation of the von Neumann equation in the semi-classical limit. Part I : numerical algorithm
No full textInternational audienceWe propose a new approach to discretize the von Neumann equation, which is efficient in the semi-classical limit. This method is first based on the so called Weyl’s variables to address the stiffness associated with the equation. Then, by applying a truncated Hermite expansion of the density operator, we successfully handle this stiffness. Additionally, we develop a finite volume approximation for practical implementation and conduct numerical simulations to illustrate the efficiency of our approach. This asymptotic preserving numerical approximation, combined with the use of Hermite polynomials, provides an efficient tool for solving the von Neumann equation in all regimes, near classical or not