More Like this

1. Dynamics of Newton Maps of Quadratic Polynomial Maps of ℝ2 into Itself

   https://doi.org/10.1142/S021812742030027X  

   De Leo, Roberto (July 2020, International Journal of Bifurcation and Chaos)

   null (Ed.)

   We study numerically the [Formula: see text]- and [Formula: see text]-limits of the Newton maps of quadratic polynomial transformations of the plane into itself. Our results confirm the conjectures posed in a recent work about the general dynamics of real Newton maps on the plane. 

   more » « less
2. Algorithms for Covering Barrier Points by Mobile Sensors with Line Constraint

   https://doi.org/10.1142/S0218195924500018  

   Jain, Princy; Wang, Haitao (February 2024, International Journal of Computational Geometry & Applications)

   We study the problem of covering barrier points by mobile sensors. Each sensor is represented by a point in the plane with the same covering range [Formula: see text] so that any point within distance [Formula: see text] from the sensor can be covered by the sensor. Given a set [Formula: see text] of [Formula: see text] points (called “barrier points”) and a set [Formula: see text] of [Formula: see text] points (representing the “sensors”) in the plane, the problem is to move the sensors so that each barrier point is covered by at least one sensor and the maximum movement of all sensors is minimized. The problem is NP-hard. In this paper, we consider two line-constrained variations of the problem and present efficient algorithms that improve the previous work. In the first problem, all sensors are given on a line [Formula: see text] and are required to move on [Formula: see text] only while the barrier points can be anywhere in the plane. We propose an [Formula: see text] time algorithm for the problem. We also consider the weighted case where each sensor has a weight; we give an [Formula: see text] time algorithm for this case. In the second problem, all barrier points are on [Formula: see text] while all sensors are in the plane but are required to move onto [Formula: see text] to cover all barrier points. We also solve the weighted case in [Formula: see text] time. 

   more » « less
3. The Information Bottleneck and Geometric Clustering

   https://doi.org/10.1162/neco_a_01136  

   Strouse, DJ; Schwab, David J. (March 2019, Neural Computation)

   The information bottleneck (IB) approach to clustering takes a joint distribution [Formula: see text] and maps the data [Formula: see text] to cluster labels [Formula: see text], which retain maximal information about [Formula: see text] (Tishby, Pereira, & Bialek, 1999 ). This objective results in an algorithm that clusters data points based on the similarity of their conditional distributions [Formula: see text]. This is in contrast to classic geometric clustering algorithms such as [Formula: see text]-means and gaussian mixture models (GMMs), which take a set of observed data points [Formula: see text] and cluster them based on their geometric (typically Euclidean) distance from one another. Here, we show how to use the deterministic information bottleneck (DIB) (Strouse & Schwab, 2017 ), a variant of IB, to perform geometric clustering by choosing cluster labels that preserve information about data point location on a smoothed data set. We also introduce a novel intuitive method to choose the number of clusters via kinks in the information curve. We apply this approach to a variety of simple clustering problems, showing that DIB with our model selection procedure recovers the generative cluster labels. We also show that, in particular limits of our model parameters, clustering with DIB and IB is equivalent to [Formula: see text]-means and EM fitting of a GMM with hard and soft assignments, respectively. Thus, clustering with (D)IB generalizes and provides an information-theoretic perspective on these classic algorithms. 

   more » « less
4. 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
5. Misiurewicz polynomials and dynamical units, part I

   https://doi.org/10.1142/S1793042123500616  

   Benedetto, Robert L; Goksel, Vefa (July 2023, International Journal of Number Theory)

   We study the dynamics of the unicritical polynomial family [Formula: see text]. The [Formula: see text]-values for which [Formula: see text] has a strictly preperiodic postcritical orbit are called Misiurewicz parameters, and they are the roots of Misiurewicz polynomials. The arithmetic properties of these special parameters have found applications in both arithmetic and complex dynamics. In this paper, we investigate some new such properties. In particular, when [Formula: see text] is a prime power and [Formula: see text] is a Misiurewicz parameter, we prove certain arithmetic relations between the points in the postcritical orbit of [Formula: see text]. We also consider the algebraic integers obtained by evaluating a Misiurewicz polynomial at a different Misiurewicz parameter, and we ask when these algebraic integers are algebraic units. This question naturally arises from some results recently proven by Buff, Epstein, and Koch and by the second author. We propose a conjectural answer to this question, which we prove in many cases. 

   more » « less