One of the central challenges of today's theory of computation is the lack of a systematic theoretical framework behind on-line algorithms. One usually studies only "off-line" algorithms with a fixed input. However, many modern computational tasks need to be performed upon a constantly updated and potentially unbounded input. For example, any algorithm dealing with a huge constantly changing database cannot have knowledge of the whole of the database before acting.
The proposed project contributes to a new and rapidly developing theory that aims to unite, explain, and ultimately advance the sparse results on on-line computation. More specifically, Kalimullin, Melnikov and Ng (2017) proposed a general framework for on-line computation for algebraic and combinatorial structures that relies on Dedekind's "primitive" recursion and advanced priority constructions. There is nothing primitive about this sort of recursion, as every polynomial-time algorithm is in fact primitive recursive.
The specific problems that we propose to attack during the workshop are motivated by the well-known results from computable algebra. These problems deal with the computational content of the theory of metric spaces, and the results will be applicable in the field of computable analysis (this is a fruitful area of the modern computability theory).
Participants' expertise requirements:
1. English language proficiency: sufficient for reading scientific articles and understanding mathematical lectures.
2. Knowing the basics of computability theory (the notions of Turing machine, partial computable function, arithmetical hierarchy, computable algebraic structure, polynomial-time algorithm).
3. Knowing the basics of topology (the notions of topological space, separable metric space, compact space).
You must necessarily possess:
PhD, Associate Professor, School of Natural and Computational Sciences, Massey University, New Zeland; Senior Researcher, Mathematical Center in Akademgorodok
Candidate of Science, Senior Researcher, Mathematical Center in Akademgorodok
Junior Researcher, Mathematical Center in Akademgorodok
Doctor of Science, Associate Professor, Chief Researcher, N.I. Lobachevsky Institute of Mathematics and Mechanics, Kazan Federal University
PhD, Associate Professor, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore
Doctor of Science, Chief Researcher, A.P. Ershov Institute of Informatics Systems; Senior Researcher, Mathematical Center in Akademgorodok