Schedule for: 16w5072 - Algorithmic Randomness Interacts with Analysis and Ergodic Theory

A welcome drink will be served at the hotel.

Choquet’s theorem and the Krein-Milman theorem characterize ways that elements of a compact subset of a locally convex topological vector space can be decomposed into weighted combinations of extreme points. Given a notion of invariance, the extreme points of the collection of invariant measures often coincide with the ergodic ones, and so these results have significant consequences for ergodic theory. In this talk we consider the computable content of these these theorems, including older results from computable analysis (in the finite dimensional case, or for invariant measures) as well as some recent results involving computable analogues of the more general theorems. Joint work with Cameron Freer.

Countless theorems of analysis assert the convergence of sequences of numbers, functions, or elements of an abstract space. Classical proofs often establish such results without providing explicit rates of convergence, and, in fact, it is often impossible to compute the limiting object or a rate of convergence from the given data. This results in the curious situation that a theorem may tell us that a sequence converges, but we have no way of knowing how fast it converges, or what it converges to.

During the past few years, much research in ergodic theory and convex optimization has been carried out in the context of so-called CAT$(\kappa)$-spaces with $\kappa>0$ which may be viewed as metric generalizations of Riemannian manifolds whose sectional curvature is bounded by $\kappa$. Recently, L. Leuştean and A. Nicolae obtained, based on proof mining techniques, a deep quantitative analysis of a nonlinear ergodic theorem in the context of CAT$(\kappa)$-spaces. We established quantitative convex feasibility theorems in this context. This leads to the question whether the proof-theoretic machinery used in the program of proof mining can be adapted to establish a general bound-extraction theorem applicable to the framework of CAT$(\kappa)$-spaces. Together with A. Nicolae we recently showed that this indeed is the case.

Subshifts of $2^{\mathbb{Z}^d}$ have been studied recently using tools from both computability theory and descriptive set theory. A lot of work in the computability approach is on the complexity of the members of subshifts (e.g. Turing spectrum). In the descriptive set theory approach one often studies the complexity of topological isomorphism for various classes of subshifts (such as Toeplitz, or minimal). Open questions in the area abound. For instance, what is the complexity of topological isomorphism between minimal subshifts? Initial contributors: Miller, Nies, Westrick, and others.

Consider dense linear orders without endpoints having underlying set the natural numbers. They admit a unique probability measure that is invariant to the logic action of S_\infty on the underlying set, called the Glasner-Weiss measure. In contrast, the Rado graph admits continuum many ergodic invariant measures (among them, the Erdős-Rényi constructions for arbitrary p such that 0 < p < 1). We characterize all isomorphism classes of structures that admit an unique invariant measure, and show that any isomorphism class admitting more than one invariant measure must admit continuum many ergodic ones. Joint work with Nathanael Ackerman, Aleksandra Kwiatkowska, and Rehana Patel.

This is a joint talk with Henry Towsner. In our 2014 paper "Randomness and Non-ergodic Systems", we showed that, given a non-Martin-Loef random point, one can construct a computable measure-preserving (but non-ergodic) transformation and a computable function for which the point fails to satisfy Birkhoff's ergodic theorem. A natural extension is to ask whether, given a weaker assumption, one can do the same with a lower semicomputable function. We summarize the technique used in our paper and then discuss the obstacles we have encountered in extending this approach to a weaker assumption.

Details TBD

See Monday

A classic result in algorithmic information theory is that every infinite binary sequence is computable from a Martin-Loef random infinite binary sequence. Proved independently by Kucera and Gacs, this result answered a question by Charles Bennett and has seen numerous applications in the last 30 years. The optimal redundancy in such a coding process has, however, remained unknown. If the computation of the first n bits of a sequence requires n + g(n) bits of the random oracle, then g is the redundancy of the computation. Kucera implicitly achieved redundancy n log n while Gacs used a more elaborate block-coding procedure which achieved redundancy sqrt(n) log n. Different approaches to coding such as the one by Merkle and Mihailovic have not improved this redundancy bound. In this talk we devise a new coding method that achieves optimal logarithmic redundancy. Our redundancy bound is exponentially smaller than the previously best known bound and is also shown to be the best possible. It follows that redundancy r log n in computation from a random oracle is possible for every stream, if and only if r > 1.

We report on classifications in the Weihrauch lattice that are related to probabilistic computations and randomness. We will demonstrate how the Weihrauch lattice can be used to characterize notions of probabilistic computability, characterize the uniform computational content of theorems and randomness notions.

Many results of computable analysis can be reunderstood in the setting of reverse mathematics. For example, if there exists a computable instance of a problem whose solution always computes a PA degree, then one can almost say that the statement implies WKL over RCA_0. However, there sometimes exists a non-trivial gap to interpret computable analysis results into reverse mathematics because of the lack of induction. In this talk, I will show such examples and introduce several ways to overcome those obstructions. This is a joint work with Andre Nies and Marcus Triplett.

https://en.wikipedia.org/wiki/Lambityeco

