**Noam Greenberg**(Victoria University of Wellington)**Keng Meng (Selwyn) Ng**(Nanyang Technological University)**Guohua Wu**(Nanyang Technological University)**Yue Yang**(National University of Singapore)

General Enquiries: ims(AT)nus.edu.sg

Scientific Aspects Enquiries: guohua(AT)ntu.edu.sg

Traditional computability and complexity theory do not always model the behavior of actual problems properly. After realizing this, people start to look at other concepts of complexity, like generic case complexity (Kapovich, Miasnikov, Schupp, and Shpilrain) and parametric complexity (Downey and Fellows). Generic case complexity looks at the algorithms which always give the right answer but only need to halt on a set of Borel density 1. They have had extensive applications in group theory and we are beginning to understand the relationship between generic complexity, algorithmic randomness, and computability. Parametric complexity seeks to exploit the fact that, aside from cryptography, we always know more about the input to a problem than simply its size.

Computability theory is a branch of mathematical logic and computation theory that originated in the 1930s with the study of computable functions and relative computability. It overlaps with algebra, analysis, combinatorics, descriptive set theory, model theory and proof theory. Historically, the study of undecidability was motivated by various problems in mathematics, such as the word problem for finitely generated groups, Hilbert's 10th problem on Diophantine equations, and the like. In the last half century, research on computability theory has been focused on the investigation of various degree structures, from both algebraic and model-theoretic point of view. Recently, the concepts of effectiveness and relative computability have been introduced in the study of many constructions in algebra, analysis, combinatorics, randomness, and so on. By applying the methods from computability theory, Slaman et al. solved a problem in analytic number theory (2014). Downey and Montalban used computational methods to demonstrate that no reasonable invariants can be assigned to countable torsion-free abelian groups.

The program will focus on the following topics:

- Parametric Complexity
- Algorithmic Randomness
- Classic Computability Theory
- Computable Structures and Reverse Mathematics

**Collaborative Research and Workshop**: 21 August - 15 September 2017**Workshop on Parametric Complexity**: 21 - 25 August 2017**Workshop on Algorithmic Randomness**: 28 August - 1 September 2017**Workshop on Classic Computability Theory**: 4 - 8 September 2017**Workshop on Computable Structures and Reverse Mathematics**: 11 - 15 September 2017**Public Lecture**: 14 September 2017, 2.00pm - 3.00pm

**Waking Up from Leibniz' Dream: On the Unmechanizability of Truth**

Denis Hirschfeldt, The University of Chicago, USA

Venue: LT31, Block S16, Level 3, Faculty of Science, NUS, 6 Science Drive 2 Singapore 117546

Please note that our office will be closed on the following public holiday.

- 1 Sep 2017, Hari Raya Haji.

© National University of Singapore. All Rights Reserved.