Scope

Computability, Complexity and Randomness is a series of conferences devoted generally to the mathematics of computation and complexity, but tends to primarily focus on algorithmic randomness/algorithmic information theory and its impact on mathematics. Algorithmic randomness is the part of mathematics devoted to ascribing meaning to the randomness of individual strings and infinite sequences. For example, we give mathematical meaning to the intuition that one would more readily believe that the string 01101101001101011 was produced via the flips of a fair coin than one would of the string 00000000000000000. The core idea is that a sequence is algorithmically random if it passes all computational randomness tests, and hence if a computational observer cannot distinguish its behaviour in some process from the expected behaviour.

There are several historical approaches to algorithmic randomness, such as computable martingales, Kolmogorov complexity and Martin-Loef of randomness. Algorithmic randomness is also related to classical concepts, such as entropy (in the senses of Shannon and Boltzmann). The mathematics of this area is really quite deep. The kinds of questions include: How do we calibrate levels of randomness? Can we amplify weak random sources? Is randomness a provable computational resource? What kinds of power do random sources give us? And so on. Tools from this area can be used in many areas of mathematics and computer science, including the expected behaviour of algorithms, computational biology, ergodic theory, geometric measure theory, number theory and normality. The theme of the conference is algorithmic randomness and related topics in computability, complexity and logic, such as Kolmogorov complexity, computational complexity and reverse mathematics.

Topics

• Algorithmic randomness,

• Computability theory,

• Computability in analysis,

• Kolmogorov complexity,

• Computational complexity,

• Reverse mathematics and logic.

The conference will be co-located with The Sixteenth Asian Logic Conference

Conference Series

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

• CCR 2018, 13th International Conference on Computability, Complexity and Randomness, Santiago de Chile, Chile, 17-21 December 2018

• CCR 2017, 12th International Conference on Computability, Complexity and Randomness, Mysore, India, 3-7 July 2017

• CCR 2016, 11th International Conference on Computability, Complexity and Randomness, Honolulu, Hawaii, USA, 4-8 January 2016

• CCR 2015, 10th International Conference on Computability, Complexity and Randomness, Heidelberg, Germany, 22-26 June 2015

• CCR 2014, 9th International Conference on Computability, Complexity and Randomness, Singapore, 9-13 June 2014

• CCR 2013, 8th International Conference on Computability, Complexity and Randomness, Moscow, Russia, 23-27 September 2013

• CCR 2012, 7th International Conference on Computability, Complexity and Randomness, Cambridge, UK, 2-6 July 2012

• CCR 2011, 6th International Conference on Computability, Complexity and Randomness, Cape Town, South Africa,January 31-February 4, 2011

• CCR 2010, 5th International Conference on Computability, Complexity and Randomness, Notre Dame, USA, 2010

• CCR 2009, 4th International Conference on Computability, Complexity and Randomness, Luminy, France, 2009

• CCR 2008, 3th International Conference on Computability, Complexity and Randomness, Nanjing, China, 2008

• CCR 2007, 2th International Conference on Computability, Complexity and Randomness, Buenos Aires, Argentina, 2007

• CCR 2004, 1th International Conference on Computability, Complexity and Randomness, Córdoba, Argentina, 2004

• 
  

Invited Speakers

• Andrei Alpeev (Chebyshev Laboratory, St. Petersburg State University, Russia)

• Steffen Lempp ( Department of Mathematics, University of Wisconsin,USA)

• Margarita Marchuk (Sobolev Institute of Mathematics, Russia)

• Luca San Mauro (Institute for Discrete Mathematics and Geometry of Vienna University of Technology, Austria)

• Elvira Marordomo (Universidad de Zaragoza,Spain)

• Tim McNicholl (Iowa State University, USA),

• Wolfgang Merkle (Universität Heidelberg, Germany)

• Svetlana Selivanova (Korea Advanced Institute of Science and Technology, Republic of Korea and Sobolev Institute of Mathematics, Russia)

• Guohua Wu (Nanyang Technological University, Singapore)

Program of the conference

• Click  Program of the Conference to download the PDF version of the program

Abstracts (Click to expand)

Nan Fang. Betting with preference on outcomes.

Elvira Mayordomo. The return trip to classical fractal theory from effective fractal dimension.

Steffen Lempp. On the order dimension of locally countable partial orderings.

Gohua Wu. Lachlan Sets and Degrees.

Luca San Mauro. Computable reducibility and its variants.

Svetlana Selivanova. Exact real computation and complexity of PDEs.

Margarita Marchuk. Index sets of decidably categorical and computably categorical structures.

Tim McNicholl. Effective metric structure theory.

Andrei Alpeev. Entropy and Kolmogorov complexity for amenable-group actions.

Wolfgang Merkle. Logical Depth of Infinite Binary Strings: an Overview.

Bruno Bauwens. Enumerable semimeasure, randomness, and dependence: explaining Leonid Levin's paper.

Sergey Goncharov, Sergey Ospichev, Dmitry Sviridenko and Denis Ponomaryov. Logical Language of Polynomial Computability.

Rod Downey. A Hierarchy of Degrees.

Alexander Shen. Kolmogorov complexity and logic.

Location

The conference will be hosted by the Departament of Mathematics, at Nazarbayev University, Astana, Kazakhstan.

Submissions

Authors are invited to submit an abstract in PDF format of typically about 1 or 2 pages via the following web page:

https://easychair.org/conferences/?conf=ccr20190

No full papers will be required for this conference. After the deadline for submissions has expired, submissions may still be accepted for reviewing at the discretion of the PC chairs.

Registration

If you are planning to attend the conference, please fill out the following registration form as soon as possible.

Conference Registration

Proceedings

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

Programme Committee

• Rod Downey (Victoria University of Wellington, New Zealand), Chair

• Yang Yue (National University of Singapore, Singapore), co-Chair

• Bruno Bauwens (National Research University Higher School of Economics, Russia)

• Daniel Turetsky (University of Notre Dame, USA)

• Serikzhan Badaev (Al-Farabi Kazakh National University, Kazakhstan)

• Ng Keng Meng (Selwyn) (Nanyang Technological University, Singapore)

• George Barmpalias (Chinese Academy of Sciences, China)

• Johanna N.Y. Franklin (Hofstra University, USA)

• Barbara F. Csima (University of Waterloo, Canada)

• Denis Hirschfeldt (University of Chicago,USA)

• Manat Mustafa (Nazarbayev University)

Local Organizing Committee

• Manat Mustafa (Nazarbayev University)

• H. Atakan Varol( Nazarbayev University).

• Francesco Sica ( Nazarbayev University).

• Timur Bakibayev (Almaty Management University)

• Zhibek Kadyrsizova( Nazarbayev University).

• Raushan Zhumanova( Nazarbayev University).

Contacts

For questions, in particular about scientific aspects of the meeting, please contact the chairs of the programme committee.

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 (Montpellier, 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).

Funding

Funding opportunities for student members of the Association for Symbolic Logic (ASL) are available. Applications should be directed to the Association for Symbolic Logic three months prior to the meeting, following these instructions.

Copyright Notice

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