We present a revisit of the seeds algorithm to explore the semigroup tree. First, an equivalent definition of seed is presented, which seems easier to manage. Second, we determine the seeds of semigroups with at most three left elements. And third, we find the great-grandchildren of any numerical semigroup in terms of its seeds. The RGD algorithm is the fastest known algorithm at the moment. But if one compares the originary seeds algorithm with the RGD algorithm, one observes that the seeds algorithm uses more elaborated mathematical tools while the RGD algorithm uses data structures that are better adapted to the final C implementations. For genera up to around one half of the maximum size of native integers, the newly defined seeds algorithm performs significantly better than the RGD algorithm. For future compilators allowing larger native sized integers this may constitute a powerful tool to explore the semigroup tree up to genera never explored before. The new seeds algorithm uses bitwise integer operations, the knowledge of the seeds of semigroups with at most three left elements and of the great-grandchildren of any numerical semigroup, apart from techniques such as parallelization and depth first search as wisely introduced in this context by Fromentin and Hivert. The algorithm has been used to prove that there are no Eliahou semigroups of genus $66$, hence proving the Wilf conjecture for genus up to $66$. We also found three Eliahou semigroups of genus $67$. One of these semigroups is neither of Eliahou-Fromentin type, nor of Delgado's type. However, it is a member of a new family suggested by Shalom Eliahou.
相關內容
Quantification is a supervised machine learning task, focused on estimating the class prevalence of a dataset rather than labeling its individual observations. We introduce Continuous Sweep, a new parametric binary quantifier inspired by the well-performing Median Sweep. Median Sweep is currently one of the best binary quantifiers, but we have changed this quantifier on three points, namely 1) using parametric class distributions instead of empirical distributions, 2) optimizing decision boundaries instead of applying discrete decision rules, and 3) calculating the mean instead of the median. We derive analytic expressions for the bias and variance of Continuous Sweep under general model assumptions. This is one of the first theoretical contributions in the field of quantification learning. Moreover, these derivations enable us to find the optimal decision boundaries. Finally, our simulation study shows that Continuous Sweep outperforms Median Sweep in a wide range of situations.
Graph Neural Networks (GNNs) are the state-of-the-art model for machine learning on graph-structured data. The most popular class of GNNs operate by exchanging information between adjacent nodes, and are known as Message Passing Neural Networks (MPNNs). Given their widespread use, understanding the expressive power of MPNNs is a key question. However, existing results typically consider settings with uninformative node features. In this paper, we provide a rigorous analysis to determine which function classes of node features can be learned by an MPNN of a given capacity. We do so by measuring the level of pairwise interactions between nodes that MPNNs allow for. This measure provides a novel quantitative characterization of the so-called over-squashing effect, which is observed to occur when a large volume of messages is aggregated into fixed-size vectors. Using our measure, we prove that, to guarantee sufficient communication between pairs of nodes, the capacity of the MPNN must be large enough, depending on properties of the input graph structure, such as commute times. For many relevant scenarios, our analysis results in impossibility statements in practice, showing that over-squashing hinders the expressive power of MPNNs. We validate our theoretical findings through extensive controlled experiments and ablation studies.
Medical imaging models have been shown to encode information about patient demographics such as age, race, and sex in their latent representation, raising concerns about their potential for discrimination. Here, we ask whether requiring models not to encode demographic attributes is desirable. We point out that marginal and class-conditional representation invariance imply the standard group fairness notions of demographic parity and equalized odds, respectively, while additionally requiring risk distribution matching, thus potentially equalizing away important group differences. Enforcing the traditional fairness notions directly instead does not entail these strong constraints. Moreover, representationally invariant models may still take demographic attributes into account for deriving predictions. The latter can be prevented using counterfactual notions of (individual) fairness or invariance. We caution, however, that properly defining medical image counterfactuals with respect to demographic attributes is highly challenging. Finally, we posit that encoding demographic attributes may even be advantageous if it enables learning a task-specific encoding of demographic features that does not rely on social constructs such as 'race' and 'gender.' We conclude that demographically invariant representations are neither necessary nor sufficient for fairness in medical imaging. Models may need to encode demographic attributes, lending further urgency to calls for comprehensive model fairness assessments in terms of predictive performance across diverse patient groups.
Modeling self-gravitating gas flows is essential to answering many fundamental questions in astrophysics. This spans many topics including planet-forming disks, star-forming clouds, galaxy formation, and the development of large-scale structures in the Universe. However, the nonlinear interaction between gravity and fluid dynamics offers a formidable challenge to solving the resulting time-dependent partial differential equations (PDEs) in three dimensions (3D). By leveraging the universal approximation capabilities of a neural network within a mesh-free framework, physics informed neural networks (PINNs) offer a new way of addressing this challenge. We introduce the gravity-informed neural network (GRINN), a PINN-based code, to simulate 3D self-gravitating hydrodynamic systems. Here, we specifically study gravitational instability and wave propagation in an isothermal gas. Our results match a linear analytic solution to within 1\% in the linear regime and a conventional grid code solution to within 5\% as the disturbance grows into the nonlinear regime. We find that the computation time of the GRINN does not scale with the number of dimensions. This is in contrast to the scaling of the grid-based code for the hydrodynamic and self-gravity calculations as the number of dimensions is increased. Our results show that the GRINN computation time is longer than the grid code in one- and two- dimensional calculations but is an order of magnitude lesser than the grid code in 3D with similar accuracy. Physics-informed neural networks like GRINN thus show promise for advancing our ability to model 3D astrophysical flows.
We study the problem of enumerating Tarski fixed points, focusing on the relational lattices of equivalences, quasiorders and binary relations. We present a polynomial space enumeration algorithm for Tarski fixed points on these lattices and other lattices of polynomial height. It achieves polynomial delay when enumerating fixed points of increasing isotone maps on all three lattices, as well as decreasing isotone maps on the lattice of binary relations. In those cases in which the enumeration algorithm does not guarantee polynomial delay on the three relational lattices on the other hand, we prove exponential lower bounds for deciding the existence of three fixed points when the isotone map is given as an oracle, and that it is NP-hard to find three or more Tarski fixed points. More generally, we show that any deterministic or bounded-error randomized algorithm must perform a number of queries asymptotically at least as large as the lattice width to decide the existence of three fixed points when the isotone map is given as an oracle. Finally, we demonstrate that our findings yield a polynomial delay and space algorithm for listing bisimulations and instances of some related models of behavioral or role equivalence.
This work is the first exploration of proof-theoretic semantics for a substructural logic. It focuses on the base-extension semantics (B-eS) for intuitionistic multiplicative linear logic (IMLL). The starting point is a review of Sandqvist's B-eS for intuitionistic propositional logic (IPL), for which we propose an alternative treatment of conjunction that takes the form of the generalized elimination rule for the connective. The resulting semantics is shown to be sound and complete. This motivates our main contribution, a B-eS for IMLL, in which the definitions of the logical constants all take the form of their elimination rule and for which soundness and completeness are established.
We derive a Bernstein von-Mises theorem in the context of misspecified, non-i.i.d., hierarchical models parametrized by a finite-dimensional parameter of interest. We apply our results to hierarchical models containing non-linear operators, including the squared integral operator, and PDE-constrained inverse problems. More specifically, we consider the elliptic, time-independent Schr\"odinger equation with parametric boundary condition and general parabolic PDEs with parametric potential and boundary constraints. Our theoretical results are complemented with numerical analysis on synthetic data sets, considering both the square integral operator and the Schr\"odinger equation.
We consider the problem of estimating the trace of a matrix function $f(A)$. In certain situations, in particular if $f(A)$ cannot be well approximated by a low-rank matrix, combining probing methods based on graph colorings with stochastic trace estimation techniques can yield accurate approximations at moderate cost. So far, such methods have not been thoroughly analyzed, though, but were rather used as efficient heuristics by practitioners. In this manuscript, we perform a detailed analysis of stochastic probing methods and, in particular, expose conditions under which the expected approximation error in the stochastic probing method scales more favorably with the dimension of the matrix than the error in non-stochastic probing. Extending results from [E. Aune, D. P. Simpson, J. Eidsvik, Parameter estimation in high dimensional Gaussian distributions, Stat. Comput., 24, pp. 247--263, 2014], we also characterize situations in which using just one stochastic vector is always -- not only in expectation -- better than the deterministic probing method. Several numerical experiments illustrate our theory and compare with existing methods.
Numerical homogenization of multiscale equations typically requires taking an average of the solution to a microscale problem. Both the boundary conditions and domain size of the microscale problem play an important role in the accuracy of the homogenization procedure. In particular, imposing naive boundary conditions leads to a $\mathcal{O}(\epsilon/\eta)$ error in the computation, where $\epsilon$ is the characteristic size of the microscopic fluctuations in the heterogeneous media, and $\eta$ is the size of the microscopic domain. This so-called boundary, or ``cell resonance" error can dominate discretization error and pollute the entire homogenization scheme. There exist several techniques in the literature to reduce the error. Most strategies involve modifying the form of the microscale cell problem. Below we present an alternative procedure based on the observation that the resonance error itself is an oscillatory function of domain size $\eta$. After rigorously characterizing the oscillatory behavior for one dimensional and quasi-one dimensional microscale domains, we present a novel strategy to reduce the resonance error. Rather than modifying the form of the cell problem, the original problem is solved for a sequence of domain sizes, and the results are averaged against kernels satisfying certain moment conditions and regularity properties. Numerical examples in one and two dimensions illustrate the utility of the approach.
Kleene's computability theory based on the S1-S9 computation schemes constitutes a model for computing with objects of any finite type and extends Turing's 'machine model' which formalises computing with real numbers. A fundamental distinction in Kleene's framework is between normal and non-normal functionals where the former compute the associated Kleene quantifier $\exists^n$ and the latter do not. Historically, the focus was on normal functionals, but recently new non-normal functionals have been studied based on well-known theorems, the weakest among which seems to be the uncountability of the reals. These new non-normal functionals are fundamentally different from historical examples like Tait's fan functional: the latter is computable from $\exists^2$, while the former are computable in $\exists^3$ but not in weaker oracles. Of course, there is a great divide or abyss separating $\exists^2$ and $\exists^3$ and we identify slight variations of our new non-normal functionals that are again computable in $\exists^2$, i.e. fall on different sides of this abyss. Our examples are based on mainstream mathematical notions, like quasi-continuity, Baire classes, bounded variation, and semi-continuity from real analysis.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191