25353 research outputs found
Sort by
Approximating Queries on Probabilistic Graphs
No full text29 pages. Extended version of the ICDT'24 articleInternational audienceQuery evaluation over probabilistic databases is notoriously intractable -- not only in combined complexity, but often in data complexity as well. This motivates the study of approximation algorithms, and particularly of combined FPRASes, with runtime polynomial in both the query and instance size. In this paper, we focus on tuple-independent probabilistic databases over binary signatures, i.e., probabilistic graphs, and study when we can devise combined FPRASes for probabilistic query evaluation. We settle the complexity of this problem for a variety of query and instance classes, by proving both approximability results and (conditional) inapproximability results doubled with (unconditional) DNNF provenance circuit size lower bounds. This allows us to deduce many corollaries of possible independent interest. For example, we show how the results of Arenas et al. on counting fixed-length strings accepted by an NFA imply the existence of an FPRAS for the two-terminal network reliability problem on directed acyclic graphs: this was an open problem until now. We also show that one cannot extend a recent result of van Bremen and Meel that gives a combined FPRAS for self-join-free conjunctive queries of bounded hypertree width on probabilistic databases: neither the bounded-hypertree-width condition nor the self-join-freeness hypothesis can be relaxed. We last show how our methods can give insights on the evaluation and approximability of regular path queries (RPQs) on probabilistic graphs in the data complexity perspective, showing in particular that some of them are (conditionally) inapproximable
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
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
Finite Element Neural Network Interpolation. Part I: Interpretable and Adaptive Discretization for Solving PDEs
No full textInternational audienceWe present the Finite Element Neural Network Interpolation (FENNI) framework, a sparse neural network architecture extending previous work on Embedded Finite Element Neural Networks (EFENN) introduced with the Hierarchical Deep-learning Neural Networks (HiDeNN). Due to their mesh-based structure, EFENN requires significantly fewer trainable parameters than fully connected neural networks, with individual weights and biases having a clear interpretation. Our FENNI framework, within the EFENN framework, brings improvements to the HiDeNN approach. First, we propose a reference element-based architecture where shape functions are defined on a reference element, enabling variability in interpolation functions and straightforward use of Gaussian quadrature rules for evaluating the loss function. Second, we propose a pragmatic multigrid training strategy based on the framework's interpretability. Third, HiDeNN's combined rh-adaptivity is extended from 1D to 2D, with a new Jacobian-based criterion for adding nodes combining h- and r-adaptivity. From a deep learning perspective, adaptive mesh behavior through rh-adaptivity and the multigrid approach correspond to transfer learning, enabling FENNI to optimize the network's architecture dynamically during training. The framework's capabilities are demonstrated on 1D and 2D test cases, where its accuracy and computational cost are compared against an analytical solution and a classical FEM solver. On these cases, the multigrid training strategy drastically improves the training stage's efficiency and robustness. Finally, we introduce a variational loss within the EFENN framework, showing that it performs as well as energy-based losses and outperforms residual-based losses. This framework is extended to surrogate modeling over the parametric space in Part II
Inverse scattering for the multipoint potentials of Bethe-Peierls-Thomas-Fermi type
No full textInternational audienceWe consider the Schrödinger equation with a multipoint potential of the Bethe-Peierls-Thomas-Fermi type. We show that such a potential in dimension d = 2 or d = 3 is uniquely determined by its scattering amplitude at a fixed positive energy. Moreover, we show that there is no non-zero potential of this type with zero scattering amplitude at a fixed positive energy and a fixed incident direction. Nevertheless, we also show that a multipoint potential of this type is not uniquely determined by its scattering amplitude at a positive energy E and a fixed incident direction. Our proofs also contribute to the theory of inverse source problem for the Helmholtz equation with multipoint source.</div
Interacting topological quantum aspects with light and geometrical functions
No full textInternational audienceI review my recent progress and develop a geometrical approach in the quantum with light as a guide, from the vector potential in classical physics, revealing that topological properties can be equivalently measured from the poles of a sphere. The topological state is induced on the Bloch sphere of a spin-1/2 particle from a radial magnetic field related to the physics of Skyrmions. This shows a relation between the global topological response being measured at the poles, the response to a circularly polarized field and the quantum metric. I show how this approach is helpful for the classification of matter with the detection of the global topological invariant at specific points in the Brillouin zone, e.g. the Dirac points, from the responses to electromagnetic waves such as circularly polarized light and from new geometrical functions associated to the quantum metric measuring the quantum Hall and spin Hall conductivities. The M point associated to the Brillouin zone of the honeycomb lattice also reveals the topological signature. Interactions are included in momentum space within a stochastic variational approach. In a realistic quantum model of interacting spins, this leads to fractional topological entangled aspects with a correspondence between a pair of half invariants and a Einstein–Podolsky–Rosen (EPR) pair or Bell state at one pole. I also formulate a correspondence between fractional topological numbers and resonating valence bond states. This approach gives further insight on the characterization of topological matter linked to superconductivity, protected topological semimetals in two dimensions and on the search of Majorana fermions for topologically protected quantum information. We also address a correspondence with the fractional quantum Hall effect and surface states of three-dimensional topological insulators
Self-Defense: Optimal QIF Solutions and Application to Website Fingerprinting
No full textInternational audienceQuantitative Information Flow (QIF) provides a robust information-theoretical framework for designing secure systems with minimal information leakage. While previous research has addressed the design of such systems under hard constraints (e.g. application limitations) and soft constraints (e.g. utility), scenarios often arise where the core system's behavior is considered fixed. In such cases, the challenge is to design a new component for the existing system that minimizes leakage without altering the original system. In this work we address this problem by proposing optimal solutions for constructing a new row, in a known and unmodifiable information-theoretic channel, aiming at minimizing the leakage. We first model two types of adversaries: an exact-guessing adversary, aiming to guess the secret in one try, and a s-distinguishing one, which tries to distinguish the secret s from all the other secrets.Then, we discuss design strategies for both fixed and unknown priors by offering, for each adversary, an optimal solution under linear constraints, using Linear Programming.We apply our approach to the problem of website fingerprinting defense, considering a scenario where a site administrator can modify their own site but not others. We experimentally evaluate our proposed solutions against other natural approaches. First, we sample real-world news websites and then, for both adversaries, we demonstrate that the proposed solutions are effective in achieving the least leakage. Finally, we simulate an actual attack by training an ML classifier for the s-distinguishing adversary and show that our approach decreases the accuracy of the attacker
Search for in decays
No full textInternational audienceA search for the very rare and decays is conducted by analysing the process. The analysis uses proton-proton collision data collected with the LHCb detector between 2011 and 2018, corresponding to an integrated luminosity of 9. The signal signatures correspond to simultaneous peaks in the and invariant masses. No evidence for an excess of events over background is observed for either signal decay mode. Upper limits at the confidence level are set on the branching fractions relative to that for decays, \begin{align*} {\cal R}_{B^{*0}(\mu^+\mu^-)\pi^+/J\mskip -3mu/\mskip -2mu\psi\pi^+} &< 3.8\times 10^{-5}\ \text{ and } {\cal R}_{B_{s}^{*0}(\mu^+\mu^-)\pi^+/J\mskip -3mu/\mskip -2mu\psi\pi^+} &< 5.0\times 10^{-5}\,. \end{align*
Search for bottom quark associated production of the standard model Higgs boson in final states with leptons in proton-proton collisions at = 13 TeV
No full textInternational audienceThis Letter presents the first search for bottom quark associated production of the standard model Higgs boson, in final states with leptons. Higgs boson decays to pairs of tau leptons and pairs of leptonically decaying W bosons are considered. The search is performed using data collected from 2016 to 2018 by the CMS experiment in proton-proton collisions at a centre-of-mass energy of 13 TeV, corresponding to an integrated luminosity of 138 fb. Upper limits at the 95% confidence level are placed on the signal strength for Higgs boson production in association with bottom quarks; the observed (expected) upper limit is 3.7 (6.1) times the standard model prediction
Search for resonant pair production of Higgs bosons in the final state using large-area jets in proton-proton collisions at = 13 TeV
No full textInternational audienceA search is presented for the resonant production of a pair of standard model-like Higgs bosons using data from proton-proton collisions at a centre-of-mass energy of 13 TeV, collected by the CMS experiment at the CERN LHC in 2016-2018, corresponding to an integrated luminosity of 138 fb. The final state consists of two b quark-antiquark pairs. The search is conducted in the region of phase space where at least one of the pairs is highly Lorentz-boosted and is reconstructed as a single large-area jet. The other pair may be either similarly merged or resolved, the latter reconstructed using two b-tagged jets. The data are found to be consistent with standard model processes and are interpreted as 95% confidence level upper limits on the product of the cross sections and the branching fractions of the spin-0 radion and the spin-2 bulk graviton that arise in warped extradimensional models. The limits set are in the range 9.74-0.29 fb and 4.94-0.19 fb for a narrow radion and a graviton, respectively, with masses between 1 and 3 TeV. For a radion and for a bulk graviton with widths 10% of their masses, the limits are in the range 12.5-0.35 fb and 8.23-0.23 fb, respectively, for the same masses. These limits result in the exclusion of a narrow-width graviton with a mass below 1.2 TeV, and of narrow and 10%-width radions with masses below 2.6, and 2.9 TeV, respectively