Patric Östergård
Department of Communications and Networking
Aalto University
Finland
Classification of mathematical structures
Abstract
Ever since the early days of digital computing, there has been a strong interaction between mathematics and computer science, in both directions. For example, the SWAC computer was used in the early 1950s by Raphael Robinson to discover five Mersenne primes and by Marshall Hall, Jr. et al. in the mid-1950s to prove uniqueness of the projective plane of order 8. The latter result is an example of classifying mathematical structures: find a complete set of structures with given parameters up to symmetry (equivalence, isomorphism, ...). Early work in this field faced many challenges. One challenge was that classification relied on pairwise comparison of structures, whereby the number of structures restricted the search. Another challenge was that errors in the algorithms and computations often went undetected. However, later advancements in the field has been able to successfully deal with these and other issues, and state-of-the-art techniques are now able to settle instances that may seem way out of reach. These lectures, which are based on parts of the below-listed book, will give the participants the skills needed to apply such techniques.
Course materials
- P. Östergård. Classification of discrete mathematical structures. Slides from EWSCS 2020. [pdf, password-protected]
- P. Östergård. Exercise class problems from EWSCS 2020. [pdf, password-protected]
- Videos from the lectures (large, unedited files) [mp4, password-protected]
- P. Kaski and P.R.J. Östergård. Classification Algorithms for Codes and Designs, v. 15 of Algorithms and Computations in Mathematics. Springer, 2006. [doi]
- B. D. McKay Isomorph-free exhaustive generation. J. Algorithms, v. 26, n. 2, pp. 306--324, 1998. [doi]
Last changed
April 10, 2020 22:33 Europe/Helsinki (GMT +03:00)
by
local organizers, ewscs20(at)cs.ioc.ee
EWSCS'20 page:
//cs.ioc.ee/ewscs/2020/