Search

In this paper, we introduce PASTA (Perceptual Assessment System for explanaTion of Artificial intelligence), a novel framework for a human-centric evaluation of XAI techniques in computer vision. Our first key contribution is a human evaluation of XAI explanations on four diverse datasets (COCO, Pascal Parts, Cats Dogs Cars, and MonumAI) which constitutes the first large-scale benchmark dataset for XAI, with annotations at both the image and concept levels. This dataset allows for robust evaluation and comparison across various XAI methods. Our second major contribution is a data-based metric for assessing the interpretability of explanations. It mimics human preferences, based on a database of human evaluations of explanations in the PASTA-dataset. With its dataset and metric, the PASTA framework provides consistent and reliable comparisons between XAI techniques, in a way that is scalable but still aligned with human evaluations. Additionally, our benchmark allows for comparisons between explanations across different modalities, an aspect previously unaddressed. Our findings indicate that humans tend to prefer saliency maps over other explanation types. Moreover, we provide evidence that human assessments show a low correlation with existing XAI metrics that are numerically simulated by probing the model., Comment: https://github.com/ENSTA-U2IS-AI/Dataset_XAI

Polarons can naturally form in materials from the interaction of extra charge carriers with the atomic lattice. Ubiquitous, they are central to various topics and phenomena such as high-T$_c$ superconductivity, electrochromism, photovoltaics, photocatalysis or ion batteries. However, polaron formation remains poorly understood and mostly relies on few historical models such as Landau-Pekar, Fr\"olich, Holstein or Jahn-Teller polarons. Here, from advanced first-principles calculations, we show that the formation of intriguing medium-size polarons in WO$_3$ does not fit with traditional models but instead arises from the undoing of distortive atomic motions inherent to the pristine phase, which lowers the bandgap through dynamical covalency effects. We so introduce the innovative concept of {\it anti-distortive} polaron and rationalize it from a quantum-dot model. We demonstrate that anti-distortive polarons are generic to different families of compounds and clarify how this new concept opens concrete perspectives for a better control of the polaronic state and related properties., Comment: 9 pages, 2 figures

We compute from density functional theory calculations the dynamical magnetic effective charges of the Jahn-Teller ground state of KCoF$_3$ and we unexpectedly obtain the largest up-to-date values reported in real materials (close to 200$\times 10^{-2}\mu_{\text{B}}/\text{\r{A}}$). We determine that those large values are due to both spin and orbital contributions, as expected from the presence of unquenched Co-d orbital magnetic moment, even though we show that the Co dynamical magnetic effective charges values are surprisingly zero by symmetry. Hence, we conclude that even if KCoF$_3$ is not multiferroic, it is antimagnetoelectric with a compensating but large individual magnetic sublattice magnetoelectric response of 210 ps/m per spin-channel. Our study shows that the dynamical magnetic effective charges might be an important property of magnetic materials beyond the magnetoelectric ones.

We establish that the Lavrentiev gap between Sobolev and Lipschitz maps does not occur for a scalar variational problem of the form: \[ \textrm{to minimize} \qquad u \mapsto \int_\Omega f(x,u,\nabla u)\text{d}x \,, \] under a Dirichlet boundary condition. Here, $\Omega$ is a bounded Lipschitz open set in $\mathbb{R}^N$, $N\geq 1$ and the function $f$ is required to be measurable with respect to the spacial variable, continuous with respect to the second one, and continuous and comparable to convex with respect to the last variable. Moreover, we assume that $f$ satisfies a natural condition balancing the variations with respect to the first variable and the growth with respect to the last one. Remarkably, typical conditions that are usually imposed on $f$ to discard the Lavrentiev gap are dropped here: we do not require $f$ to be bounded or convex with respect to the second variable, nor impose any condition of $\Delta_2$-kind with respect to the last variable.

In local certification, vertices of a $n$-vertex graph perform a local verification to check if a given property is satisfied by the graph. This verification is performed thanks to certificates, which are pieces of information that are given to the vertices. In this work, we focus on the local certification of $P_5$-freeness, and we prove a $O(n^{3/2})$ upper bound on the size of the certificates, which is (to our knowledge) the first subquadratic upper bound for this property.

This paper presents the design and implementation of the Scintillation Filter by Kalman-colored algorithm (SciFi), which is used to remove tropospheric scintillation from Q/V bands total attenuation data series. In contrast to the classical methods using low-pass filters, the SciFi algorithm allows to estimate both the attenuation, its slope and a confidence interval. Moreover, the linear observer structure of the Kalman filter allows it to operate in real time. Therefore, the states and uncertainties estimated by SciFi can be used as input for Fade Mitigation Techniques (FMT) such as Adaptive Coding and Modulation (ACM) or Site Diversity (SD). In this article, we propose a method to tune the noise level based on recommendations approved by the ITU-R. Finally, some results of filtering on Alphasat experimental data are discussed., Comment: Ka and Broadband Communications Conference, Seattle, WA, USA, Sept 2024

