CCR 2012: 7th Conference on Computability, Complexity and Randomness
09:00 to 09:25 
Registration  
09:25 to 09:30 
Welcome  INI 1  
09:30 to 10:30 
J Lutz (Iowa State University) Alan Turing in the twentyfirst century: normal numbers, randomness, and finite automata
We discuss ways in which Turing's thenunpublished ``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. 
INI 1  
10:30 to 11:00 
Morning coffee  
11:00 to 12:00 
A Nies (University of Auckland) Demuth randomness and its variants
A Demuth test is like a MartinLö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., MLrandomness 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 BLRtraceability, 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 Ktrivial 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'' Ktrivial set $A$: it is difficult to cover in that any MartinLöf random set $Y$ above $A$ must be LRhard. [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. 
INI 1  
12:00 to 12:30 
S Sanders (Universiteit Gent) Nonstandard Analysis: a new way to compute
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 spinoff 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. 
INI 1  
12:30 to 13:30 
Lunch at Wolfson Court.  
14:00 to 15:00 
A Shen (Université de Montpellier 2) Topological arguments in Kolmogorov complexity
We show how topological arguments (simple facts about nonhomotopic 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(xy) and C(yx) are equal to n+O(1).
See also: http://arxiv.org/abs/1206.4927 
INI 1  
15:00 to 15:30 
K Miyabe (Kyoto University) Schnorr triviality is equivalent to being a basis for ttSchnorr randomness
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 prefixfree machine,
we also have a characterization of Schnorr triviality using complexity
via a decidable prefixfree 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 truthtable reducible to any Schnorr random set.

INI 1  
15:30 to 16:00 
Afternoon tea  
17:00 to 17:30 
T Petrovic (University of Zagreb) Two betting strategies that predict all compressible sequences
A new type of betting games that charaterize MartinLöf randomness
is introduced. These betting games can be compared to martingale
processes of Hitchcock and Lutz as well as nonmonotonic betting
strategies. Sequenceset betting is defined as successive betting on
prefixfree sets that contain a finite number of words. In each iteration
we start with an initial prefixfree set $P$ and an initial capital
$c$, then we divide $P$ into two prefixfree 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 prefixfree set contains the empty string. The
player succeeds on the infinite sequence if the series of bets increases
capital unboundedly. Nonmonotonic betting can be viewed as sequenceset
betting with an additional requirement that the initial prefixfree set
is divided into two prefixfree 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 prefixfree set
$P$ is divided into two prefixfree 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 sequenceset betting strategy there is an infinite
sequence on which betting strategy doesn't succeed and which is not
MartinLöf random. Furthermore it is shown that there is an algorithm
that constructs two sets of betting decisions for two sequenceset
betting strategies such that for any sequence that is not MartinLöf
random at least one of them succeeds on that sequence.

INI 1  
17:30 to 18:00 
J Rute (Carnegie Mellon University) Computable randomness and its properties
Computable randomness at first does not seem as natural of a randomness
notion as Schnorr and MartinLö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 sigmaalgebra 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. 
INI 1  
18:00 to 18:30 
Welcome Drinks Reception 
09:00 to 10:00 
S Simpson (Pennsylvania State University) Propagation of partial randomness
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 MartinLöf random,
we can nevertheless quantify the amount of partial randomness
which is inherent in $X$. Many researchers including Calude,
Hudelson, KjosHanssen, 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 leftr.e. semimeasure. Note that
$\mathrm{KA}$ is similar but not identical to the more familiar
prefixfree 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 MartinLö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}=$ prefixfree complexity. 
INI 1  
10:00 to 10:30 
P Cholak (University of Notre Dame) Computably enumerable partial orders
We study the degree spectra and reversemathematical applications
of computably enumerable and cocomputably 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 (coc.e.) partial order, and hence that there is a
c.e. (coc.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 
INI 1  
10:30 to 11:00 
Morning coffee  
11:00 to 12:00 
V Brattka (University of Cape Town) On the computational content of the Baire Category Theorem
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 BolzanoWeierstrass 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. 
INI 1  
12:00 to 12:30 
C Porter (University of Notre Dame) Trivial measures are not so trivial
Although algorithmic randomness with respect to various biased computable
measures is wellstudied, 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}$. 
INI 1  
12:30 to 13:30 
Lunch at Wolfson Court  
14:00 to 15:00 
M Hoyrup (INRIA Paris  Rocquencourt) On the inversion of computable functions
Ergodic shiftinvariant 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 MartinLöf random sequence has a tail in every
effective closed set of positive measure [2]. These
properties are generally not satisfied by a nonergodic measure, unless
its (unique) decomposition into a combination of ergodic measures is
effective. V'yugin [3] constructed a computable nonergodic
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 noneffectively decomposable measure?
We prove that the answer is positive: there exist two noncomputable 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 onetoone computable function $f$ that entail the existence of a noncomputable $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. "Nonrobustness 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. "Ergodictype 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. Pgenericity for Recursively Enumerable Sets. University of Illinois at UrbanaChampaign, 1981. 
INI 1  
15:00 to 15:30 
I Herbert (University of California, Berkeley) (Almost) Lowness for K and finite selfinformation
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^{

INI 1  
15:30 to 16:00 
Afternoon Tea  
17:00 to 17:30 
B Bauwens (Universidade do Porto) Prefix and plain Kolmogorov complexity characterizations of 2randomness: simple proofs
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 2random 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 Kdegrees, low for Kdegrees, 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. 
INI 1  
20:00 to 22:15 
Codebreaker movie  INI 1 
09:00 to 10:00 
J M Hitchcock (University of Wyoming) Limitations of Efficient Reducibility to the Kolmogorov Random Strings 
INI 1  
10:00 to 10:30 
M Zimand (Towson University) Language compression for sets in P/poly
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
informationtheoretical bound compressed($x$) $\approx \log (A)$,
for all $x$ in $A$. This optimal rate is achievable for c.e. (and also
coc.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 timebounded setting, we would like to have
a polynomialtime type of unambiguous description. The relevant concept
is the timebounded 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 polynomialsize
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.

INI 1  
10:30 to 11:00 
Morning Coffee  
11:00 to 12:00 
M Koucky (Academy of Sciences of the Czech Republic) The story of superconcentrators – the missing link
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 nsuperconcentrator 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 equalsized set Y of output nodes there are X vertex disjoint paths connecting the sets. Contrary to previous conjectures Valiant showed that there are nsuperconcentrators with O(n) edges thus killing the hope of using them to prove lower bounds on computation. His nsuperconcentrators have depth O(log n). Despite this setback, superconcentrators found their way into lower bounds in the setting of boundeddepth circuits. They provide asymptotically optimal bounds for computing many functions including integer addition, and most recently computing good errorcorrectin g codes. The talk will provide an exposition of this fascinating area.

INI 1  
12:00 to 12:30 
D Nguyen (University at Buffalo) Autoreducibility for NEXP
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$. AmbosSpies introduced the polynomialtime 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 polynomialtime 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 exponentialtime 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 truthtable complete set for NEXP is disjunctive and conjunctive truthtable 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. 
INI 1  
12:30 to 13:30 
Lunch at Wolfson Court  
13:30 to 17:00 
Excursion  
19:30 to 22:00 
Conference Dinner at Emmanuel College 
09:00 to 10:00 
D Turetsky (Victoria University of Wellington) SJThardness and pseudojump inversion
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 Ktriviality, 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 htrace if h(z) bounds the size of T_z.
A set is called jumptraceable (JT) if every partial function it computes has a c.e. htrace for some computable order h. A set is called strongly jumptraceable (SJT) if every partial function it computes has a c.e. htrace for every computable order h.
Figuiera et al. constructed a noncomputable c.e. set which is SJT. This gives a natural pseudojump operator. Pseudojump inverting this SJToperator 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 htrace which is uniformly c.e. relative to A. Such a set is called SJThard.
Downey and Greenberg showed that there is a noncomputable c.e. set E which is computable from every c.e. SJThard set. Thus the SJToperator cannot be pseudojump inverted outside of the cone above E. We strengthen this result, showing that E can be made super high.

INI 1  
10:00 to 10:30 
J Teutsch (Pennsylvania State University) Translating the Cantor set by a random
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 MartinLö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 MartinLö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 ${\leftA\right} \geq \ell \geq 2$, then there exists a set of integers $B \subseteq (k,k)$ such that $A + B \supseteq [0, k)$ with ${\leftB\right} \leq ck\frac{\log \ell}{\ell}$. Given a MartinLö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. 
INI 1  
10:30 to 11:00 
Morning Coffee  
11:00 to 12:00 
G Barmpalias (Chinese Academy of Sciences) Exact pairs for the ideal of the $K$trivial sequences in the Turing degrees
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. 
INI 1  
12:00 to 12:30 
P A Heiber (Universidad de Buenos Aires) Normality and Differentiability
By transferring to the world of functions computable by finite automata the classical theorem of numerical analysis establishing that every nondecreasing 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 nondecreasing 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 nondecreasing function computable by a finite automaton mapping infinite sequences to infinite sequences is differentiable at the expansion of x in base b. (3) Every nondecreasing 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. 
INI 1  
12:30 to 13:30 
Lunch at Wolfson Court  
14:00 to 14:30 
W Fouche (University of South Africa) Kolmogorov complexity and Fourier aspects of Brownian motion
It is wellknown 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 mosteconomical 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 nonclassical 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 nonclassical 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 KolmogorovChaitinMartinLöf random.

INI 1  
14:30 to 15:00 
J Franklin (University of Connecticut) Ergodic theory and strong randomness notions
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 MartinLö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 2random 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.

INI 1  
15:00 to 15:30 
Z Reznikova (Novosibirsk State University) Integration of ideas and methods of Kolmogorov Complexity and classical mathematical statistics
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.

INI 1  
15:30 to 16:00 
Afternoon Tea  
17:00 to 17:30 
D Ryabko ([INRIA, Lille, France]) Limit capacity of nonstochastic steganographic systems and Hausdorff dimension
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.

INI 1 
10:00 to 10:30 
K Tadaki (Chuo University) Cryptography and Algorithmic Randomness
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.

INI 1  
10:30 to 11:00 
Morning Coffee  
11:00 to 12:00 
A Lewis (University of Leeds) The typical Turing degree
Since Turing degrees are tailsets, it follows from Kolmogorov's 01 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. 
INI 1  
12:00 to 12:30 
H Takahashi ([University of ElectroCommunications, Tokyo]) Algorithmic randomness and stochastic selection function
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)
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 nontrivial 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 KamaeWeiss 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. 
INI 1  
12:30 to 13:30 
Lunch at Wolfson Court  
14:00 to 15:00 
A Day (University of California, Berkeley) Cupping with random sets
A set $X$ is MLcuppable if there exists an incomplete MartinLöf
random $R$ that joins $X$ to zero jump. It is weakly MLcuppable if
there exists an incomplete MartinLöf random $R$ that joins $X$
above zero jump. We prove that a set is Ktrivial if and only if it is
not weakly MLcuppable. Further, we show that a set below zero jump is
Ktrivial if and only if it is not MLcuppable. These results settle a
question of Kučera, who introduced both cuppability notions. This
is joint work with Joseph S. Miller.

INI 1  
15:30 to 16:00 
Afternoon Tea  
16:00 to 17:00 
R Downey (Victoria University of Wellington) Resolute sets and initial segment complexity
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 MartinLö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 LathropLutz ultracompressible degrees.
Our investigations are only just beginning and I will report on our progress.
Joint work with George Barmpalias.

INI 1 