SAS Follow on: International conference on computability, complexity and randomness

Workshop theme

In 2012, the Newton Institute hosted a high-profile programme Syntax and Semantics: A Legacy of Alan Turing, which was a major component of the worldwide Alan Turing Year celebrations. The capstone workshop of the Syntax and Semantics programme was the 7^th Conference on computability, Complexity and Randomness. This follow-up workshop serves as the 15^th Conference on Computability, Complexity and Randomness.

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-Loff 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.

Applications for this workshop are now closed

Fees

Registration Only

Registration Package: £208
Student Registration Package: £158

The Registration Package includes admission to all seminars, lunches and refreshments on the days that lectures take place (Monday - Friday), wine reception and formal dinner, but does not include other meals or accommodation.

Accommodation

Unfortunately we do not have any accommodation to offer so all successful applicants will need to source their own accommodation.

Please see the Hotels Combined website for a list of local hotels and guesthouses.

Meals

Lunch Lunch timings and location will be confirmed with timetable.

Evening Meal Participants are free to make their own arrangements for dinner.

Formal Dinner The Formal Dinner location and date is to be confirmed.

Participants on the Accommodation Package or Registration Package, including organisers and speakers, are automatically included in this event.

The Institute kindly requests that any papers published as a result of this programme’s activities are credited as such. Please acknowledge the support of the Institute in your paper using the following text:

The author(s) would like to thank the Isaac Newton Institute for Mathematical Sciences, Cambridge, for support and hospitality during the programme SAS Follow on: International conference on computability, complexity and randomness, where work on this paper was undertaken. This work was supported by EPSRC grant EP/F005431/1 and EP/I016392/1.

Timetable

Monday 29th June 2020
09:00 to 09:50	Registration	No Room Required
09:50 to 10:00	Welcome	No Room Required
11:00 to 11:30	Morning Coffee	No Room Required
12:30 to 13:30	Lunch	No Room Required
15:30 to 16:00	Afternoon Tea	No Room Required
17:00 to 18:00	Welcome Wine Reception at INI	No Room Required

Tuesday 30th June 2020
11:00 to 11:30	Morning Coffee	No Room Required
12:30 to 13:30	Lunch	No Room Required
15:30 to 16:00	Afternoon Tea	No Room Required

Wednesday 1st July 2020
11:00 to 11:30	Morning Coffee	No Room Required
12:30 to 13:30	Lunch	No Room Required
15:30 to 16:00	Afternoon Tea	No Room Required

Thursday 2nd July 2020
11:00 to 11:30	Morning Coffee	No Room Required
12:30 to 13:30	Lunch	No Room Required
15:30 to 16:00	Afternoon Tea	No Room Required

Friday 3rd July 2020
11:00 to 11:30	Morning Coffee	No Room Required
12:30 to 13:30	Lunch	No Room Required
15:30 to 16:00	Afternoon Tea	No Room Required

Monday 6th June 2022
09:00 to 09:55	Registration	No Room Required
09:55 to 10:00	Ulrike Tillmann University of Oxford Welcome talk	Room 1
10:00 to 11:00	Selwyn Ng Chair: Elvira Mayordomo The algorithmic strength of planar graph colouring theorems	Room 1
11:00 to 11:15	Morning Coffee	No Room Required
11:15 to 12:15	Bjoern Kjos-Hanssen Chair: Elvira Mayordomo Automatic complexity: a computable measure of irregularity	Room 1
12:15 to 13:30	Lunch at Churchill College	No Room Required
13:30 to 14:30	Joseph Miller Chair: Elvira Mayordomo Introenumerable sets and the cototal enumeration degrees	Room 1
14:30 to 15:30	Julia F. Knight University of Notre Dame; None / Other Chair: Elvira Mayordomo Generalizing a question of Gromov, Part I	Room 1
15:30 to 16:00	Afternoon Tea	No Room Required
16:00 to 17:00	Jack Lutz Iowa State University Chair: Elvira Mayordomo Effectivizing Analytic Concepts	Room 1
17:00 to 18:00	Welcome Wine Reception at the INI	No Room Required

Tuesday 7th June 2022
09:00 to 10:00	Noam Greenberg Victoria University of Wellington Chair: Laurent Bienvenu An effective classification of Borel Wadge classes	Room 1
10:00 to 11:00	Neil Lutz Swarthmore College; University of Pennsylvania Chair: Laurent Bienvenu The Point-to-Set Principle in Metric Spaces and Complexity Classes	Room 1
11:00 to 11:15	Group photo and Morning Coffee	No Room Required
11:15 to 12:15	Anuj Dawar University of Cambridge Chair: Laurent Bienvenu Unconditional Hardness of Approximation	Room 1
12:15 to 13:30	Lunch at Churchill College	No Room Required
13:30 to 14:30	Andre Nies University of Auckland Chair: Laurent Bienvenu 20 years of K-triviality	Room 1
14:30 to 15:30	Verónica Becher Universidad de Buenos Aires Chair: Laurent Bienvenu Insertion in normal numbers	Room 1
15:30 to 16:00	Afternoon Tea	No Room Required
16:00 to 17:00	Adam Case Drake University Chair: Laurent Bienvenu Finite-State Mutual Dimension	Room 1

