University Logo spc DFG Logo spc CCR Logo spc Match Logo spc Match Logo

Tenth International Conference on Computability, Complexity and Randomness (CCR 2015)

22-26 June 2015, Heidelberg, Germany

Heidelberg Panorama


A booklet with programme and abstracts is now available.

Monday, 22 June 2015
9.45 Opening
9.50 Antonín Kučera (Charles University, Prague)
Demuth's path to randomness
10.40 Coffee Break
11.10 Alex Galicki (The University of Auckland)
Differentiability of computable monotone functions in \(\mathbb{R}^n\)
11.40 André Nies (The University of Auckland)
Multiple recurrence and algorithmic randomness
12.10 Lunch Break
14.00 Noam Greenberg (Victoria University of Wellington)
Computing from projections of random points: a dense hierarchy of subideals of the K-trivial degrees
14.50 Joseph S. Miller (University of Wisconsin, Madison)
Computing from projections of random points: K-triviality and geometry
15.20 Coffee Break
16.00 Jason Rute (Pennsylvania State University, State College)
New directions in randomness
16.50 Nikolay Vereshchagin (Moscow State University)
Short lists with short programs for functions

Tuesday, 23 June 2015
9.10 Gilad Bavly (Bar-Ilan University, Ramat Gan)
How to gamble against all odds
10.00 Coffee Break
10.30 Mathieu Hoyrup (LORIA, Nancy)
On the information carried by programs about the objects they compute
11.00 Jan Leike (Australian National University, Canberra)
Solomonoff induction violates Nicod's criterion
11.30 Jason Teutsch (National University of Singapore)
Enumerations including laconic enumerators
12.00 Lunch Break
14.00 George Barmpalias (Chinese Academy of Sciences, Beijing)
Randomness, probabilities and machines
14.50 Marius Zimand (Towson University, Baltimore)
Polynomial-time algorithms in Kolmogorov complexity theory
15.40 Coffee

Wednesday, 24 June 2015
9.10 Dominik Janzing (Universität Tübingen)
Probability-free causal inference via the algorithmic Markov condition
10.00 Coffee Break
10.30 Kohtaro Tadaki (Chubu University, Kasugai)
An operational characterization of the notion of probability by algorithmic randomness and its applications
11.00 Tom Sterkenburg (CWI Amsterdam)
Generalized characterizations of semicomputable semimeasures
11.30 Peter A. Cholak (University of Notre Dame)
On uniform splits of computably enumerable sets
Free Afternoon

Thursday, 25 June 2015
9.10 Arno Pauly (University of Cambridge)
Weihrauch-completeness for layerwise computability
10.00 Coffee Break
10.30 Rutger Kuyper (Radboud University Nijmegen)
Uniformity and randomness
11.00 Gregory Igusa (University of Notre Dame)
1-genericity and the finite intersection principle
11.30 Bjørn Kjos-Hanssen (University of Hawaii at Manoa)
Permutations of the integers do not induce nontrivial automorphisms of the Turing degrees
12.00 Lunch Break
14.00 Rupert Hölzl (National University of Singapore)
The Vitali Covering Theorem in the Weihrauch lattice
14.50 Johanna N.Y. Franklin (Hofstra University, Hempstead)
Bases and JT- and LR-reducibility
15.20 Coffee Break
16.00 Jack H. Lutz (Iowa State University, Ames)
Algorithmic randomness in chemical reaction networks

Friday, 26 June 2015
9.30 Douglas Cenzer (University of Florida, Gainesville)
Compressibility, decidability and strong homeomorphisms of closed sets
10.00 Nan Fang (Peking University, Beijing)
Solovay functions and the no-gap phenomena
10.30 Coffee Break
11.00 Bruno Bauwens (Ghent University)
Conditional probability and van Lambalgen's theorem
11.50 Frank Stephan (National University of Singapore)
Complexity of semiautomatic structures
12.20 Sandwiches


The conference is hosted by the Institute of Computer Science of Heidelberg University and is part of the focus semester Computability and Randomness, which is organized and supported by the Mathematics Center Heidelberg (MatCH) .

The conference will be held on the ground floor of the Bioquant building on the university campus Neuenheimer Feld.

In order to reach the conference by public transportation from University Square or from Bismarck Square, use bus number 31 in direction Universitäts-Klinikum (sometimes also Chirurgische Klinik) and get off at stop Bunsengymnasium, which is directly at a gas station. At Bismarck Square, make sure to go in the right direction, i.e., use the stop that is about 10 m from the department store overlooking the square, next to a small bakery shop. Currently other possible connections may have problems due to construction work on the bridge next to the campus, in particular, all trams serving the campus are substituted by busses. On busses (but not on trams) tickets can be purchased at the driver. Tickets are valid on all busses and trams, including all changes within a reasonable amount of time.

Schedules for bus number 31 [Bismarck Square -> Bunsengymnasium] [Bunsengymnasium -> Bismarck Square].

The related conference Varieties of Algorithmic Information will take place in Heidelberg in the week before CCR 2015. Note that the venue of VAI is the Internationales Wissenschaftsforum Heidelberg (IWH) at the east end of Old Town.

Conference Series

The conference, previously known as conference on Logic, Computability and Randomness, will be in the tradition of the previous meetings in


Confirmed Invited Speakers

Important dates

Submission deadline: 20 April,
Notification of authors: 12 May,
Final version of abstract: 30 May,
Conference: 22-26 June 2015.


No registration is needed for persons already listed on the webpage of the focus semester Computability and Randomness as participating in the focus semester during the time of CCR.

All others should register by sending an informal email to Anja Kamp <> or Wolfgang Merkle <>. In particular, we would like to ask all prospective participants from Heidelberg to register this way.


No full papers will be required for this conference. Authors are invited to submit an abstract or extended abstract in PDF format via the submission page hosted by EasyChair.

After the deadline for submissions has expired, submissions may still be accepted for reviewing at the discretion of the PC chairs.


No proceedings will be published before the conference. A booklet with abstracts will be made available at the conference.

There will be a special issue of Theory of computing systems (TOCS) that will contain full versions of selected abstracts presented at the conference. Submissions to the special issue will be refereed according to the usual standards of TOCS.


There are limited local funds that will allow to support selected participants. Applications for funding are particularly welcome by researchers in an early phase of their career and from under-represented groups or regions.

Further funding opportunities for student members of the Association for Symbolic Logic (ASL) are available. Applications should be submitted to the Association for Symbolic Logic not later than three months before the meeting, following these instructions.

Programme Committee

Local Organizing Committee

Klaus Ambos-Spies, Anja Kamp, Nadine Losert, Wolfgang Merkle, Martin Monath


For questions, in particular about scientific aspects of the meeting, please contact the chairs of the programme committee Andy Lewis-Pye and Wolfgang Merkle .

Inquiries about organizational matters such as registration or accommodation are best addressed to the local organizing committee.

CCR Steering Committee

Verónica Becher (Buenos Aires, Argentina), Laurent Bienvenu (Paris, France), Rod Downey, chair (Wellington, New Zealand), Denis Hirschfeldt (Chicago, United States), Elvira Mayordomo (Zaragoza, Spain), Wolfgang Merkle (Heidelberg, Germany), Nikolai K. Vereshchagin (Moscow, Russia), Liang Yu (Nanjing, China).

Copyright Notice

The layout of this webpage has been adapted from the style of the CCA conference series and is used by courtesy of Vasco Brattka.

The panoramic picture of Heidelberg on top of this page is copyrighted and using it requires permission by its owner.