No.047 Algorithmic Randomness and Complexity

Icon

NII Shonan Meeting Seminar 047

Transportation

How to get the venue

The venue is Shonan Village Center (湘南国際村センター). You can browse the access page.
The following is a summary of this page.

The easiest way from Narita Airport

Use JR YOKOSUKA line (横須賀線) from NARITA airport station that directly goes to ZUSHI station (逗子駅). (The one going to YOKOSUKA or KURIHAMA is good too.) It takes approximately 2h30min. This takes a longer time but no need to change. I would recommend you go buy GREEN CAR (first class car (no seat reservation)) at the same time (which is cheaper than NEX ticket to TOKYO).

From ZUSHI station, get on a taxi and tell the driver “Shonan Village Center”. The driver may not understand English, so it would be a good idea to print out this page, which contains the Chinese characters “湘南国際村センター” of the venue, and show this to the driver.

Shonan Village is actually a big one. The building you need to go is the one with No.1 in Map of Shonan Village. It may be a good idea to print out this page too in case.

Other ways

Actually there are several ways to go there. You can use a faster train but needs to change trains. You can use a bus for saving money. Please consult the access page for details.

Participants

Confirmed:

  • Eric Allender, Rutgers University
  • George Barmpalias, Victoria University of Wellington
  • Laurent Bienvenu, CNRS & Université Paris 7
  • Adam Day, Victoria University of Wellington
  • Cameron Freer, Massachusetts Institute of Technology
  • Noam Greenberg, Victoria University of Wellington
  • Rupert Hölzl, National University of Singapore
  • Akitoshi Kawamura, University of Tokyo
  • Mushfeq Khan, University of Hawaii
  • Takayuki Kihara, Japan Advanced Institute of Science and Technology
  • Selwyn Ng, Nanyang Technological University
  • Jan Reimann, Pennsylvania State University
  • Frank Stephan, National University of Singapore
  • Kohtaro Tadaki, Chuo University
  • Keita Yokoyama, Japan Advanced Institute of Science and Technology
  • Joseph Miller, University of Wisconsin – Madison
  • Johanna Franklin, Hofstra University
  • Andy Lewis-Pye, LSE
  • Benoit Monin, Paris Diderot
  • Satyadev Nandakumar, Indian Institute of Technology Kanpur

Organizers

  • Rodney Downey, Victoria University of Wellington
  • Kenshi Miyabe, Meiji University
  • Andre Nies, University of Auckland
  • Osamu Watanabe, Tokyo Institute of Technology

Schedule

 

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

Overview

Shonan Village Center
8 ? 12 September, 2014

Information and randomness are fundamental notions of computer science. Their practical applications are ever increasing. For instance, a recent volume of Communications of the ACM describes an application of (approximations of) Kolmogorov complexity to voice recognition. Kolmogorov complexity can be used to measure information distance in a natural and context-free way, and can be used in areas as diverse as computational biology, music evolution, data mining, and at least 20 other areas. Classical information theory and probability provide formalizations, but do not allow us to speak of the information content of a specific string or to say that a particular infinite binary sequence is random. These notions were formalized in the 1960s with the introduction of Kolmogorov complexity and Martin-Loef randomness. The first measures the complexity (or information content) of finite binary strings, while the second captures the intuition that a random infinite binary sequence has no “distinguishing features”. There are also characterizations of Martin-Loef randomness that capture the alternative intuitions that a random sequence is unpredictable and incompressible, the latter connecting Martin-Loef randomness to Kolmogorov complexity.

In recent years the people working in computability theory have produced a surge that resulted in rapid progress in our understanding of even the most basic notions, and in the solution of old open questions. This progress has changed and is still changing the landscape and opened up new avenues of research. An evidence of this activity has been the publication of two new books in the area, and the new edition of an already classical one.

  1. Algorithmic Randomness and Complexity, R. Downey and D. Hirschfeldt, Theory and Applications of Computability, Springer, 2010.
  2. Computability and Randomness, A. Nies, Oxford University Press, 2009.
  3. An Introduction to Kolmogorov Complexity and Its Applications, M. Li and P. Vitanyi. Third Edition, Springer Verlag, 2008.

Additionally, two of the proposers have been invited to the International Congress of Mathematicians to speak on algorithmic randomness, and a number of special issues of Computer Science Journals have been devoted to this area.

Research on the notions of information and randomness has drawn on methods and ideas from computability theory and computational complexity, as well as from core mathematical subjects like measure theory and information theory. The proposed list of invitees is balanced with respect to the various fields and reflects our aim to bring together the leading researchers from these areas. A major goal of the seminar is to bring together researchers to discuss the current open problems.

Organizers

  • Rodney Downey, Victoria University of Wellington
  • Kenshi Miyabe, Meiji University
  • Andre Nies, University of Auckland
  • Osamu Watanabe, Tokyo Institute of Technology