More Like this

1. Euler Transformation of Polyhedral Complexes

   https://doi.org/10.1142/S0218195920500090  

   Gupta, Prashant; Krishnamoorthy, Bala (January 2021, International Journal of Computational Geometry & Applications)

   null (Ed.)

   We propose an Euler transformation that transforms a given [Formula: see text]-dimensional cell complex [Formula: see text] for [Formula: see text] into a new [Formula: see text]-complex [Formula: see text] in which every vertex is part of the same even number of edges. Hence every vertex in the graph [Formula: see text] that is the [Formula: see text]-skeleton of [Formula: see text] has an even degree, which makes [Formula: see text] Eulerian, i.e., it is guaranteed to contain an Eulerian tour. Meshes whose edges admit Eulerian tours are crucial in coverage problems arising in several applications including 3D printing and robotics. For [Formula: see text]-complexes in [Formula: see text] ([Formula: see text]) under mild assumptions (that no two adjacent edges of a [Formula: see text]-cell in [Formula: see text] are boundary edges), we show that the Euler transformed [Formula: see text]-complex [Formula: see text] has a geometric realization in [Formula: see text], and that each vertex in its [Formula: see text]-skeleton has degree [Formula: see text]. We bound the numbers of vertices, edges, and [Formula: see text]-cells in [Formula: see text] as small scalar multiples of the corresponding numbers in [Formula: see text]. We prove corresponding results for [Formula: see text]-complexes in [Formula: see text] under an additional assumption that the degree of a vertex in each [Formula: see text]-cell containing it is [Formula: see text]. In this setting, every vertex in [Formula: see text] is shown to have a degree of [Formula: see text]. We also present bounds on parameters measuring geometric quality (aspect ratios, minimum edge length, and maximum angle of cells) of [Formula: see text] in terms of the corresponding parameters of [Formula: see text] for [Formula: see text]. Finally, we illustrate a direct application of the proposed Euler transformation in additive manufacturing. 

   more » « less
2. On the structure of limiting flocks in hydrodynamic Euler Alignment models

   https://doi.org/10.1142/S0218202519500507  

   Leslie, Trevor M.; Shvydkoy, Roman (December 2019, Mathematical Models and Methods in Applied Sciences)

   The goal of this paper is to study limiting behavior of a self-organized continuous flock evolving according to the 1D hydrodynamic Euler Alignment model. We provide a series of quantitative estimates that show how far the density of the limiting flock is from a uniform distribution. The key quantity that controls density distortion is the entropy [Formula: see text], and the measure of deviation from uniformity is given by a well-known conserved quantity [Formula: see text], where [Formula: see text] is velocity and [Formula: see text] is the communication operator with kernel [Formula: see text]. The cases of Lipschitz, singular geometric, and topological kernels are covered in the study. 

   more » « less
3. Weighted Sobolev regularity and rate of approximation of the obstacle problem for the integral fractional Laplacian

   https://doi.org/10.1142/S021820251950057X  

   Borthagaray, Juan Pablo; Nochetto, Ricardo H.; Salgado, Abner J. (December 2019, Mathematical Models and Methods in Applied Sciences)

   We obtain regularity results in weighted Sobolev spaces for the solution of the obstacle problem for the integral fractional Laplacian [Formula: see text] in a Lipschitz bounded domain [Formula: see text] satisfying the exterior ball condition. The weight is a power of the distance to the boundary [Formula: see text] of [Formula: see text] that accounts for the singular boundary behavior of the solution for any [Formula: see text]. These bounds then serve us as a guide in the design and analysis of a finite element scheme over graded meshes for any dimension [Formula: see text], which is optimal for [Formula: see text]. 

   more » « less
4. For interpolating kernel machines, minimizing the norm of the ERM solution maximizes stability

   https://doi.org/10.1142/S0219530522400115  

   Rangamani, Akshay; Rosasco, Lorenzo; Poggio, Tomaso (January 2023, Analysis and Applications)

   In this paper, we study kernel ridge-less regression, including the case of interpolating solutions. We prove that maximizing the leave-one-out ([Formula: see text]) stability minimizes the expected error. Further, we also prove that the minimum norm solution — to which gradient algorithms are known to converge — is the most stable solution. More precisely, we show that the minimum norm interpolating solution minimizes a bound on [Formula: see text] stability, which in turn is controlled by the smallest singular value, hence the condition number, of the empirical kernel matrix. These quantities can be characterized in the asymptotic regime where both the dimension ([Formula: see text]) and cardinality ([Formula: see text]) of the data go to infinity (with [Formula: see text] as [Formula: see text]). Our results suggest that the property of [Formula: see text] stability of the learning algorithm with respect to perturbations of the training set may provide a more general framework than the classical theory of Empirical Risk Minimization (ERM). While ERM was developed to deal with the classical regime in which the architecture of the learning network is fixed and [Formula: see text], the modern regime focuses on interpolating regressors and overparameterized models, when both [Formula: see text] and [Formula: see text] go to infinity. Since the stability framework is known to be equivalent to the classical theory in the classical regime, our results here suggest that it may be interesting to extend it beyond kernel regression to other overparameterized algorithms such as deep networks. 

   more » « less
5. Coarse computability, the density metric, Hausdorff distances between Turing degrees, perfect trees, and reverse mathematics

   https://doi.org/10.1142/S0219061323500058  

   Hirschfeldt, Denis R; Jockusch, Carl G; Schupp, Paul E (August 2024, Journal of Mathematical Logic)

   For [Formula: see text], the coarse similarity class of A, denoted by [Formula: see text], is the set of all [Formula: see text] such that the symmetric difference of A and B has asymptotic density 0. There is a natural metric [Formula: see text] on the space [Formula: see text] of coarse similarity classes defined by letting [Formula: see text] be the upper density of the symmetric difference of A and B. We study the metric space of coarse similarity classes under this metric, and show in particular that between any two distinct points in this space there are continuum many geodesic paths. We also study subspaces of the form [Formula: see text] where [Formula: see text] is closed under Turing equivalence, and show that there is a tight connection between topological properties of such a space and computability-theoretic properties of [Formula: see text]. We then define a distance between Turing degrees based on Hausdorff distance in the metric space [Formula: see text]. We adapt a proof of Monin to show that the Hausdorff distances between Turing degrees that occur are exactly 0, [Formula: see text], and 1, and study which of these values occur most frequently in the senses of Lebesgue measure and Baire category. We define a degree a to be attractive if the class of all degrees at distance [Formula: see text] from a has measure 1, and dispersive otherwise. In particular, we study the distribution of attractive and dispersive degrees. We also study some properties of the metric space of Turing degrees under this Hausdorff distance, in particular the question of which countable metric spaces are isometrically embeddable in it, giving a graph-theoretic sufficient condition for embeddability. Motivated by a couple of issues arising in the above work, we also study the computability-theoretic and reverse-mathematical aspects of a Ramsey-theoretic theorem due to Mycielski, which in particular implies that there is a perfect set whose elements are mutually 1-random, as well as a perfect set whose elements are mutually 1-generic. Finally, we study the completeness of [Formula: see text] from the perspectives of computability theory and reverse mathematics. 

   more » « less