Virtual participation: Zoom details available here
Speaker: Professor Igor Potapov, University of Liverpool
Title: "New Computational Problems on Combinatorial Structures for Crystal Structure Prediction"
Abstract: Crystal Structure Prediction (CSP) is one of the major unsolved problems in materials science. The CSP is a fundamental optimisation problem: “In which way can N points be occupied (in real space) to minimise the sum of their pairwise interactions?” Crystal structures are periodic and the exploration of the energy landscape of crystal structures raises many computational problems for combinatorial structures. Many methods for exploring configuration space are still heuristic without mathematical guarantees about the quality of the solutions. In order to design efficient approximation algorithms, we are looking for new methods to evaluate distances between combinatorial objects and the efficiency of different exploration strategies, new techniques for effective selection of representative samples without explicit constructions of exponentially large configuration space and a better understanding of computational problems on probabilistic graphs, weighted graphs, permutation groups, and multidimensional words.
Biography: Igor Potapov is a Professor of Computer Science and a leader of "Algorithms, Complexity Theory and Optimisation" group at the Department of Computer Science of the University of Liverpool. His research is mostly in the study of different reachability questions and the boundaries between decidable and undecidable problems that concern automata, formal languages, semigroups and iterative maps. These areas have quite broad connections with algorithms and combinatorics on words, abstract algebra, topology and computation theory. Another line of his research is related to the design and analysis of algorithms in distributed computational models where he is particularly interested in self-organization, pattern formation and analysis of computational power. In 2020 Igor was awarded a Royal Society Leverhulme Trust Senior Research Fellowship for his work on reachability problems in automata and matrix semigroups. Recently in 2024, he won a Royal Society Apex award to focus on interdisciplinary research of accelerating the discovery of crystallised materials by developing new algorithmic approaches. Igor is a member of the UK branch of the Science for Ukraine initiative, where he leads several activities, including academic mentoring between the UK and Ukraine, facilitating new joint research projects with Ukrainian organizations, and supporting various research twinning programs.