7 Sep (Sunday)
- 15:00 ? Hotel check-in (early check-in from 12:00 is negotiable if informed in advance)
- 19:00 – 21:00 Welcome Banquet
8 Sep (Monday)
- 7:30 – 9:00 Breakfast
- 9:00 – 9:10 Introductory film on the NII Shonan
- 9:00 – 12:00 Session on computability and algorithmic randomness
Joseph S. Miller, UW-Madison
Randomness relative to an enumeration oracle
Abstract: We initiate the study of algorithmic randomness relative to an enumeration oracle. Most of the notions in algorithmic randomness, and all of those most closely related to Martin-Löf randomness, can be expressed in terms of c.e. sets. So when we relativize these notions to an oracle X, we are usually interested in the X-c.e. sets, rather than the X-computable sets. Generalizing from Turing degrees to enumeration degrees should be straightforward: to relativize a randomness notion to the enumeration degree of a set A we simply replace “X-c.e.” with “c.e. in every enumeration of A” (i.e., enumeration reducible to A). The resulting definitions are easily seen to be unchanged for the total degrees (the range of the Turing degrees under their natural embedding into the enumeration degrees). For nontotal degrees, we find that some familiar theorems are preserved, perhaps with more subtle proofs, while other theorems may fail. For example, there need not be a universal Martin-Löf test relative to the enumeration degree of A, and there are continuum many enumeration degrees that are low for randomness. These and other facts follow from studying specific classes of enumeration degrees; unsurprisingly, properties of an enumeration degree are reflected in the behavior of randomness notions relative to that degree.
This work is joint with Mariya Soskova.
Keng Meng Ng, NTU
Diamond embeddings and minimal pairs in the r.e. truth table degrees
Abstract: We present some recent and old results on minimal pairs in the r.e. truth table degrees. Jockusch and Mohrherr showed that the diamond lattice {a,b,0,1} can be embedded in the r.e. truth table degrees preserving the top and bottom elements. We discuss related results about the possible degrees of a and b. We also discuss how to use the determinacy of finite games to construct minimal pairs in the r.e. truth table degrees.
George Barmpalias, Victoria U, Wellington
Open problems on reducibilities in Algorithmic randomness
This talk is based on my recent BSL paper on the topic. I will
present the state-of-the art of measures of relative randomness as reducibilities
measuring randomness and related concepts.
- 12:30 – 14:00 Lunch
- 14:00 – 16:00 Informal discussion session
- 18:00 – 19:30 Dinner
9 Sep (Tuesday)
- 7:30 – 9:00 Breakfast
- 9:00 – 12:00 Session on Entropy and Ergodic theory
Johanna Franklin, Hofstra University
Techniques in randomness and ergodic theory
Abstract: Many different results concerning the relationship between algorithmic randomness and effective ergodic theory have been proven in recent years. In this talk, I’ll survey the approaches that have been taken and the results from classical ergodic theory that have been used in the proofs of these results, focusing on my own work with Towsner and the method of cutting and stacking.
Satyadev Nandakumar, IIT Kanpur
Effective Kolmogorov-Sinai and Topological Entropy
Abstract: Symbolic dynamics is a useful approach for generalizing theorems in a symbolic setting to general settings of the dynamics of measure-preserving maps on metric spaces. We give an exposition on two important notions of complexity in symbolic dynamics, viz. the notion of Kolmogorov-Sinai entropy and topological entropy, and the connection between the two via the Variational Principle. Moreover these notions of entropy can also be a tool for the classification of dynamical systems – if two measure-preserving dynamical systems have a measure-preserving isomorphism between them, then they have the same Kolmogorov-Sinai entropy.
We give an overview of effectivizations of these notion, by Brudno, White, and by Galotolo, Hoyrup and Rojas, in terms of the complexity of orbits of Martin-Lof random objects in effective dynamical systems. We also explain the completeness of Kolmogorov-Sinai entropy as an invariant, in the context of Bernoulli systems – that is, two Bernoulli Systems are isomorphic if and only if they have the same KS entropy. We explain a recent attempt at the effectivization of this result, and suggest currently open areas of research.
Jan Reimann
Effektive Multifractals und Renyi-Entropy
Abstract: Multifractal measures play an important role in the study of point
processes and strange attractors. A central component of the theory is
the multifractal formalism, which connects local properties of a measure
(pointwise dimensions) with its global properties (average scaling
behavior).
I will introduce a new, effective multifractal spectrum,
where one replaces pointwise dimension by asymptotic compression ratio. It
turns out that the underlying measure can be seen as a universal object
for the multifractal analysis of computable measures. The multifractal
spectrum of a computable measure can be expressed as a “deficiency of
multifractality” spectrum with respect to the universal measure.
This in turn allows for developing a quantitative theory of dimension
estimators based on Kolmogorov complexity. I will discuss some
applications to seismological dynamics.
- 12:30 – 14:00 Lunch
- 14:00 – 16:00 Informal discussion session
- 18:00 – 19:30 Dinner
10 Sep (Wednesday)
- 7:30 – 9:00 Breakfast
- 9:00 – 12:00 Session on computational complexity and descriptive string complexity
at most 45 min each talk
Eric Allender
The Minimum Circuit Size Problem, and Kolmogorov Complexity
Abstract: The Minimum Circuit Size Problem (MCSP) is a well-known example of a set
in NP that is not known (or widely believed) to be NP-complete, although
it appears to be intractable. It has recently been shown to be hard for
the complexity class SZK (Statistical Zero Knowledge).
MCSP is closely related to the set R_KT — the set of KT-random strings
(where KT is a type of time-bounded Kolmogorov complexity). The
MCSP-hardness result also holds for a “promise problem” version of R_KT:
The yes instances consisting of all x such that KT(x) > |x|-1.
The no instances consisting of all x such that KT(x) < |x|/2.
Investigating the “promise problem” version of the sets reducible to R_K
may lead to improved connections between complexity theory and the study
of K-randomness (such as attempts to characterize classes such as NEXP
and BPP in terms of efficient reductions to R_K.
Akitoshi Kawamura Tokyo University
Sets efficiently reducible to Kolmogorov randomness
Abstract: Allender, Friedman, and Gasarch proved an upper bound of PSPACE for
the class DTTR of decidable languages that are polynomial-time
truth-table reducible to the set of prefix-free Kolmogorov-random
strings regardless of the universal machine used in the definition of
Kolmogorov complexity. It is conjectured that DTTR in fact lies
closer to BPP, a lower bound established earlier by Buhrman, Fortnow,
Koucky, and Loff. It is also conjectured that we have similar bounds
for the analogous class defined by plain Kolmogorov randomness. We
discuss how these conjectures become more plausible when we impose
restrictions on the lengths of the queries asked in the reduction.
(Based on joint work with Shuichi Hirahara presented at MFCS 2014.)
Frank Stephan, NUS
Bennett deep sequences in recursion theory
Abstract: Logical depth measures the depth of a set, identified with its
characteristic function, in terms of how much normal Kolmogorov complexity
improves with respect to any resource-bounded versin of it. These notions
can be based on the prefix-free and the plain Kolmogorov complexity and
the results are in both cases different. While for prefix-free Kolmogorov
complexity, there is a strong connection between logical depth and
truth-table reducibility, such a connection fails for plain Kolmogorov
complexity even with respect to many-one reducibility. The talk highlights
various recursion-theoretic properties of sets which have a close connection
to logical depth.
- 12:00 – 13:30 Lunch
- 13:30 – 19:00 Excursion
- 19:00 – 20:30 Main Banquet
11 Sep (Thursday)
- 7:30 – 9:00 Breakfast
- 9:00 – 12:00 Session on generic case
complexity
R. Downey , Victoria Univ Wellington.
Introduction to generic case
complexity.
L. Bienvenu , CNRS and University Paris 7.
Coarse and generic computability of the halting problem
Abstract: Most of the current research on coarse and generic computability looks at approximability of sets by computable sets w.r.t. lower density. I will discuss a few results on approximability of the halting problem (properly formulated) when upper density is used instead. (joint work with Damien Desfontaines and Alexander Shen).
- 12:30 – 14:00 Lunch
- 14:00 – 16:00 Informal discussion session
- 18:00 – 19:30 Dinner
- 19:30 -20ish Discussion on Journal editing (near lounge)
12 Sep (Friday)
- 7:30 – 9:00 Breakfast
- 10:00 Mushfeq Khan, University of Hawai’i
Lebesgue density and effectively closed sets
Analyzing the effective content of the Lebesgue density the- orem played a crucial role in some recent developments in algorithmic randomness, namely, the solutions of the ML-covering and ML-cupping problems. Two new classes of reals emerged from this analysis: the posi- tive density points with respect to effectively closed (or Π01) sets of reals, and a proper subclass, the density-one points. Bienvenu, Ho ?lzl, Miller, and Nies have shown that the Martin-Lo ?f random positive density points are exactly the ones that do not compute the halting problem. Treat- ing this theorem as our starting point, we present several new results that shed light on how density, randomness, and computational strength interact.
- Keita Yokoyama, JAIST
Notes on the reverse mathematics for WWKL
It is well-known that Reverse Mathematics for analysis has a strong
connection with computable analysis. In fact, many theorems in Reverse
Mathematics can be understood as reformulations of theorems in
computable analysis. For example, the Cauchy-Peano theorem requires
WKL because there exists a computable differential equation whose
solution always computes a PA-degree. On the other hand, some theorems
might look rather strange. In this talk, I will consider the following
example from [1]:
Over RCA_0, WWKL is equivalent to the assertion that every continuous
function from [0,1] to [0,1] is Riemann integrable.
[1] S. Sanders and Y, The Dirac delta function in two settings of
Reverse Mathematics, Arch. Math. Logic 51, pp: 99?121, 2012.
- Cameron Freer, MIT
Invariant measures concentrated on Erdos-Renyi graphs
- 12:30 – 14:00 Lunch