More Like this

1. On the computability of rotation sets and their entropies

   https://doi.org/10.1017/etds.2018.45  

   BURR, MICHAEL A.; SCHMOLL, MARTIN; WOLF, CHRISTIAN (February 2020, Ergodic Theory and Dynamical Systems)

   null (Ed.)

   Let $$f:X\rightarrow X$$ be a continuous dynamical system on a compact metric space $$X$$ and let $$\unicode[STIX]{x1D6F7}:X\rightarrow \mathbb{R}^{m}$$ be an $$m$$ -dimensional continuous potential. The (generalized) rotation set $$\text{Rot}(\unicode[STIX]{x1D6F7})$$ is defined as the set of all $$\unicode[STIX]{x1D707}$$ -integrals of $$\unicode[STIX]{x1D6F7}$$ , where $$\unicode[STIX]{x1D707}$$ runs over all invariant probability measures. Analogous to the classical topological entropy, one can associate the localized entropy $$\unicode[STIX]{x210B}(w)$$ to each $$w\in \text{Rot}(\unicode[STIX]{x1D6F7})$$ . In this paper, we study the computability of rotation sets and localized entropy functions by deriving conditions that imply their computability. Then we apply our results to study the case where $$f$$ is a subshift of finite type. We prove that $$\text{Rot}(\unicode[STIX]{x1D6F7})$$ is computable and that $$\unicode[STIX]{x210B}(w)$$ is computable in the interior of the rotation set. Finally, we construct an explicit example that shows that, in general, $$\unicode[STIX]{x210B}$$ is not continuous on the boundary of the rotation set when considered as a function of $$\unicode[STIX]{x1D6F7}$$ and $$w$$ . In particular, $$\unicode[STIX]{x210B}$$ is, in general, not computable at the boundary of $$\text{Rot}(\unicode[STIX]{x1D6F7})$$ . 

   more » « less
2. CHARACTERIZING THE CONTINUOUS DEGREES

   Andrews, Uri; Igusa, Gregory; Miller, Joseph S.; Soskova, Mariya I. (January 2019, Israel journal of mathematics)

   The continuous degrees measure the computability-theoretic content of elements of computable metric spaces. They properly extend the Turing degrees and naturally embed into the enumeration degrees. Although nontotal (i.e., non-Turing) continuous degrees exist, they are all very close to total: joining a continuous degree with a total degree that is not below it always results in a total degree. We call this property almost totality. We prove that the almost total degrees coincide with the continuous degrees. Since the total degrees are definable in the partial order of enumeration degrees, we see that the continuous degrees are also definable. Applying earlier work on the continuous degrees, this shows that the relation “PA above” on the total degrees is definable in the enumeration degrees. In order to prove that every almost total degree is continuous, we pass through another characterization of the continuous degrees that slightly simplifies one of Kihara and Pauly. We prove that the enumeration degree of A is continuous if and only if A is codable, meaning that A is enumeration above the complement of an infinite tree, every path of which enumerates A. 

   more » « less
3. Generically computable Abelian groups

   https://doi.org/10.1007/978-3-031-34034-5_3  

   Calvert, W.; Cenzer, D.; Harizanov, V. (June 2023, Unconventional Computation and Natural Computation)

   Genova, D.; Kari, J. (Ed.)

   Generically computable sets, as introduced by Jockusch and Schupp, have been of great interest in recent years. This idea of approximate computability was motivated by asymptotic density problems studied by Gromov in combinatorial group theory. More recently, we have defined notions of generically computable structures, and studied in particular equivalence structures and injection structures. A structure is said to be generically computable if there is a c.e. substructure defined on an asymptotically dense set, where the functions are computable and the relations are computably enumerable. It turned out that every equivalence structure has a generically computable copy, whereas there is a non-trivial characterization of the injection structures with generically computable copies. In this paper, we return to group theory, as we explore the generic computability of Abelian groups. We show that any Abelian p-group has a generically computable copy and that such a group has a Σ2-generically computably enumerable copy if and only it has a computable copy. We also give a partial characterization of the Σ1-generically computably enumerable Abelian p-groups. We also give a non-trivial characterization of the generically computable Abelian groups that are not p-groups. 

   more » « less
4. How Deep Sparse Networks Avoid the Curse of Dimensionality: Efficiently Computable Functions are Compositionally Sparse

   Poggio, Tomaso (March 2023, Center for Brains, Minds and Machines (CBMM))

   The main claim of this perspective is that compositional sparsity of the target function, which corresponds to the task to be learned, is the key principle underlying machine learning. Mhaskar and Poggio (2016) proved that sparsity of the compositional target functions (when the functions are on the reals, the constituent functions are also required to be smooth), naturally leads to sparse deep networks for approximation and thus for optimization. This is the case of most CNNs in current use, in which the known sparse graph of the target function is reflected in the sparse connectivity of the network. When the graph of the target function is unknown, I conjecture that transformers are able to implement a flexible version of sparsity (selecting which input tokens interact in the MLP layer), through the self-attention layers. Surprisingly, the assumption of compositional sparsity of the target function is not restrictive in practice, since I prove here that for computable functions (if on the reals with Lipschitz continuous derivatives) compositional sparsity is equivalent to efficient computability, that is Turing computability in polynomial time. 

   more » « less
5. Gromov-Witten Invariants in Complex and Morava-Local K-Theories

   https://doi.org/10.1007/s00039-024-00697-4  

   Abouzaid, Mohammed; McLean, Mark; Smith, Ivan (December 2024, Geometric and Functional Analysis)

   Abstract Given a closed symplectic manifoldX, we construct Gromov-Witten-type invariants valued both in (complex)K-theory and in any complex-oriented cohomology theory$$\mathbb{K}$$which isK_p(n)-local for some MoravaK-theoryK_p(n). We show that these invariants satisfy a version of the Kontsevich-Manin axioms, extending Givental and Lee’s work for the quantumK-theory of complex projective algebraic varieties. In particular, we prove a Gromov-Witten type splitting axiom, and hence define quantumK-theory and quantum$$\mathbb{K}$$-theory as commutative deformations of the corresponding (generalised) cohomology rings ofX; the definition of the quantum product involves the formal group of the underlying cohomology theory. The key geometric input of these results is a construction of global Kuranishi charts for moduli spaces of stable maps of arbitrary genus toX. On the algebraic side, in order to establish a common framework covering both ordinaryK-theory andK_p(n)-local theories, we introduce a formalism of ‘counting theories’ for enumerative invariants on a category of global Kuranishi charts. 

   more » « less