2019: Dr Alexander Melnikov, Massey University Albany, School of Natural and Computational Sciences, has been awarded a Rutherford Discovery Fellowship for research titled ‘Applications of modern computability’
Published 10 Whiringa-ā-nuku October 2019
Dr Alexander Melnikov is a Senior Lecturer in the School of Natural and Computational Sciences at Massey University, Albany, with an interest in computability theory and its applications to logic, algebra, topology, and computer science. Dr Melnikov received his PhD in Computer Science from the University of Auckland in 2013 and his CSc (PhD) in Algebra and Logic from Novosibirsk State University, Russia in 2012. From 2012-2015 he conducted research as a Postdoctoral Fellow, firstly at Nanyang Technological University, Singapore then at Victoria University of Wellington, and finally at the University of California, Berkeley.
Computable mathematics blends abstract theory with computation within the diverse fields of mathematical logic, algebra, topology, and theoretical computer science. In pure mathematics, the properties of abstract objects are deduced through a requirement for logical consistency. Conversely, in computable mathematics, the properties of an abstract object are understood by using algorithms to construct them within a computer. In practice, being able to construct abstract objects often becomes a necessity in order to apply mathematics to computational problems. Dr Melnikov is particularly interested in so-called ‘online’ algorithms, which are particularly suited to certain types of problems. An online algorithm can process its input piece by piece in a serial fashion without having the entire input available from the start. However, because it does not know the whole input, an online algorithm is forced to make decisions that may later turn out not to be optimal.
Dr Melnikov will apply advanced methods of computability theory to two broad and interconnected programs of research. The first, classification problems in mathematics, uses computational and algorithmic tools to attack long-standing open problems in logic, algebra and topology. The second is a new general theory of online algorithms, relying on similar methods, to develop a new general theory of online computation, which has strong connections with algorithm design. Dr Melnikov believes that the burgeoning online algorithm program will eventually find real-world applications through explaining and advancing already extant applied algorithms as well as constructing entirely new algorithms.