In the Stanley lattice defined on Dyck paths of size $n$, cover relations are obtained by replacing a valley $DU$ by a peak $UD$. We investigate a greedy version of this lattice, first introduced by Chenevi\`ere, where cover relations replace a factor $DU^k D$ by $U^kD^2$. By relating this poset to another poset recently defined by Nadeau and Tewari, we prove that this still yields a lattice, which we call the ascent lattice $L_n$. We then count intervals in $L_n$. Their generating function is found to be algebraic of degree $3$. The proof is based on a recursive decomposition of intervals involving two catalytic parameters. The solution of the corresponding functional equation is inspired by recent work on the enumeration of walks confined to a quadrant. We also consider the order induced in $L_{mn}$ on $m$-Dyck paths, that is, paths in which all ascent lengths are multiples of $m$, and on mirrored $m$-Dyck paths, in which all descent lengths are multiples of $m$. The first poset $L_{m,n}$ is still a lattice for any $m$, while the second poset $L'_{m,n}$ is only a join semilattice when $m>1$. In both cases, the enumeration of intervals is still described by an equation in two catalytic variables. Interesting connections arise with the sylvester congruence of Hivert, Novelli and Thibon, and again with walks confined to a quadrant. We combine the latter connection with probabilistic results to give asymptotic estimates of the number of intervals in both $L_{m,n}$ and $L'_{m,n}$. Their form implies that the generating functions of intervals are no longer algebraic, nor even D-finite, when $m>1$., Comment: 35 pages

Local certification is the area of distributed network computing asking the following question: How to certify to the nodes of a network that a global property holds, if they are limited to a local verification? In this area, it is often essential to have identifiers, that is, unique integers assigned to the nodes. In this short paper, we show how to reduce the range of the identifiers, in three different settings. More precisely, we show how to rename identifiers in the classical local certification setting, when we can (resp. cannot) choose the new identifiers, and we show how a global certificate can help to encode very compactly a new identifier assignment that is not injective in general, but still useful. We conclude with a number of applications of these three results.

In this paper, we investigate how local rules enforced at every node can influence the topology of a network. More precisely, we establish several results on the diameter of trees as a function of the number of nodes, as listed below. These results have important consequences on the landscape of locally checkable labelings (LCL) on \emph{unbounded} degree graphs, a case in which our lack of knowledge is in striking contrast with that of \emph{bounded degree graphs}, that has been intensively studied recently. [See paper for full abstract.]

Input variables in numerical models are often subject to several levels of uncertainty, usually modeled by probability distributions. In the context of uncertainty quantification applied to these models, studying the robustness of output quantities with respect to the input distributions requires: (a) defining variational classes for these distributions; (b) calculating boundary values for the output quantities of interest with respect to these variational classes. The latter should be defined in a way that is consistent with the information structure defined by the ``baseline'' choice of input distributions. Considering parametric families, the variational classes are defined using the geodesic distance in their Riemannian manifold, a generic approach to such problems. Theoretical results and application tools are provided to justify and facilitate the implementation of such robustness studies, in concrete situations where these distributions are truncated -- a setting frequently encountered in applications. The feasibility of our approach is illustrated in a simplified industrial case study.

Chirality refers to the asymmetry of objects that cannot be superimposed on their mirror image. It is a concept that exists in various scientific fields and has profound consequences. Although these are perhaps most widely recognized within biology, chemistry, and pharmacology, recent advances in chiral phonons, topological systems, crystal enantiomorphic materials, and magneto-chiral materials have brought this topic to the forefront of condensed matter physics research. Our review discusses the symmetry requirements and the features associated with structural chirality in inorganic materials. This allows us to explore the nature of phase transitions in these systems, the coupling between order parameters, and their impact on the material's physical properties. We highlight essential contributions to the field, particularly recent progress in the study of chiral phonons, altermagnetism, magnetochirality between others. Despite the rarity of naturally occurring inorganic chiral crystals, this review also highlights a significant knowledge gap, presenting challenges and opportunities for structural chirality mostly at the fundamental level, e.g., chiral displacive phase transitions and ferrochirality, possibilities of tuning and switching structural chirality by external means (electric, magnetic, or strain fields), whether chirality could be an independent order parameter, and whether structural chirality could be quantified, etc. Beyond simply summarising this field of research, this review aims to inspire further research in materials science by addressing future challenges, encouraging the exploration of chirality beyond traditional boundaries, and seeking the development of innovative materials with superior or new properties.

An st-shortest path, or st-path for short, in a graph G is a shortest (induced) path from s to t in G. Two st-paths are said to be adjacent if they differ on exactly one vertex. A reconfiguration sequence between two st-paths P and Q is a sequence of adjacent st-paths starting from P and ending at Q. Deciding whether there exists a reconfiguration sequence between two given $st$-paths is known to be PSPACE-complete, even on restricted classes of graphs such as graphs of bounded bandwidth (hence pathwidth). On the positive side, and rather surprisingly, the problem is polynomial-time solvable on planar graphs. In this paper, we study the parameterized complexity of the Shortest Path Reconfiguration (SPR) problem. We show that SPR is W[1]-hard parameterized by k + \ell, even when restricted to graphs of bounded (constant) degeneracy; here k denotes the number of edges on an st-path, and \ell denotes the length of a reconfiguration sequence from P to Q. We complement our hardness result by establishing the fixed-parameter tractability of SPR parameterized by \ell and restricted to nowhere-dense classes of graphs. Additionally, we establish fixed-parameter tractability of SPR when parameterized by the treedepth, by the cluster-deletion number, or by the modular-width of the input graph.

Using first-principles calculations, we explore the magnetoelectric properties of the room-temperature multiferroic crystal BiCoO$_3$. We use both applied magnetic field and finite-difference techniques to show that BiCoO$_3$ is anti-magnetoelectric at the linear level. The calculation of the dynamical effective charges reveals that the total magnetoelectric response is zero due to the compensating non-zero magnetoelectric response of each magnetic sublattice. This calculation also highlights that the the orbital contribution to the response is remarkably larger than the spin one and that each sublattice has a rather large total magnetoelectric response of 85 ps/m. Furthermore, we provide an intuitive recipe to visualize the dynamical magnetic effective charge, allowing to examine its multipolar nature which we confirm by means of ab initio calculations. Given the large value of the local response, we investigate the ferromagnetic phase as well, which gives a giant magnetoelectric response of about 1000 ps/m and coming mainly from the spin contribution this time. Finally, we discuss the possible reasons for such a large magnetoelectric response in BiCoO3 and propose possible strategies to unveil this potentially large response.

In this short note, we prove that every twin-free graph on $n$ vertices contains a locating-dominating set of size at most $\lceil\frac{5}{8}n\rceil$. This improves the earlier bound of $\lfloor\frac{2}{3}n\rfloor$ due to Foucaud, Henning, L\"owenstein and Sasse from 2016, and makes some progress towards the well-studied locating-dominating conjecture of Garijo, Gonz\'alez and M\'arquez., Comment: 5 pages, 1 figure. Changed title. To appear in Discrete Mathematics 348(2), 2025

We compare the various chirality measures most widely used in the literature to quantify chiral symmetry in extended solids, i.e., the continuous chirality measure, the Hausdorff distance, and the angular momentum. By studying these functions in an algebraically tractable case, we can evaluate their strengths and weaknesses when applied to more complex crystals. Going beyond those classical calculations, we propose a new method to quantify the handedness of a crystal based on a pseudoscalar function, i.e., the helicity. This quantity, borrowed from hydrodynamics, can be computed from the eigenvector carrying the system from the high-symmetry non-chiral phase to the low-symmetry chiral phase. Different model systems like K$_3$NiO$_2$, CsCuCl$_3$ and MgTi$_2$O$_4$ are used as test cases where we show the superior interest of using helicity to quantify chirality together with the handedness distinction.

We demonstrate through first-principles calculations applied to the K$_{3}$NiO$_{2}$ crystal that a structural phase transition from an achiral to a chiral phase can be mediated by a degenerate soft phonon mode and controlled by pressure and epitaxial strain. Breaking such degeneracy with an electric field generates a competition between enantiomorphic, polar, and orthorhombic displacements. Originated by the interaction between spontaneous chiral and induced polar and axial modes, an optimal parameter window for converting the handedness of the system into its opposite kind is observed.

Surface acoustic wave devices are key components for processing radio frequency signals in wireless communication because these devices offer simultaneously high performance, compact size and low cost. The optimization of the device structure requires a quantitative understanding of energy conversion and loss mechanisms. Stroboscopic full-field diffraction x-ray microscopy studies of a prototypical one-port resonator device revealed the existence of unanticipated acoustic loss. A non-uniform acoustic excitation in the active area was responsible for the substantial end and side leakages observed at the design frequency. Quantitative analysis of the strain amplitude using a wave decomposition method allowed the determination of several key device parameters. This high-resolution spatiotemporal strain imaging technique is, more generally, suited for studying nanophononics, specifically when the feature size is smaller than optical wavelengths. The strain sensitivity allows precise measurement of acoustic waves with picometer-scale amplitude.

The SdSv challenge Task 2 provided an opportunity to assess efficiency and robustness of modern text-independent speaker verification systems. But it also made it possible to test new approaches, capable of taking into account the main issues of this challenge (duration, language, ...). This paper describes the contributions of our laboratory to the speaker recognition field. These contributions highlight two other challenges in addition to short-duration and language: the mismatch between enrollment and test data and the one between subsets of the evaluation trial dataset. The proposed approaches experimentally show their relevance and efficiency on the SdSv evaluation, and could be of interest in many real-life applications., Comment: LIA system description for the Short Duration Speaker Verification (SdSv) challenge 2020 Task 2

This article provides a critical review of the main methods used to produce conservative estimators of probabilities of rare events, or critical failures, for reliability and certification studies in the broadest sense. These probabilities must theoretically be calculated from simulations of (certified) numerical models, but which typically suffer from prohibitive computational costs. This occurs frequently, for instance, for complex and critical industrial systems. We focus therefore in adapting the common use of surrogates to replace these numerical models, the aim being to offer a high level of confidence in the results. We suggest avenues of research to improve the guarantees currently reachable.

Detecting specific structures in a network has been a very active theme of research in distributed computing for at least a decade. In this paper, we start the study of subgraph detection from the perspective of local certification. Remember that a local certification is a distributed mechanism enabling the nodes of a network to check the correctness of the current configuration, thanks to small pieces of information called certificates. Our main question is: For a given graph $H$, what is the minimum certificate size that allows checking that the network does not contain $H$ as a (possibly induced) subgraph? We show a variety of lower and upper bounds, uncovering an interesting interplay between the optimal certificate size, the size of the forbidden subgraph, and the locality of the verification. Along the way we introduce several new technical tools, in particular what we call the \emph{layered map}, which is not specific to forbidden subgraphs and that we expect to be useful for certifying many other properties.

In this work, we provide an upper bound for global certification of graph homomorphism, a generalization of graph coloring. In certification, the nodes of a network should decide if the network satisfies a given property, thanks to small pieces of information called certificates. Here, there is only one global certificate which is shared by all the nodes, and the property we want to certify is the existence of a graph homomorphism to a given graph. For bipartiteness, a special case of graph homomorphism, Feuilloley and Hirvonen proved in~\cite{FeuilloleyH18} some upper and lower bounds on the size of the optimal certificate, and made the conjecture that their lower bound could be improved to match their upper bound. We prove that this conjecture is false: their lower bound was in fact optimal, and we prove it by providing the matching upper bound using a known result of perfect hashing.

Given a graph $G$ and two independent sets of $G$, the independent set reconfiguration problem asks whether one independent set can be transformed into the other by moving a single vertex at a time, such that at each intermediate step we have an independent set of $G$. We study the complexity of this problem for $H$-free graphs under the token sliding and token jumping rule. Our contribution is twofold. First, we prove a reconfiguration analogue of Alekseev's theorem, showing that the problem is PSPACE-complete unless $H$ is a path or a subdivision of the claw. We then show that under the token sliding rule, the problem admits a polynomial-time algorithm if the input graph is fork-free., Comment: 19 pages, 4 figures

Dominating sets in graphs are often used to model some monitoring of the graph: guards are posted on the vertices of the dominating set, and they can thus react to attacks occurring on the unguarded vertices by moving there (yielding a new set of guards, which may not be dominating anymore). A dominating set is eternal if it can endlessly resist to attacks. From the attacker's perspective, if we are given a non-eternal dominating set, the question is to determine how fast can we provoke an attack that cannot be handled by a neighboring guard. We investigate this question from a computational complexity point of view, by showing that this question is PSPACE-hard, even for graph classes where finding a minimum eternal dominating set is in P. We then complement this result by giving polynomial time algorithms for cographs and trees, and showing a connection with tree-depth for the latter. We also investigate the problem from a parameterized complexity perspective, mainly considering two parameters: the number of guards and the number of steps., Comment: 26 pages, 4 figures

The fusion of non-Abelian anyons or topological defects is a fundamental operation in measurement-only topological quantum computation. In topological superconductors, this operation amounts to a determination of the shared fermion parity of Majorana zero modes. As a step towards this, we implement a single-shot interferometric measurement of fermion parity in indium arsenide-aluminum heterostructures with a gate-defined nanowire. The interferometer is formed by tunnel-coupling the proximitized nanowire to quantum dots. The nanowire causes a state-dependent shift of these quantum dots' quantum capacitance of up to 1 fF. Our quantum capacitance measurements show flux h/2e-periodic bimodality with a signal-to-noise ratio of 1 in 3.7 $\mu$s at optimal flux values. From the time traces of the quantum capacitance measurements, we extract a dwell time in the two associated states that is longer than 1 ms at in-plane magnetic fields of approximately 2 T. These results are consistent with a measurement of the fermion parity encoded in a pair of Majorana zero modes that are separated by approximately 3 $\mu$m and subjected to a low rate of poisoning by non-equilibrium quasiparticles. The large capacitance shift and long poisoning time enable a parity measurement error probability of 1%., Comment: Added data on a second measurement of device A and a measurement of device B, expanded discussion of a trivial scenario. Refs added, author list updated

We say that a graph is $k$-mixing if it is possible to transform any $k$-coloring into any other via a sequence of single vertex recolorings keeping a proper coloring all along. Cereceda, van den Heuvel and Johnson proved that deciding if a graph is $3$-mixing is co-NP-complete and left open the case $k \ge 4$. We prove that for every $k \ge 4$, $k$-mixing is co-NP-hard.

A new loss function for speaker recognition with deep neural network is proposed, based on Jeffreys Divergence. Adding this divergence to the cross-entropy loss function allows to maximize the target value of the output distribution while smoothing the non-target values. This objective function provides highly discriminative features. Beyond this effect, we propose a theoretical justification of its effectiveness and try to understand how this loss function affects the model, in particular the impact on dataset types (i.e. in-domain or out-of-domain w.r.t the training corpus). Our experiments show that Jeffreys loss consistently outperforms the state-of-the-art for speaker recognition, especially on out-of-domain data, and helps limit false alarms., Comment: Accepted in ICASSP 2023

Local certification is a distributed mechanism enabling the nodes of a network to check the correctness of the current configuration, thanks to small pieces of information called certificates. For many classic global properties, like checking the acyclicity of the network, the optimal size of the certificates depends on the size of the network, $n$. In this paper, we focus on properties for which the size of the certificates does not depend on $n$ but on other parameters. We focus on three such important properties and prove tight bounds for all of them. Namely, we prove that the optimal certification size is: $\Theta(\log k)$ for $k$-colorability (and even exactly $\lceil \log k \rceil$ bits in the anonymous model while previous works had only proved a $2$-bit lower bound); $(1/2)\log t+o(\log t)$ for dominating sets at distance $t$ (an unexpected and tighter-than-usual bound) ; and $\Theta(\log \Delta)$ for perfect matching in graphs of maximum degree $\Delta$ (the first non-trivial bound parameterized by $\Delta$). We also prove some surprising upper bounds, for example, certifying the existence of a perfect matching in a planar graph can be done with only two bits. In addition, we explore various specific cases for these properties, in particular improving our understanding of the trade-off between locality of the verification and certificate size., Comment: Accepted at STACS 2024

We study from first-principles calculations the ferroelectric structural phase transition of Pb$_5$Ge$_3$O$_{11}$ crystal. The calculations of phonons and Born effective charges of the paraelectric phase allow us to identify a polar instability that is unstable in both transverse-optic and longitudinal-optic versions, giving rise to an entire branch of instability along a propagation vector parallel to the mode polarization (the hexagonal axe). This is the hint of hyperferroelectricity and the stable head-to-head and tail-to-tail domain, as recently reported from both experiments and theory. Then, our analysis of the ferroelectric phase shows that the polarization of Pb$_5$Ge$_3$O$_{11}$ is uniaxial along the hexagonal axes and with small in-plane components due to a piezoelectric effect. The symmetry-adapted mode analysis shows that the total ferroelectric ground state distortion comes mainly from polar distortions of the unstable polar phonon mode but also from an invariant, cooperative mode that amplifies the polar deformation. We also build a phenomenological model that highlights how the coupling between these modes is at play and helps us understand how to reproduce the second-order phase transition. At last, we also quantify the structural chirality through the continuous symmetry measure method and trace its origin to the polar unstable mode itself. By extending our approach to the phonon states we further show that the chirality is poorly affected by the relaxation but could also be enhanced by activating high frequency modes with polar symmetry. Finally we study the phonon angular momentum (AM) distribution in both phases and identify trends in the AM behaviour across the Brillouin zone.

A non-crossing spanning tree of a set of points in the plane is a spanning tree whose edges pairwise do not cross. Avis and Fukuda in 1996 proved that there always exists a flip sequence of length at most $2n-4$ between any pair of non-crossing spanning trees (where $n$ denotes the number of points). Hernando et al. proved that the length of a minimal flip sequence can be of length at least $\frac 32 n$. Two recent results of Aichholzer et al. and Bousquet et al. improved the Avis and Fukuda upper bound by proving that there always exists a flip sequence of length respectively at most $2n - \log n$ and $2n - \sqrt{n}$. We improve the upper bound by a linear factor for the first time in 25 years by proving that there always exists a flip sequence between any pair of non-crossing spanning trees $T_1,T_2$ of length at most $c n$ where $c \approx 1.95$. Our result is actually stronger since we prove that, for any two trees $T_1,T_2$, there exists a flip sequence from $T_1$ to $T_2$ of length at most $c |T_1 \setminus T_2|$. We also improve the best lower bound in terms of the symmetric difference by proving that there exists a pair of trees $T_1,T_2$ such that a minimal flip sequence has length $\frac 53 |T_1 \setminus T_2|$, improving the lower bound of Hernando et al. by considering the symmetric difference instead of the number of vertices. We generalize this lower bound construction to non-crossing flips (where we close the gap between upper and lower bounds) and rotations.

Performing an additive decomposition of arbitrary functions of random elements is paramount for global sensitivity analysis and, therefore, the interpretation of black-box models. The well-known seminal work of Hoeffding characterized the summands in such a decomposition in the particular case of mutually independent inputs. Going beyond the framework of independent inputs has been an ongoing challenge in the literature. Existing solutions have so far required constraining assumptions or suffer from a lack of interpretability. In this paper, we generalize Hoeffding's decomposition for dependent inputs under very mild conditions. For that purpose, we propose a novel framework to handle dependencies based on probability theory, functional analysis, and combinatorics. It allows for characterizing two reasonable assumptions on the dependence structure of the inputs: non-perfect functional dependence and non-degenerate stochastic dependence. We then show that any square-integrable, real-valued function of random elements respecting these two assumptions can be uniquely additively decomposed and offer a characterization of the summands using oblique projections. We then introduce and discuss the theoretical properties and practical benefits of the sensitivity indices that ensue from this decomposition. Finally, the decomposition is analytically illustrated on bivariate functions of Bernoulli inputs.

We establish the sign of the linear magnetoelectric (ME) coefficient, $\alpha$, in chromia, Cr$_2$O$_3$. Cr$_2$O$_3$ is the prototypical linear ME material, in which an electric (magnetic) field induces a linearly proportional magnetization (polarization), and a single magnetic domain can be selected by annealing in combined magnetic (H) and electric (E) fields. Opposite antiferromagnetic domains have opposite ME responses, and which antiferromagnetic domain corresponds to which sign of response has previously been unclear. We use density functional theory (DFT) to calculate the magnetic response of a single antiferromagnetic domain of Cr$_2$O$_3$ to an applied in-plane electric field at 0 K. We find that the domain with nearest neighbor magnetic moments oriented away from (towards) each other has a negative (positive) in-plane ME coefficient, $\alpha_{\perp}$, at 0 K. We show that this sign is consistent with all other DFT calculations in the literature that specified the domain orientation, independent of the choice of DFT code or functional, the method used to apply the field, and whether the direct (magnetic field) or inverse (electric field) ME response was calculated. Next, we reanalyze our previously published spherical neutron polarimetry data to determine the antiferromagnetic domain produced by annealing in combined E and H fields oriented along the crystallographic symmetry axis at room temperature. We find that the antiferromagnetic domain with nearest-neighbor magnetic moments oriented away from (towards) each other is produced by annealing in (anti-)parallel E and H fields, corresponding to a positive (negative) axial ME coefficient, $\alpha_{\parallel}$, at room temperature. Since $\alpha_{\perp}$ at 0 K and $\alpha_{\parallel}$ at room temperature are known to be of opposite sign, our computational and experimental results are consistent., Comment: 11 pages, 5 figures

We explore from first-principles calculations the ferroelectric material Pb5Ge3O11 as a model for controlling the spin-orbit interaction (SOC) in crystalline solids. The SOC has a surprisingly strong effect on the structural energy landscape by deepening the ferroelectric double well. We observe that this effect comes from a specific Pb Wyckoff site that lies on the verge of a natural cavity channel of the crystal. We also find that a unique cavity state is formed by the empty 6p states of another Pb site at the edge of the cavity channel. This cavity state exhibits a sizeable spin splitting with a mixed Rashba-Weyl character and a topologically protected crossing of the related bands. We also show that the ferroelectric properties and the significant SOC effects are exceptionally robust against n-doping up to several electrons per unit cell. We trace the provenance of these original effects to the unique combination of the structural cavity channel and the chemistry of the Pb atoms with 6p orbitals localizing inside the channel.

We consider a greedy version of the $m$-Tamari order defined on $m$-Dyck paths, recently introduced by Dermenjian. Inspired by intriguing connections between intervals in the ordinary 1-Tamari order and planar triangulations, and more generally by the existence of simple formulas counting intervals in the ordinary $m$-Tamari orders, we investigate the number of intervals in the greedy order on $m$-Dyck paths of fixed size. We find again a simple formula, which also counts certain planar maps (of prescribed size) called $(m+1)$-constellations. For instance, when $m=1$ the number of intervals in the greedy order on 1-Dyck paths of length $2n$ is proved to be $\frac{3\cdot 2^{n-1}}{(n+1)(n+2)} \binom{2n}{n}$, which is also the number of bipartite maps with $n$ edges. Our approach is recursive, and uses a ``catalytic'' parameter, namely the length of the final descent of the upper path of the interval. The resulting bivariate generating function is algebraic for all $m$. We show that the same approach can be used to count intervals in the ordinary $m$-Tamari lattices as well. We thus recover the earlier result of the first author, Fusy and Pr\'eville-Ratelle, who were using a different catalytic parameter., Comment: 24 pages

The metric dimension has been introduced independently by Harary, Melter and Slater in 1975 to identify vertices of a graph G using its distances to a subset of vertices of G. A resolving set X of a graph G is a subset of vertices such that, for every pair (u,v) of vertices of G, there is a vertex x in X such that the distance between x and u and the distance between x and v are distinct. The metric dimension of the graph is the minimum size of a resolving set. Computing the metric dimension of a graph is NP-hard even on split graphs and interval graphs. Bonnet and Purohit proved that the metric dimension problem is W[1]-hard parameterized by treewidth. Li and Pilipczuk strenghtened this result by showing that it is NP-hard for graphs of treewidth. In this article, we prove that that metric dimension is FPT parameterized by treewidth in chordal graphs.

We consider spanning trees of $n$ points in convex position whose edges are pairwise non-crossing. Applying a flip to such a tree consists in adding an edge and removing another so that the result is still a non-crossing spanning tree. Given two trees, we investigate the minimum number of flips required to transform one into the other. The naive $2n-\Omega(1)$ upper bound stood for 25 years until a recent breakthrough from Aichholzer et al. yielding a $2n-\Omega(\log n)$ bound. We improve their result with a $2n-\Omega(\sqrt{n})$ upper bound, and we strengthen and shorten the proofs of several of their results.

Given two $k$-dicolourings of a digraph $D$, we prove that it is PSPACE-complete to decide whether we can transform one into the other by recolouring one vertex at each step while maintaining a dicolouring at any step even for $k=2$ and for digraphs with maximum degree $5$ or oriented planar graphs with maximum degree $6$. A digraph is said to be $k$-mixing if there exists a transformation between any pair of $k$-colourings. We show that every digraph $D$ is $k$-mixing for all $k\geq \delta^*_{\min}(D)+2$, generalizing a result due to Dyer et al. We also prove that every oriented graph $\vec{G}$ is $k$-mixing for all $k\geq \delta^*_{\max}(\vec{G}) +1$ and for all $k\geq \delta^*_{\rm avg}(\vec{G})+1$. We conjecture that, for every digraph $D$, the dicolouring graph of $D$ on $k\geq \delta_{\min}^*(D)+2$ colours has diameter at most $O(|V(D)|^2)$ and give some evidences. We first prove that the dicolouring graph of any digraph $D$ on $k\geq 2\delta_{\min}^*(D) + 2$ colours has linear diameter, extending a result from Bousquet and Perarnau. We also prove that the conjecture is true when $k\geq \frac{3}{2}(\delta_{\min}^*(D)+1)$. Restricted to the special case of oriented graphs, we prove that the dicolouring graph of any subcubic oriented graph on $k\geq 2$ colours is connected and has diameter at most $2n$. We conjecture that every non $2$-mixing oriented graph has maximum average degree at least $4$, and we provide some support for this conjecture by proving it on the special case of $2$-freezable oriented graphs. More generally, we show that every $k$-freezable oriented graph on $n$ vertices must contain at least $kn + k(k-2)$ arcs, and we give a family of $k$-freezable oriented graphs that reach this bound. In the general case, we prove as a partial result that every non $2$-mixing oriented graph has maximum average degree at least $\frac{7}{2}$., Comment: 28 pages, 6 figures

Understanding the behavior of a black-box model with probabilistic inputs can be based on the decomposition of a parameter of interest (e.g., its variance) into contributions attributed to each coalition of inputs (i.e., subsets of inputs). In this paper, we produce conditions for obtaining unambiguous and interpretable decompositions of very general parameters of interest. This allows to recover known decompositions, holding under weaker assumptions than stated in the literature.

We show that every $3$-connected $K_{2,\ell}$-minor free graph with minimum degree at least $4$ has maximum degree at most $7\ell$. As a consequence, we show that every 3-connected $K_{2,\ell}$-minor free graph with minimum degree at least $5$ and no twins of degree $5$ has bounded size. Our proofs use Steiner trees and nested cuts; in particular, they do not rely on Ding's characterization of $K_{2,\ell}$-minor free graphs.

The independent set reconfiguration problem asks whether one can transform one given independent set of a graph into another, by changing vertices one by one in such a way the intermediate sets remain independent. Extremal problems on independent sets are widely studied: for example, it is well known that an $n$-vertex graph has at most $3^{n/3}$ maximum independent sets (and this is tight). This paper investigates the asymptotic behavior of maximum possible length of a shortest reconfiguration sequence for independent sets of size $k$ among all $n$-vertex graphs. We give a tight bound for $k=2$. We also provide a subquadratic upper bound (using the hypergraph removal lemma) as well as an almost tight construction for $k=3$. We generalize our results for larger values of $k$ by proving an $n^{2\lfloor k/3 \rfloor}$ lower bound.

We study several variants of a combinatorial game which is based on Cantor's diagonal argument. The game is between two players called Kronecker and Cantor. The names of the players are motivated by the known fact that Leopold Kronecker did not appreciate Georg Cantor's arguments about the infinite, and even referred to him as a "scientific charlatan". In the game Kronecker maintains a list of m binary vectors, each of length n, and Cantor's goal is to produce a new binary vector which is different from each of Kronecker's vectors, or prove that no such vector exists. Cantor does not see Kronecker's vectors but he is allowed to ask queries of the form"What is bit number j of vector number i?" What is the minimal number of queries with which Cantor can achieve his goal? How much better can Cantor do if he is allowed to pick his queries \emph{adaptively}, based on Kronecker's previous replies? The case when m=n is solved by diagonalization using n (non-adaptive) queries. We study this game more generally, and prove an optimal bound in the adaptive case and nearly tight upper and lower bounds in the non-adaptive case., Comment: 11 pages, added acknowledgements

We construct a universally Bayes consistent learning rule that satisfies differential privacy (DP). We first handle the setting of binary classification and then extend our rule to the more general setting of density estimation (with respect to the total variation metric). The existence of a universally consistent DP learner reveals a stark difference with the distribution-free PAC model. Indeed, in the latter DP learning is extremely limited: even one-dimensional linear classifiers are not privately learnable in this stringent model. Our result thus demonstrates that by allowing the learning rate to depend on the target distribution, one can circumvent the above-mentioned impossibility result and in fact, learn \emph{arbitrary} distributions by a single DP algorithm. As an application, we prove that any VC class can be privately learned in a semi-supervised setting with a near-optimal \emph{labeled} sample complexity of $\tilde{O}(d/\varepsilon)$ labeled examples (and with an unlabeled sample complexity that can depend on the target distribution).

This chapter reviews for each province and destination of the Solar System the representative space missions that will have to be designed and implemented by 2061 to address the six key science questions about the diversity, origins, workings and habitability of planetary systems (described in chapter 1) and to perform the critical observations that have been described in chapters 3 and partly 2. It derives from this set of future representative missions, some of which will have to be flown during the 2041-2061 period, the critical technologies and supporting infrastructures that will be needed to fly these challenging missions, thus laying the foundation for the description of technologies and infrastructures for the future of planetary exploration that is given in chapters 5 and 6, respectively., Comment: 83 pages, 23 figures, 7 tables, Horizon 2061 is a science-driven, foresight exercise, for future scientific investigations

We pursue the study of a model convex functional with orthotropic structure and nonstandard growth conditions, this time focusing on the sub-quadratic case. We prove that bounded local minimizers are locally Lipschitz. No restriction on the ratio between the highest and the lowest growth rates are needed. The result holds also in presence of a non-autonomous lower order term, under sharp integrability assumptions. Finally, we prove higher differentiability of bounded local minimizers, as well., Comment: 45 pages

This manuscript describes the I4U submission to the 2020 NIST Speaker Recognition Evaluation (SRE'20) Conversational Telephone Speech (CTS) Challenge. The I4U's submission was resulted from active collaboration among researchers across eight research teams - I$^2$R (Singapore), UEF (Finland), VALPT (Italy, Spain), NEC (Japan), THUEE (China), LIA (France), NUS (Singapore), INRIA (France) and TJU (China). The submission was based on the fusion of top performing sub-systems and sub-fusion systems contributed by individual teams. Efforts have been spent on the use of common development and validation sets, submission schedule and milestone, minimizing inconsistency in trial list and score file format across sites., Comment: SRE 2021, NIST Speaker Recognition Evaluation Workshop, CTS Speaker Recognition Challenge, 14-12 December 2021

Out-of-plane polar domain structures have recently been discovered in strained and twisted bilayers of inversion symmetry broken systems such as hexagonal boron nitride. Here we show that this symmetry breaking also gives rise to an in-plane component of polarization, and the form of the total polarization is determined purely from symmetry considerations. The in-plane component of the polarization makes the polar domains in strained and twisted bilayers topologically non-trivial, forming a network of merons and antimerons (half-skyrmions and half-antiskyrmions). For twisted systems, the merons are of Bloch type whereas for strained systems they are of N\'eel type. We propose that the polar domains in strained or twisted bilayers may serve as a platform for exploring topological physics in layered materials and discuss how control over topological phases and phase transitions may be achieved in such systems., Comment: Accepted version

A coloring of a digraph is a partition of its vertex set such that each class induces a digraph with no directed cycles. A digraph is $k$-chromatic if $k$ is the minimum number of classes in such partition, and a digraph is oriented if there is at most one arc between each pair of vertices. Clearly, the smallest $k$-chromatic digraph is the complete digraph on $k$ vertices, but determining the order of the smallest $k$-chromatic oriented graphs is a challenging problem. It is known that the smallest $2$-, $3$- and $4$-chromatic oriented graphs have $3$, $7$ and $11$ vertices, respectively. In 1994, Neumann-Lara conjectured that a smallest $5$-chromatic oriented graph has $17$ vertices. We solve this conjecture and show that the correct order is $19$.

We consider Sharpness-Aware Minimization (SAM), a gradient-based optimization method for deep networks that has exhibited performance improvements on image and language prediction problems. We show that when SAM is applied with a convex quadratic objective, for most random initializations it converges to a cycle that oscillates between either side of the minimum in the direction with the largest curvature, and we provide bounds on the rate of convergence. In the non-quadratic case, we show that such oscillations effectively perform gradient descent, with a smaller step-size, on the spectral norm of the Hessian. In such cases, SAM's update may be regarded as a third derivative -- the derivative of the Hessian in the leading eigenvector direction -- that encourages drift toward wider minima.

Humans can reason compositionally when presented with new tasks. Previous research shows that appropriate prompting techniques enable large language models (LLMs) to solve artificial compositional generalization tasks such as SCAN. In this work, we identify additional challenges in more realistic semantic parsing tasks with larger vocabulary and refine these prompting techniques to address them. Our best method is based on least-to-most prompting: it decomposes the problem using prompting-based syntactic parsing, then uses this decomposition to select appropriate exemplars and to sequentially generate the semantic parse. This method allows us to set a new state of the art for CFQ while requiring only 1% of the training data used by traditional approaches. Due to the general nature of our approach, we expect similar efforts will lead to new results in other tasks and domains, especially for knowledge-intensive applications., Comment: Fixed metadata. No other changes

Robustness studies of black-box models is recognized as a necessary task for numerical models based on structural equations and predictive models learned from data. These studies must assess the model's robustness to possible misspecification of regarding its inputs (e.g., covariate shift). The study of black-box models, through the prism of uncertainty quantification (UQ), is often based on sensitivity analysis involving a probabilistic structure imposed on the inputs, while ML models are solely constructed from observed data. Our work aim at unifying the UQ and ML interpretability approaches, by providing relevant and easy-to-use tools for both paradigms. To provide a generic and understandable framework for robustness studies, we define perturbations of input information relying on quantile constraints and projections with respect to the Wasserstein distance between probability measures, while preserving their dependence structure. We show that this perturbation problem can be analytically solved. Ensuring regularity constraints by means of isotonic polynomial approximations leads to smoother perturbations, which can be more suitable in practice. Numerical experiments on real case studies, from the UQ and ML fields, highlight the computational feasibility of such studies and provide local and global insights on the robustness of black-box models to input perturbations.

Learning curves plot the expected error of a learning algorithm as a function of the number of labeled samples it receives from a target distribution. They are widely used as a measure of an algorithm's performance, but classic PAC learning theory cannot explain their behavior. As observed by Antos and Lugosi (1996 , 1998), the classic `No Free Lunch' lower bounds only trace the upper envelope above all learning curves of specific target distributions. For a concept class with VC dimension $d$ the classic bound decays like $d/n$, yet it is possible that the learning curve for \emph{every} specific distribution decays exponentially. In this case, for each $n$ there exists a different `hard' distribution requiring $d/n$ samples. Antos and Lugosi asked which concept classes admit a `strong minimax lower bound' -- a lower bound of $d'/n$ that holds for a fixed distribution for infinitely many $n$. We solve this problem in a principled manner, by introducing a combinatorial dimension called VCL that characterizes the best $d'$ for which $d'/n$ is a strong minimax lower bound. Our characterization strengthens the lower bounds of Bousquet, Hanneke, Moran, van Handel, and Yehudayoff (2021), and it refines their theory of learning curves, by showing that for classes with finite VCL the learning rate can be decomposed into a linear component that depends only on the hypothesis class and an exponential component that depends also on the target distribution. As a corollary, we recover the lower bound of Antos and Lugosi (1996 , 1998) for half-spaces in $\mathbb{R}^d$. Finally, to provide another viewpoint on our work and how it compares to traditional PAC learning bounds, we also present an alternative formulation of our results in a language that is closer to the PAC setting.