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) so as to minimise the sum of their pairwise interactions?” Crystal structures are periodic and the exploration of the energy landscape of crystal structures raises a number of 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 need new results about distances between different combinatorial objects, selection of representative samples without explicit constructions of all and a better understanding of probabilistic graphs, weighted graphs, permutation groups, and multidimensional words.