3 citations · 3 across the 4 of their papers we have counts for
9 papers
Structural vs. computational complexity
Johanna N. Y. Franklin, Dino Rossegger, Dan Turetsky
We consider highness in the context of computable structure theory and, particularly, the Scott rank of a structure. We define highness for Scott rank and highness for computably d…
Free structures and limiting density
Johanna N. Y. Franklin, Meng-Che "Turbo" Ho, Julia Knight
Gromov asked what a typical (finitely presented) group looks like, and he suggested a way to make the question precise in terms of limiting density. The typical finitely generated…
Computable classifications of continuous, transducer, and regular functions
Johanna N. Y. Franklin, Rupert Hölzl, Alexander Melnikov +2
We develop a systematic algorithmic framework that unites global and local classification problems using index sets. We prove that the classification problem for continuous (binary…
Key developments in algorithmic randomness
Johanna N. Y. Franklin, Christopher P. Porter
The goal of this introductory survey is to present the major developments of algorithmic randomness with an eye toward its historical development. While two highly comprehensive bo…
Degrees of and lowness for isometric isomorphism
Johanna N. Y. Franklin, Timothy H. McNicholl
We contribute to the program of extending computable structure theory to the realm of metric structures by investigating lowness for isometric isomorphism of metric structures. We…
Lowness for isomorphism, countable ideals, and computable traceability
Johanna N. Y. Franklin, Reed Solomon
We show that every countable ideal of degrees that are low for isomorphism is contained in a principal ideal of degrees that are low for isomorphism by adapting an exact pair const…
Algorithmic randomness and Fourier analysis
Johanna Franklin, Timothy McNicholl, Jason Rute
Suppose . Carleson's Theorem states that the Fourier series of any function in converges almost everywhere. We show that the Schnorr random points are…
Randomness and Non-ergodic Systems
Johanna N. Y. Franklin, Henry Towsner
We characterize the points that satisfy Birkhoff's ergodic theorem under certain computability conditions in terms of algorithmic randomness. First, we use the method of cutting an…
Anti-complex sets and reducibilities with tiny use
Johanna N. Y. Franklin, Noam Greenberg, Frank Stephan +1
In contrast with the notion of complexity, a set is called anti-complex if the Kolmogorov complexity of the initial segments of chosen by a recursive function is always bou…