Schnorr randomness is a randomness notion based on Brouwer's concept of a "constructive null set." Recently, Schnorr randomness has been closely associated with a number of theorems in computable analysis, including the Lebesgue differentiation theorem, the ergodic theorem (for ergodic measures), and Carleson's theorem. Nonetheless, the theory of Schnorr randomness is not nearly as developed as that of Martin-Löf randomness. In particular, there is no established notion of Schnorr randomness with respect to noncomputable measures. Such a notion would be essential to applying Schnorr randomness to disintegration theorems such as de Finetti's theorem or the ergodic decomposition theorem. In this talk I will present a novel definition of Schnorr randomness for noncomputable measures. Say that $x_0$ is \emph{Schnorr random with respect to} a (possibly noncomputable) measure $\mu_0$ if $t(x_0,\mu_0) < \infty$ for all lower semicomputable functions $t(x,\mu)$ such that $\mu \mapsto \int t(x,\mu) d\mu$ is finite and computable. I will show that this definition satisfies the basic properties that one would expect such a notion to have. I will also present various applications of this definition, and discuss how it fits into a larger research program.

In 1927, Van der Waerden proved that if the set of natural numbers is partitioned into two sets, one of them will have arbitrarily long arithmetic progressions. Erdos conjectured that one could partition any infinite set S of numbers into two, and one of the parts will contain arbitrarily long arithmetic progressions. Szemeredi proved this correct in 1975, using combinatorial techniques, namely the Regularity Lemma. In 1978, Furstenberg provided an ergodic theoretic proof of Szemeredi's result. The talk will cover the topological dynamical approach to questions on arithmetic progressions on integer sets using Furstenberg's approach. We mention an effective version of Furstenberg's result in specific settings, a joint work with Rod Downey and Andre Nies.

Assuming Woodin's ${\sf AD}^+$, we show that, in a certain sense, the structure of ``natural'' many-one degrees is isomorphic to the Wadge degrees. More precisely, we show that there is an isomorphism between the {\em many-one-on-a-cone} degrees of {\em uniformly Turing- to many-one degree invariant functions} and the Wadge degrees of subsets of the Baire space. Furthermore, if $\mathcal{Q}$ is a better-quasi-order, the same holds true for $\mathcal{Q}$-valued many-one/Wadge degrees (e.g., many-one/Wadge degrees of $k$-partitions, $k$-coverings, ordinal-valued maps, etc.) Moreover, within ${\sf ZFC}$, we also show that these order structures restricted to $\mathcal{Q}$-valued {\em Borel} functions are isomorphic to a simple quasi-order on transfinite nests of $\mathcal{Q}$-labeled trees. This is joint work with Antonio Montalb\'an.

It is known that if $x\in[0,1]$ is polynomial time random then x is normal in any integer base greater than one. We show that if x is polynomial time random and \beta>1 is Pisot, then x is "normal in base beta", in the sense that the sequence $(x \beta^n)_{n \in N}$ is uniformly distributed modulo one. We work with the notion of "P-martingale", a generalization of martingales to non-uniform distributions, and show that a sequence over a finite alphabet is distributed according to an irreducible, invariant Markov measure P if an only if no P-martingale whose betting factors are computed by a deterministic finite automaton succeeds on it. This is a generalization of Schnorr and Stimm's characterization of normal sequences in integer bases. Our results use tools and techniques from symbolic dynamics, together with automata theory and algorithmic randomness. (Joint with Javier Almarza)

One of the most important open problems in computable complex dynamics is whether the Mandelbrot set can be computed with arbitrary precision. We will review what is known about this question, and present a recent negative result for a Mandelbrot-like set associated with a one-parameter cubic (instead of quadratic) family. This is joint work with Coronel and Yampolsky.

Discuss all talks of Wed and Th

Every ML random set $X$ is effectively bi-immune: there is a recursive function $g$ such that if $W_e$ is a subset of $X$ or its complement, then $|W_e| < g(e)$. Beros has shown that there are DNR functions that compute no effectively bi-immune set, answering a question of Jockusch and Lewis. We improve this result and show that there are reals of effective Hausdorff dimension 1 that compute no effectively bi-immune set. Greenberg and Miller had previously shown the same thing with effective bi-immunity replaced with ML randomness. It is open whether every effectively bi-immune set computes an ML random set.

We will give an overview of the main results and last progresses in higher randomness. We will first talk about how, many results of algorithmic randomness can be transferred in the higher setting (we cover for this part results from the paper "Continuous higher randomness", Bienvenu, Greenberg, Monin). We will then talk more specifically about results which are specific to the higher settings, in particular results about $\Pi^1_1$-randomness and its categorical analogue : $\Sigma^1_1$-genericity (we cover for this part results from the paper "Higher randomness and genericity", Greenberg, Monin).

Denjoy defined a method of integration which generalizes Lebesgue integration. The functions obtainable by Denjoy integration are continuous and belong to a transfinite hierarchy, where the height in the hierarchy is determined uniquely by the number of steps of Denjoy integration needed to produce the function. We discuss effective properties of this hierarchy.