Wednesday 8th June 2022
09:00 to 10:00	Daniel Turetsky Victoria University of Wellington TBA	Room 1
09:00 to 10:00	Daniel Turetsky Victoria University of Wellington Chair: Peter Cholak Studying Introreducibility	Room 1
10:00 to 11:00	Linda Brown TBA	Room 1
10:00 to 11:00	Linda Brown Chair: Peter Cholak Step functions in the Weihrauch lattice	Room 1
11:00 to 11:15	Morning Coffee	No Room Required
11:15 to 12:15	Theodore Slaman University of California, Berkeley Chair: Peter Cholak Computability and Set Theoretic Aspects of Hausdorff Dimension	Room 1
12:15 to 13:30	Lunch at Churchill College	No Room Required
13:30 to 17:00	Free Afternoon	No Room Required
19:30 to 22:00	Formal Dinner at Robinson College	No Room Required

Thursday 9th June 2022
09:00 to 10:00	Kenshi Miyabe Meiji University Chair: Linda Westrick Subclasses of the weakly computable reals	Room 1
10:00 to 11:00	Arno Pauly Swansea University Chair: Linda Westrick Luzin's N and randomness reflection	Room 1
11:00 to 11:15	Morning Coffee	No Room Required
11:15 to 12:15	Peter Cholak University of Notre Dame Chair: Linda Westrick On Ramsey-like theorems on the rationals and the Rado graph	Room 1
12:15 to 13:30	Lunch at Churchill College	No Room Required
13:30 to 14:30	Ekaterina Fokina Chair: Linda Westrick Classification problem for effective structures	Room 1
14:30 to 15:30	Giovanni Solda Chair: Linda Westrick Multifunctions computing sequentially discontinuous multifunctions	Room 1
15:30 to 16:00	Afternoon Tea	No Room Required
16:00 to 17:00	Johanna Franklin Hofstra University; None / Other Chair: Linda Westrick Generalizing a question of Gromov, Part II	Room 1

Friday 10th June 2022
09:00 to 10:00	Takayuki Kihara Nagoya University Chair: Paul Shafer Weihrauch reducibility on multi-represented spaces	Room 1
10:00 to 11:00	Vasco Brattka Universität der Bundeswehr München; University of Cape Town Chair: Paul Shafer Which Weihrauch degrees correspond to axiom systems?	Room 1
11:00 to 11:15	Morning Coffee	No Room Required
11:15 to 12:15	Dariusz Kalociński Polish Academy of Sciences Chair: Paul Shafer Degree spectra of computable functions on natural numbers with standard order	Room 1
12:15 to 13:30	Lunch	No Room Required
13:30 to 14:30	Tomasz Steifer Pontificia Universidad Católica de Chile; Polish Academy of Sciences Chair: Paul Shafer Learning and randomness	Room 1
14:30 to 15:30	Steffen Lempp University of Wisconsin-Madison Chair: Paul Shafer Toward deciding the AE-theory of the Sigma02-enumeration degrees	Room 1
15:30 to 16:00	Afternoon Tea	No Room Required
16:00 to 17:00	Chair: Paul Shafer Close	Room 1

SAS Follow on: International conference on computability, complexity and randomness

Organisers

Rod Downey Victoria University of Wellington
Elvira Mayordomo Universidad de Zaragoza
Paul Shafer University of Leeds

Speakers

Verónica Becher Universidad de Buenos Aires
Vasco Brattka Universität der Bundeswehr München; University of Cape Town
Linda Brown
Adam Case Drake University
Peter Cholak University of Notre Dame
Anuj Dawar University of Cambridge
Ekaterina Fokina
Johanna Franklin Hofstra University; None / Other
Noam Greenberg Victoria University of Wellington
Dariusz Kalociński Polish Academy of Sciences
Takayuki Kihara Nagoya University
Bjoern Kjos-Hanssen
Julia F. Knight University of Notre Dame; None / Other
Steffen Lempp University of Wisconsin-Madison
Jack Lutz Iowa State University
Neil Lutz Swarthmore College; University of Pennsylvania
Joseph Miller
Kenshi Miyabe Meiji University
Selwyn Ng
Andre Nies University of Auckland
Arno Pauly Swansea University
Theodore Slaman University of California, Berkeley
Giovanni Solda
Tomasz Steifer Pontificia Universidad Católica de Chile; Polish Academy of Sciences
Ulrike Tillmann University of Oxford
Daniel Turetsky Victoria University of Wellington

Show All