Workshop Programme
for period 2 - 6 July 2012
CCR 2012: 7th Conference on Computability, Complexity and Randomness
2 - 6 July 2012
Timetable
Monday 2 July | ||||
09:00-09:25 | Registration | |||
09:25-09:30 | Welcome | |||
09:30-10:30 | Lutz, J (Iowa State University) | |||
Alan Turing in the twenty-first century: normal numbers, randomness, and finite automata | Sem 1 | |||
We discuss ways in which Turing's then-unpublished ``A Note on Normal Numbers'' foreshadows and can still guide research in our time. This research was supported in part by NSF Grant 0652569. Part of the work was done while the author was on sabbatical at Caltech and the Isaac Newton Institute for Mathematical Sciences at the University of Cambridge. |
||||
10:30-11:00 | Morning coffee | |||
11:00-12:00 | Nies, A (University of Auckland) | |||
Demuth randomness and its variants | Sem 1 | |||
A Demuth test is like a Martin-Löf test with the passing condition to be out of infinitely many components; the strength of the test is enhanced by the possibility to exchange the $n$-th component of the test a computably bounded number of times. Demuth introduced Demuth randomness of reals in 1982, and showed that the Denjoy alternative for Markov computable functions holds at any such real. In [1] we proved that Demuth's hypothesis is in fact too strong: difference randomness (i.e., ML-randomness together with incompleteness) of the real already suffices. However, Demuth randomness now plays an important role in the interaction of computability and randomness. The basic relevant fact here is that a Demuth random set can be below the halting problem. In [2] we characterized lowness for Demuth randomness by a property called BLR-traceability, in conjunction with being computably dominated. The low for Demuth random sets form a proper subclass of the computably traceable sets used by Terwijn and Zambella to characterize lowness for Schnorr randomness. The covering problem asks whether each K-trivial set $A$ is Turing below a difference random set $Y$. Combining work of Kucera and Nies [3] with results of Downey, Diamondstone, Greenberg and Turetsky gives an affirmative answer to an analogous question: a set $A$ is strongly jump traceable if and only if it is below a Demuth random set $Y$. In recent work, Bienvenu, Greenberg, Kucera, Nies, and Turetsky introduced a weakening of Demuth randomness called Oberwolfach randomness. They used it to build a ``smart'' K-trivial set $A$: it is difficult to cover in that any Martin-Löf random set $Y$ above $A$ must be LR-hard. [2] Bienvenu, Downey, Greenberg, Nies, and Turetsky. "Characterizing lowness for Demuth Randomness." Submitted. [1] Bienvenu, Hoelzl, Miller, and Nies. "The Denjoy alternative for computable functions." Proceedings of STACS 2012. [3] Kucera, A. and Nies, A. Demuth. "randomness and computational complexity." Annals of Pure and Applied Logic 162 (2011) 504–513. |
||||
12:00-12:30 | Sanders, S (Universiteit Gent) | |||
Nonstandard Analysis: a new way to compute | Sem 1 | |||
Constructive Analysis was introduced by Errett Bishop to identify the `computational meaning' of mathematics. Bishop redeveloped mathematics, in the spirit of intuitionistic mathematics, based on primitive notions like algorithm, explicit computation, and finite procedure. The exact meaning of these vague terms was left open, to ensure the compatibility of Constructive Analysis with several traditions in mathematics. Constructive Reverse Mathematics (CRM) is a spin-off from Harvey Friedman's famous Reverse Mathematics program, based on Constructive Analysis. In this talk, we introduce `$\Omega$-invariance': a simple and elegant definition of finite procedure in (classical) Nonstandard Analysis. We show that $\Omega$-invariance captures Bishop's notion of algorithm quite well. In particular, using an intuitive interpretation based on $\Omega$-invariance, we obtain many results from CRM inside Nonstandard Analysis. Similar results for Computability (aka Recursion) Theory are also discussed. This research is made possible through the generous support of a grant from the John Templeton Foundation for the project Philosophical Frontiers in Reverse Mathematics. Please note that the opinions expressed in this publication are those of the author and do not necessarily reflect the views of the John Templeton Foundation. |
||||
12:30-13:30 | Lunch at Wolfson Court. | |||
14:00-15:00 | Shen, A (Université de Montpellier 2) | |||
Topological arguments in Kolmogorov complexity | Sem 1 | |||
We show how topological arguments (simple facts about non-homotopic mappings) can be used to prove result about Kolmogorov complexity. In particular, we show that for every string x of complexity at least n +c log n one can find a string y such that both conditional complexities C(x|y) and C(y|x) are equal to n+O(1). See also: http://arxiv.org/abs/1206.4927 |
||||
15:00-15:30 | Miyabe, K (Kyoto University) | |||
Schnorr triviality is equivalent to being a basis for tt-Schnorr randomness | Sem 1 | |||
We present some new characterizations of Schnorr triviality. Schnorr triviality is defined using complexity via a computable measure machine, with which Schnorr randomness has a characterization. Since we have a characterization of Schnorr randomness via decidable prefix-free machine, we also have a characterization of Schnorr triviality using complexity via a decidable prefix-free machine. It should be noted that numerous characterizations of Schnorr triviality have the following form: for any computable object, there exists another computable object such that the real is in some object. By defining a basis for Schnorr randomness in a similar manner, we can show the equivalence to Schnorr triviality while Franklin and Stephan (2010) showed that there exists a Schnorr trivial set that is not truth-table reducible to any Schnorr random set. |
||||
15:30-16:00 | Afternoon tea | |||
17:00-17:30 | Petrovic, T (University of Zagreb) | |||
Two betting strategies that predict all compressible sequences | Sem 1 | |||
A new type of betting games that charaterize Martin-Löf randomness is introduced. These betting games can be compared to martingale processes of Hitchcock and Lutz as well as non-monotonic betting strategies. Sequence-set betting is defined as successive betting on prefix-free sets that contain a finite number of words. In each iteration we start with an initial prefix-free set $P$ and an initial capital $c$, then we divide $P$ into two prefix-free sets $P_{0}$ and $P_{1}$ of equal size and wager some amount of capital on one of the sets, let's say $P_{0}$. If the infinite sequence we are betting on has a prefix in $P_{0}$ then in the next iteration the initial set is $P_{0}$ and the wagered amount is doubled. If the infinite sequence we are betting on does not have a prefix in $P_{0}$ then in the next iteration the initial set is $P_{1}$ and the wagered amount is lost. In the first iteration the initial prefix-free set contains the empty string. The player succeeds on the infinite sequence if the series of bets increases capital unboundedly. Non-monotonic betting can be viewed as sequence-set betting with an additional requirement that the initial prefix-free set is divided into two prefix-free sets such that sequences in one set have at some position bit 0 and in the other have at that same position bit 1. On the other hand if the requirement that the initial prefix-free set $P$ is divided into two prefix-free sets of equal size is removed, and we allow that $P_{0}$ may have a different size from $P_{1}$ we have a betting game that is equivalent to martingale processes in the sense that for each martingale process there is a betting strategy that succeeds on the same sequences as martingale process and for each betting strategy a martingale process exists that succeeds on the the same sequences as the betting strategy. It is shown that, unlike martingale processes, for any computable sequence-set betting strategy there is an infinite sequence on which betting strategy doesn't succeed and which is not Martin-Löf random. Furthermore it is shown that there is an algorithm that constructs two sets of betting decisions for two sequence-set betting strategies such that for any sequence that is not Martin-Löf random at least one of them succeeds on that sequence. |
||||
17:30-18:00 | Rute, J (Carnegie Mellon University) | |||
Computable randomness and its properties | Sem 1 | |||
Computable randomness at first does not seem as natural of a randomness notion as Schnorr and Martin-Löf randomness. However, recently Brattka, Miller, and Nies [1] have shown that computable randomness is closely linked to differentiability. Why is this so? What are the chances that, say, computable randomness will also be linked to the ergodic theorem? In this talk I will explain how computable randomness is similar to and how it is different from other notions of randomness. Unlike other notions of randomness, computable randomness is closely linked to the Borel sigma-algebra of a space. This has a number of interesting implications:
However, this line of research still leaves many open questions about the nature of computable randomness and the nature of randomness in general. I believe the tools used to explore computable randomness may have other applications to algorithmic randomness and computable analysis. [1] Vasco Brattka, Joseph S. Miller, and André Nies. "Randomness and differentiability." Submitted. [2] Jason Rute. "Computable randomness and betting for computable probability spaces." In preparation. |
||||
18:00-18:30 | Welcome Drinks Reception |
Tuesday 3 July | ||||
09:00-10:00 | Simpson, S (Pennsylvania State University) | |||
Propagation of partial randomness | Sem 1 | |||
Let $X$ be an infinite sequence of $0$'s and $1$'s, i.e., $X\in\{0,1\}^\mathbb{N}$. Even if $X$ is not Martin-Löf random, we can nevertheless quantify the amount of partial randomness which is inherent in $X$. Many researchers including Calude, Hudelson, Kjos-Hanssen, Merkle, Miller, Reimann, Staiger, Tadaki, and Terwijn have studied partial randomness. We now present some new results due to Higuchi, Hudelson, Simpson and Yokoyama concerning propagation of partial randomness. Our results say that if $X$ has a specific amount of partial randomness, then $X$ has an equal amount of partial randomness relative to certain Turing oracles. More precisely, let $\mathrm{KA}$ denote a priori Kolmogorov complexity, i.e., $\mathrm{KA}(\sigma)=-\log_2m(\sigma)$ where $m$ is Levin's universal left-r.e. semimeasure. Note that $\mathrm{KA}$ is similar but not identical to the more familiar prefix-free Kolmogorov complexity. Given a computable function $f:\{0,1\}^*\to[0,\infty)$, we say that $X\in\{0,1\}^\mathbb{N}$ is strongly $f$-random if $\exists c\,\forall n\,(\mathrm{KA}(X{\upharpoonright}\{1,\ldots,n\})>f(X{\upharpoonright}\{1,\ldots,n\})-c)$. Two of our results read as follows. Theorem 1. Assume that $X$ is strongly $f$-random and Turing reducible to $Y$ where $Y$ is Martin-Löf random relative to $Z$. Then $X$ is strongly $f$-random relative to $Z$. Theorem 2. Assume that $\forall i\,(X_i$ is strongly $f_i$-random$)$. Then, we can find a $\mathrm{PA}$-oracle $Z$ such that $\forall i\,(X_i$ is strongly $f_i$-random relative to $Z)$. We also show that Theorems 1 and 2 fail badly with $\mathrm{KA}$ replaced by $\mathrm{KP}=$ prefix-free complexity. |
||||
10:00-10:30 | Cholak, P (University of Notre Dame) | |||
Computably enumerable partial orders | Sem 1 | |||
We study the degree spectra and reverse-mathematical applications of computably enumerable and co-computably enumerable partial orders. We formulate versions of the chain/antichain principle and ascending/descending sequence principle for such orders, and show that the latter is strictly stronger than the latter. We then show that every $\emptyset'$-computable structure (or even just of c.e. degree) has the same degree spectrum as some computably enumerable (co-c.e.) partial order, and hence that there is a c.e. (co-c.e.) partial order with spectrum equal to the set of nonzero degrees. A copy of the submitted paper can be found at http://www.nd.edu/~cholak/papers/ceorderings.pdf |
||||
10:30-11:00 | Morning coffee | |||
11:00-12:00 | Brattka, V (University of Cape Town) | |||
On the computational content of the Baire Category Theorem | Sem 1 | |||
We present results on the classification of the computational content of the Baire Category Theorem in the Weihrauch lattice. The Baire Category Theorem can be seen as a pigeonhole principle that states that a large (= complete) metric space cannot be decomposed into a countable number of small (= nowhere dense) pieces (= closed sets). The difficulty of the corresponding computational task depends on the logical form of the statement as well as on the information that is provided. In the first logical form the task is to find a point in the space that is left out by a given decomposition of the space that consists of small pieces. In the contrapositive form the task is to find a piece that is not small in a decomposition that exhausts the entire space. In both cases pieces can be given by descriptions in negative or positive form. We present a complete classification of the complexity of the Baire Category Theorem in all four cases and for certain types of spaces. The results are based on joint work with Guido Gherardi and Alberto Marcone, on the one hand, and Matthew Hendtlass and Alexander Kreuzer, on the other hand. One obtains a refinement of what is known in reverse mathematics in this way. [1] Vasco Brattka and Guido Gherardi. "Effective choice and boundedness principles in computable analysis." The Bulletin of Symbolic Logic, 17(1):73–117, 2011. [2] Vasco Brattka and Guido Gherardi. "Weihrauch degrees, omniscience principles and weak computability." The Journal of Symbolic Logic, 76(1):143–176, 2011. [3] Vasco Brattka, Guido Gherardi, and Alberto Marcone. "The Bolzano-Weierstrass theorem is the jump of weak KŐnig's lemma." Annals of Pure and Applied Logic, 163:623–655, 2012. [4] Vasco Brattka, Matthew Hendtlass, and Alexander P. Kreuzer. "On the Weihrauch complexity of computability theory." unpublished notes, 2012.
[5] Vasco Brattka.
"Computable versions of Baire's category theorem."
In Jiří Sgall, Aleš Pultr, and Petr Kolman, editors,
Mathematical Foundations of Computer Science 2001,
volume 2136 of Lecture Notes in Computer Science, pages 224–235, Berlin, 2001.
Springer. [6] Douglas K. Brown and Stephen G. Simpson. "The Baire category theorem in weak subsystems of second order arithmetic." The Journal of Symbolic Logic, 58:557–578, 1993. |
||||
12:00-12:30 | Porter, C (University of Notre Dame) | |||
Trivial measures are not so trivial | Sem 1 | |||
Although algorithmic randomness with respect to various biased computable measures is well-studied, little attention has been paid to algorithmic randomness with respect to computable trivial measures, where a measure $\mu$ on $2^\omega$ is trivial if the support of $\mu$ consists of a countable collection of sequences. In this talk, I will show that there is much more structure to trivial measures than has been previously suspected. In particular, I will outline the construction of
Lastly, I will show that, if we consider the class of $LR$-degrees associated with a trivial measure $\mu$ (generalizing the standard definition of the $LR$-degrees), then for every finite distributive lattice $\mathcal{L}=(L, \leq)$, there is a trivial measure $\mu$ such that the the collection of $LR$-degrees with respect to $\mu$ is a finite distributive lattice that is isomorphic to $\mathcal{L}$. |
||||
12:30-13:30 | Lunch at Wolfson Court | |||
14:00-15:00 | Hoyrup, M (INRIA Paris - Rocquencourt) | |||
On the inversion of computable functions | Sem 1 | |||
Ergodic shift-invariant measures inherit many effective properties of the uniform measure: for instance, the frequency of $1$'s in a typical sequence converge effectively, hence it converges at every Schnorr random sequence; the convergence is robust to small violations of randomness [1]; every Martin-Löf random sequence has a tail in every effective closed set of positive measure [2]. These properties are generally not satisfied by a non-ergodic measure, unless its (unique) decomposition into a combination of ergodic measures is effective. V'yugin [3] constructed a computable non-ergodic measure whose decomposition is not effective. This measure is a countable combination of ergodic measures. What happens for finite combinations? Is there a finitely but non-effectively decomposable measure? We prove that the answer is positive: there exist two non-computable ergodic measures $P$ and $Q$ such that $P+Q$ is computable. Moreover, the set of pairs $(P,Q)$ such that neither $P$ nor $Q$ is computable from $P+Q$ is large in the sense of Baire category. This result can be generalized into a theorem about the inversion of computable functions, which gives sufficient conditions on a one-to-one computable function $f$ that entail the existence of a non-computable $x$ such that $f(x)$ is computable. We also establish a stronger result ensuring the existence of a ``sufficiently generic'' $x$ such that $f(x)$ is computable, in the spirit of Ingrassia's notion of $p$-genericity [4]. [1] Vladimir V. V'yugin. "Non-robustness property of the individual ergodic theorem." Problems of Information Transmission, 37(2):27–39, 2001. [2] Laurent Bienvenu, Adam Day, Ilya Mezhirov, and Alexander Shen. "Ergodic-type characterizations of algorithmic randomness." In Computability in Europe (CIE 2010), volume 6158 of LNCS, pages 49–58. Springer, 2010. [3] Vladimir V. V'yugin. "Effective convergence in probability and an ergodic theorem for individual random sequences." SIAM Theory of Probability and Its Applications, 42(1):39–50, 1997. [4] M.A. Ingrassia. P-genericity for Recursively Enumerable Sets. University of Illinois at Urbana-Champaign, 1981. |
||||
15:00-15:30 | Herbert, I (University of California, Berkeley) | |||
(Almost) Lowness for K and finite self-information | Sem 1 | |||
A real $X$, is called low for K if there is a constant $c$ such that using $X$ as an oracle does not decrease the Kolmogorov complexity of any string by more than $c$. That is, the inequality $K(\sigma) \leq K^{X}(\sigma) +c$ holds for all $\sigma \in 2^{<\omega}$. One can relax this definition by replacing the constant with a slow growing function $f$ and one obtains reals that are `almost' low for $K$ `up to $f$'. It is not surprising that there are reals that are `almost' low for $K$ but not actually low for $K$, but the classes of reals that are 'almost' low for $K$ and those that are low for $K$ in the traditional sense can behave very differently. We will explain some of these results, and in particular discuss how they relate to one definition of mutual information. |
||||
15:30-16:00 | Afternoon Tea | |||
17:00-17:30 | Bauwens, B (Universidade do Porto) | |||
Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs | Sem 1 | |||
Joseph Miller[1] and independently Andre Nies, Frank Stephan and Sebastian Terwijn[2] gave a complexity characterization of $2$-random sequences in terms of plain Kolmogorov complexity $C\,(\cdot)$: they are sequences that have infinitely many initial segments with $O(1)$-maximal plain complexity (among the strings of the same length). Later Miller[3] (see also [4]) showed that prefix complexity $K\,(\cdot)$ can be also used in a similar way: a sequence is $2$-random if and only if it has infinitely many initial segments with $O(1)$-maximal prefix complexity (which is $n+K\,(n)$ for strings of length~$n$). The known proofs of these results are quite involved; we provide simple direct proofs for both of them. In [1] Miller also gave a quantitative version of the first result: the $0'$-randomness deficiency of a sequence $\omega$ equals $\liminf_n [n - C\,(\omega_1\dots\omega_n)] + O(1)$. (Our simplified proof also can be used to prove this quantitative version.) We show (and this seems to be a new result) that a similar quantitative result is true also for prefix complexity: $0'$-randomness deficiency $d^{0'}(\omega)$ equals also $\liminf_n [n + K\,(n) - K\,(\omega_1\dots\omega_n)]+ O(1)$. This completes the picture: \begin{eqnarray*} d^{0'}(\omega) &=& \sup_n \, \left[ n - K\,^{0'}(\omega_1\dots\omega_n) \right] + O(1) \\ &=& \liminf_n \, \left[ n - C\,(\omega_1\dots\omega_n) \right] + O(1) \\ &=& \liminf_n \, \left[ n + K\,(n) - K\,(\omega_1\dots\omega_n) \right] + O(1) \,. \end{eqnarray*} [1] J.S. Miller. "Every 2-random real is Kolmogorov random." Journal of Symbolic Logic, 69(3):907–913, 2004. [2] A. Nies, F. Stephan, and S.A. Terwijn. "Randomness, relativization and turing degrees." The Journal of Symbolic Logic, 70(2), 2005. [3] J.S. Miller. "The K-degrees, low for K-degrees, and weakly low for K sets." Notre Dame Journal of Formal Logic, 50(4):381–391, 2009. [4] R.G. Downey and D.R. Hirschfeldt. "Algorithmic Randomness and Complexity." Theory and Applications of Computability. Springer, 2010. |
||||
20:00-22:15 | "Codebreaker" movie |
Wednesday 4 July | ||||
09:00-10:00 | Hitchcock, J M (University of Wyoming) | |||
Limitations of Efficient Reducibility to the Kolmogorov Random Strings | Sem 1 | |||
10:00-10:30 | Zimand, M (Towson University) | |||
Language compression for sets in P/poly | Sem 1 | |||
If we consider a finite set $A$, it is desirable to represent every $x$ in $A$ by another shorter string compressed($x$) such that compressed($x$) describes unambiguously the initial $x$. Regarding the compression rate, ideally, one would like to achieve the information-theoretical bound |compressed($x$)| $\approx \log (|A|)$, for all $x$ in $A$. This optimal rate is achievable for c.e. (and also co-c.e.) sets $A$, because for such a set C($x$) $\leq \log (|A^{=n}|) + O(\log n)$ (C($x$) is the Kolmogorov complexity of string $x$ and $n$ is the length of $x$). In the time-bounded setting, we would like to have a polynomial-time type of unambiguous description. The relevant concept is the time-bounded distinguishing complexity, CD(), introduced by Sipser. The $t$-time bounded distinguishing complexity of $x$, denoted CD$^t(x)$ is the length of the shortest program $p$ that accepts $x$ and only $x$ within time $t(|x|)$. Recently we have shown that for sets in P, NP, PSPACE, optimal compression can be achieved, using some reasonable hardness assumptions. We show that this also holds for sets in P/poly, i.e., for sets computable by polynomial-size circuits. Furthermore, we sketch here a different proof method (even though some key elements are common) suggested by Vinodchandran, which needs a weaker hardness assumption. |
||||
10:30-11:00 | Morning Coffee | |||
11:00-12:00 | Koucky, M (Academy of Sciences of the Czech Republic) | |||
The story of superconcentrators – the missing link | Sem 1 | |||
In 60's and 70's directed graphs with strong connectivity property were linked to proving lower bounds on complexity of solving various computational problems. Graphs with strongest such property were named superconcentrators by Valiant (1975). An n-superconcentrator is a directed acyclic graph with n designated input nodes and n designated output nodes such that for any subset X of input nodes and any equal-sized set Y of output nodes there are |X| vertex disjoint paths connecting the sets. Contrary to previous conjectures Valiant showed that there are n-superconcentrators with O(n) edges thus killing the hope of using them to prove lower bounds on computation. His n-superconcentrators have depth O(log n). Despite this setback, superconcentrators found their way into lower bounds in the setting of bounded-depth circuits. They provide asymptotically optimal bounds for computing many functions including integer addition, and most recently computing good error-correctin g codes. The talk will provide an exposition of this fascinating area. |
||||
12:00-12:30 | Nguyen, D (University at Buffalo) | |||
Autoreducibility for NEXP | Sem 1 | |||
Autoreducibility was first introduced by Trakhtenbrot in a recursion theoretic setting. A set $A$ is autoreducible if there is an oracle Turing machine $M$ such that $A = L(M^A)$ and M never queries $x$ on input $x$. Ambos-Spies introduced the polynomial-time variant of autoreducibility, where we require the oracle Turing machine to run in polynomial time. The question of whether complete sets for various classes are polynomial-time autoreducible has been studied extensively. In some cases, it turns out that resolving autoreducibility can result in interesting complexity class separations. One question that remains open is whether all Turing complete sets for NEXP are Turing autoreducible. An important separation may result when solving the autoreducibility for NEXP; if there is one Turing complete set of NEXP that is not Turing autoreducible, then EXP is different from NEXP. We do not know whether proving all Turing complete sets of NEXP are Turing autoreducible yields any separation results. Buhrman et al. showed that all ${\le_{\mathit{2\mbox{-}tt}}^{\mathit{p}}}$-complete sets for EXP are ${\le_{\mathit{2\mbox{-}tt}}^{\mathit{p}}}$-autoreducible. This proof technique exploits the fact that EXP is closed under exponential-time reductions that only ask one query that is smaller in length. Difficulties arise when we want to prove that the above result holds for NEXP, because we do not know whether this property still holds for NEXP. To resolve that difficulty, we use a nondeterministic technique that applies to NEXP and obtain the similar result for NEXP; that is, all ${\le_{\mathit{2\mbox{-}tt}}^{\mathit{p}}}$-complete sets for NEXP are ${\le_{\mathit{2\mbox{-}tt}}^{\mathit{p}}}$-autoreducible. Using similar techniques, we can also show that every disjunctive and conjunctive truth-table complete set for NEXP is disjunctive and conjunctive truth-table autoreducible respectively. In addition to those positive results, negative ones are also given. Using different notions of reductions, we can show that there is a complete set for NEXP that is not autoreducible. Finally, in the relativized world, there is a ${\le_{\mathit{2\mbox{-}T}}^{\mathit{p}}}$-complete set for NEXP that is not Turing autoreducible. |
||||
12:30-13:30 | Lunch at Wolfson Court | |||
13:30-17:00 | Excursion | |||
19:30-22:00 | Conference Dinner at Emmanuel College |
Thursday 5 July | ||||
09:00-10:00 | Turetsky, D (Victoria University of Wellington) | |||
SJT-hardness and pseudo-jump inversion | Sem 1 | |||
Tracing was introduced to computability theory by Terwijn and Zambella, who used it to characterize the degrees which are low for Schnorr randomness. Zambella observed that tracing also has a relationship to K-triviality, which was strengthened by Nies and then later others. A trace for a partial function f is a sequence of finite sets (T_z) with f(z) in T_z for all z in the domain of f. A trace (T_z) is c.e. if the T_z are uniformly c.e. sets. An order function is a total, nondecreasing, unbounded positive function. If h is an order, a trace (T_z) is an h-trace if h(z) bounds the size of T_z. A set is called jump-traceable (JT) if every partial function it computes has a c.e. h-trace for some computable order h. A set is called strongly jump-traceable (SJT) if every partial function it computes has a c.e. h-trace for every computable order h. Figuiera et al. constructed a non-computable c.e. set which is SJT. This gives a natural pseudo-jump operator. Pseudo-jump inverting this SJT-operator gives a set A such that the halting problem looks SJT relative to A. That is, for every partial function computable from the halting problem, and every computable order h, there is an h-trace which is uniformly c.e. relative to A. Such a set is called SJT-hard. Downey and Greenberg showed that there is a non-computable c.e. set E which is computable from every c.e. SJT-hard set. Thus the SJT-operator cannot be pseudo-jump inverted outside of the cone above E. We strengthen this result, showing that E can be made super high. |
||||
10:00-10:30 | Teutsch, J (Pennsylvania State University) | |||
Translating the Cantor set by a random | Sem 1 | |||
I will discuss the constructive dimension of points in random translates of the Cantor set. The Cantor set ``cancels randomness'' in the sense that some of its members, when added to Martin-Löf random reals, identify a point with lower constructive dimension than the random itself. In particular, we find the Hausdorff dimension of the set of points in a Cantor set translate with a given constructive dimension. More specifically, let $\mathcal{C}$ denote the standard middle third Cantor set, and for each real $\alpha$ let $\mathcal{E}_{\alpha}$ consist of all real numbers with constructive dimension $\alpha$. Our result is the following.
If $1 -\log2/\log3 \leq \alpha \leq 1$ and $r$ is a Martin-Löf random real, then the Hausdorff dimension of the set $ (\mathcal{C}+r) \cap \mathcal{E}_{\alpha}$ is $\alpha -(1 -\log 2/\log 3)$. From this theorem we obtain a simple relation between the effective and classical Hausdorff dimensions of this set; the difference is exactly $1$ minus the dimension of the Cantor set. We conclude that many points in the Cantor set additively cancel randomness. On the surface, the theorem above describes a connection between algorithmic randomness and classical fractal geometry. Less obvious is its relationship to additive number theory. In 1954, G. G. Lorentz proved the following statement.
There exists a constant $c$ such that for any integer $k$, if $A\subseteq [0, k)$ is a set of integers with ${\left|A\right|} \geq \ell \geq 2$, then there exists a set of integers $B \subseteq (-k,k)$ such that $A + B \supseteq [0, k)$ with ${\left|B\right|} \leq ck\frac{\log \ell}{\ell}$. Given a Martin-Löf random real $r$, I will show how Lorentz's Lemma can be used to identify a point $x\in\mathcal{C}$ such that the constructive dimension of $x+r$ is close to $1 - \log 2 / \log 3$, which is as small as it can possibly be. This talk is based on joint work with Randy Dougherty, Jack Lutz, and Dan Mauldin. |
||||
10:30-11:00 | Morning Coffee | |||
11:00-12:00 | Barmpalias, G (Chinese Academy of Sciences) | |||
Exact pairs for the ideal of the $K$-trivial sequences in the Turing degrees | Sem 1 | |||
The $K$-trivial sets form an ideal in the Turing degrees, which is generated by its computably enumerable (c.e.) members and has an exact pair below the degree of the halting problem. The question of whether it has an exact pair in the c.e. degrees was first raised in a published list of questions in the Bulletin of Symbolic Logic in 2006 by Miller and Nies and later in Nies' book on computability and randomness. Moreover it was featured in several conferences in algorithmic randomness, since 2005. We give a negative answer to this question. In fact, we show the following stronger statement in the c.e. degrees. There exists a $K$-trivial degree $\mathbf{d}$ such that for all degrees $\mathbf{a}, \mathbf{b}$ which are not $K$-trivial and $\mathbf{a}>\mathbf{d}, \mathbf{b}>\mathbf{d}$ there exists a degree $\mathbf{v}$ which is not $K$-trivial and $\mathbf{a}>\mathbf{v}, \mathbf{b}>\mathbf{v}$. This work sheds light to the question of the definability of the $K$-trivial degrees in the c.e. degrees. |
||||
12:00-12:30 | Heiber, P A (Universidad de Buenos Aires) | |||
Normality and Differentiability | Sem 1 | |||
By transferring to the world of functions computable by finite automata the classical theorem of numerical analysis establishing that every non-decreasing real valued function is almost everywhere differentiable, we obtain a characterization of the property of Borel normality. We consider functions mapping infinite sequences to infinite sequences and a notion of differentiability that, on the class of non-decreasing real valued functions, coincides with standard differentiability. We prove that the following are equivalent, for a real x in [0,1]: (1) x is normal to base b. (2) Every non-decreasing function computable by a finite automaton mapping infinite sequences to infinite sequences is differentiable at the expansion of x in base b. (3) Every non-decreasing function computable by a finite automaton in base b mapping real numbers to real numbers is differentiable at x. Joint work with Verónica Becher, Universidad de Buenos Aires. |
||||
12:30-13:30 | Lunch at Wolfson Court | |||
14:00-14:30 | Fouche, W (University of South Africa) | |||
Kolmogorov complexity and Fourier aspects of Brownian motion | Sem 1 | |||
It is well-known that the notion of randomness, suitably refined, goes a long way in dealing with the tension between the ``incompatability of shortest descriptions and of effecting the most-economical algorithmical processing" Manin(2006). In this work, we continue to explore this interplay between short descriptions and randomness in the context of Brownian motion and its associated geometry. In this way one sees how random phenomena associated with the geometry of Brownian motion, are implicitly enfolded in each real number which is complex in the sense of Kolmogorov. These random phenomena range from fractal geometry, Fourier analysis and non-classical noises in quantum physics. In this talk we shall discuss countable dense random sets as the appear in the theory of Brownian motion in the context of algorithmic randomness. We shall also discuss applications to Fourier analysis. In particular, we also discuss the images of certain $\Pi_2^0$ perfect sets of Hausdorff dimension zero under a complex oscillation (which is also known as an algorithmically random Brownian motion). This opens the way to relate certain non-classical noises to Kolmogorov complexity. For example, the work of the present work enables one to represent Warren's splitting noise directly in terms of infinite binary strings which are Kolmogorov-Chaitin-Martin-Löf random. |
||||
14:30-15:00 | Franklin, J (University of Connecticut) | |||
Ergodic theory and strong randomness notions | Sem 1 | |||
There has been a great deal of interest recently in the connection between algorithmic randomness and ergodic theory, which naturally leads to the question of how much one can say if the transformations in question need not be ergodic. We have essentially reversed a result of V'yugin and shown that if an element of the Cantor space is not Martin-Löf random, then there is a computable function and a computable transformation for which this element is not typical with respect to the ergodic theorem. More recently, we have shown that every weakly 2-random element of the Cantor space is typical with respect to the ergodic theorem for every lower semicomputable function and computable transformation. I will explain the proof of the latter result and discuss the technical difficulties present in producing a full characterization. |
||||
15:00-15:30 | Reznikova, Z (Novosibirsk State University) | |||
Integration of ideas and methods of Kolmogorov Complexity and classical mathematical statistics | Sem 1 | |||
A new approach is suggested which allows to combine the advantages of methods based on Kolmogorov complexity with classical methods of testing of statistical hypotheses. As distinct from other approaches to analysis of different sequences by means of Kolmogorov complexity, we stay within the framework of mathematical statistics. As examples, we consider behavioural sequences of animals (ethological ``texts'') testing the hypotheses whether the complexity of hunting behaviour in ants and rodents depends on the age of an individual. |
||||
15:30-16:00 | Afternoon Tea | |||
17:00-17:30 | Ryabko, D (INRIA, Lille, France) | |||
Limit capacity of non-stochastic steganographic systems and Hausdorff dimension | Sem 1 | |||
It was shown recently that the limit capacity of perfect steganography systems for i.i.d. and Markov sources equals the Shannon entropy of the ``cover'' process. Here we address the problem of limit capacity of general perfect steganographic systems. We show that this value asymptotically equals the Hausdorff dimension of the set of possible cover messages. |
Friday 6 July | ||||
10:00-10:30 | Tadaki, K (Chuo University) | |||
Cryptography and Algorithmic Randomness | Sem 1 | |||
In modern cryptography, the random oracle model is widely used as an imaginary framework in which the security of a cryptographic scheme is discussed. In the random oracle model, the cryptographic hash function used in a cryptographic scheme is formulated as a random variable uniformly distributed over all possibility of the function, called the random oracle, and the legitimate users and the adversary against the scheme are modeled so as to get the values of the hash function not by evaluating it in their own but by querying the random oracle. Since the random oracle is an imaginary object, even if the security of a cryptographic scheme is proved in the random oracle model, the random oracle has to be instantiated using a concrete cryptographic hash function such as the SHA hash functions if we want to use the scheme in the real world. However, it is not clear how much the instantiation can maintain the security originally proved in the random oracle model, nor is it clear w hether the random oracle can be instantiated somehow while keeping the original security. In the present talk we investigate this problem using concepts and methods of algorithmic randomness. Our results use the general form of definitions of security notions for cryptographic schemes, and depend neither on specific schemes nor on specific security notions. |
||||
10:30-11:00 | Morning Coffee | |||
11:00-12:00 | Lewis, A (University of Leeds) | |||
The typical Turing degree | Sem 1 | |||
Since Turing degrees are tailsets, it follows from Kolmogorov's 0-1 law that for any property which may or may not be satisfied by any given Turing degree, the satisfying class will either be of Lebesgue measure 0 or 1, so long as it is measurable. So either the typical degree satisfies the property, or else the typical degree satisfies its negation. Further, there is then some level of randomness sufficient to ensure typicality in this regard. I shall describe a number of results in a largely new programme of research which aims to establish the (order theoretically) definable properties of the typical Turing degree, and the level of randomness required in order to guarantee typicality. A similar analysis can be made in terms of Baire category, where a standard form of genericity now plays the role that randomness plays in the context of measure. This case has been fairly extensively examined in the previous literature. I shall analyse how our new results for the measure theoretic case contrast with existing results for Baire category, and also provide some new results for the category theoretic analysis. This is joint work with George Barmpalias and Adam Day. |
||||
12:00-12:30 | Takahashi, H (University of Electro-Communications, Tokyo) | |||
Algorithmic randomness and stochastic selection function | Sem 1 | |||
For $x=x_1x_2\cdots,y=y_1y_2\cdots\in\{0,1\}^\infty$, let $x^n:=x_1\cdots x_n$ and $x/y:=x_{\tau(1)}x_{\tau(2)}\cdots$ where $\{i\mid y_i=1\}=\{\tau(1)<\tau(2)<\cdots\}$. Our first problem is to identify Martin-Löf randomness of $x$ in terms of randomness of subsequences $x/y$ for some finite set of selection functions $y$. This is trivial if we allow $y=s1^\infty$ for any finite string $s$, where $1^\infty$ is the sequence of 1's. In the following, we say that a selection function is non-trivial if it contains infinitely many 1's and 0's. Let ${\cal R}^P$ be the set of Martin-Löf random sequences w.r.t. a computable probability $P$ on $\{0,1\}^\infty$. The following two statements are equivalent.
The author do not know whether we can drop the assumption that $x$ is random w.r.t. some computable probability in (ii), i.e., whether we can replace (ii) with $x/y\in R^u$ for $y\in Y^x$ where $Y^x$ consists of non-trivial selection functions and depends on $x$. We also have a similar algorithmic analogy for Steinhause theorem [1]. Let $w$ be a computable probability such that
Then the following two statements are equivalent.
For example, $w:=\int P_\rho d\rho$, where $P_\rho$ is a probability derived from irrational rotation with parameter $\rho$, satisfies the condition of Prop. 2, see [2]. There are similar algorithmic analogies for Kamae's theorem [4], see [3]. [1] H. Steinhaus. "Les probabilités dénombrables et leur rapport à la théorie de la meésure." Fund. Math., 4:286–310, 1922. [2] H. Takahashi and K. Aihara. "Algorithmic analysis of irrational rotations in a sigle neuron model." J. Complexity, 19:132–152, 2003. [3] H. Takahashi. "Algorithmic analogies to Kamae-Weiss theorem on normal numbers." In Solomonoff 85th memorial conference. To appear in LNAI. [4] T. Kamae. "Subsequences of normal numbers." Israel J. Math., 16:121–149, 1973. |
||||
12:30-13:30 | Lunch at Wolfson Court | |||
14:00-15:00 | Day, A (University of California, Berkeley) | |||
Cupping with random sets | Sem 1 | |||
A set $X$ is ML-cuppable if there exists an incomplete Martin-Löf random $R$ that joins $X$ to zero jump. It is weakly ML-cuppable if there exists an incomplete Martin-Löf random $R$ that joins $X$ above zero jump. We prove that a set is K-trivial if and only if it is not weakly ML-cuppable. Further, we show that a set below zero jump is K-trivial if and only if it is not ML-cuppable. These results settle a question of Kučera, who introduced both cuppability notions. This is joint work with Joseph S. Miller. |
||||
15:30-16:00 | Afternoon Tea | |||
16:00-17:00 | Downey, R (Victoria University of Wellington) | |||
Resolute sets and initial segment complexity | Sem 1 | |||
Notions of triviality have been remarkably productive in algorithmic randomness,with $K$-triviality being the most notable. Of course, ever since the original characterization of Martin-Löf randomness by initial segment complexity, there has been a longstanding interplay between initial segment complexity and calibrations of randomness, as witnessed by concepts such as autocomplexity, and the like. In this talk I wish to discuss recent work with George Barmpalias on a triviality notion we call resoluteness. Resoluteness is defined in terms of computable shifts by is intimately related to a notion we call weak resoluteness where $A$ is weakly resolute iff for all computable orders $h$, $K(A\uparrow n) \ge^+ K(A\uparrow h(n)), $ for all $n$. It is not difficult to see that $K$-trivials have this property but it turns out that there are uncountablly many degrees which are completely $K$-resolute, and there are c.e. degrees also with this property. These degrees seem related to Lathrop-Lutz ultracompressible degrees. Our investigations are only just beginning and I will report on our progress. Joint work with George Barmpalias. |