Aspects of Computation

Overview

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