in celebration of the research work of Professor Rod Downey
- Noam Greenberg (Victoria University of Wellington)
- Keng Meng (Selwyn) Ng (Nanyang Technological University)
- Guohua Wu (Nanyang Technological University)
- Yue Yang (National University of Singapore)
This four-week program on aspects of computation will focus on recent developments in parametric complexity theory, computability theory with applications in algebra, algorithmic randomness, model theory, etc.
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
- Classical Computability Theory
- Computable Structures and Reverse Mathematics
For full details of the program, please click here.
There will be talks in the mornings and free discussions in the afternoons.
- 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 Classical 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.