Saugata Basu – Complexity in different contexts

Abstract:
The notion of complexity appears in many different contexts, including in the theory of computation, but also in topology and geometry. In the context of computational complexity there are also famous open questions about separations of complexity classes such as P and NP. In this talk I will discuss how these notions extend to more abstract mathematical structures such as constructible functions and sheaves, and how the classical questions about separation of complexity classes reduces to studying the complexity of certain functors. After giving some examples, I will mention a recent attempt in developing a unified theory of complexity from a purely categorical point of view. This last part is joint work with Umut Isik.

Margarita Korovina and Oleg Kudinov – Outline of Partial Computability in Computable Topology

Abstract:
In the framework of computable topology we investigate properties of partial computable functions, in particular complexity of various problems in computable analysis in terms of index sets, the effective Borel and Lusin hierarchies.

Alexander Melnikov – Eliminating unbounded search in computable algebra

Abstract:
Klaimullin, Melnikov and Ng have recently suggested a new systematic approach to algorithms in algebra which is intermediate between computationally feasible algebra and abstract computable structure theory. In this short survey we discuss some of the key results and ideas of this new topic. We also suggest several open problems.

Russell Miller – Computable Transformations of Structures

Abstract:
The isomorphism problem, for a class of structures, is the set of pairs of structures within that class which are isomorphic to each other. Isomorphism problems have been well studied for many classes of computable structures. Here we consider isomorphism problems for broader classes of countable structures, using Turing functionals and applying the notions of finitary and countable computable reductions which have been developed for equivalence relations more generally.