J013 AlgoMaNet

Faculty of Informatics
Spring 2023
Extent and Intensity
0/0/1. 1 credit(s). Type of Completion: z (credit).
Teacher(s)
Prof. Dr. Pascal Schweitzer (lecturer), prof. RNDr. Daniel Kráľ, Ph.D., DSc. (deputy)
Dr. Sophia Brenner (seminar tutor), prof. RNDr. Daniel Kráľ, Ph.D., DSc. (deputy)
prof. RNDr. Daniel Kráľ, Ph.D., DSc. (assistant)
Guaranteed by
prof. RNDr. Daniel Kráľ, Ph.D., DSc.
Department of Computer Science – Faculty of Informatics
Supplier department: Department of Computer Science – Faculty of Informatics
Prerequisites
SOUHLAS
The student should be familiar with notions from abstract algebra, algorithm design, computational complexity and discrete mathematics at the level of an advanced undergraduate student.
Course Enrolment Limitations
The course is also offered to the students of the fields other than those the course is directly associated with.
fields of study / plans the course is directly associated with
there are 12 fields of study the course is directly associated with, display
Course objectives
The aim of the course is to present the state of the art related to isomorphism testing algorithm in the setting of groups. When it comes to questions of polynomial-time solvability in computational group theory, the way we encode the groups in the computer is crucial. Groups can for example be represented explicitly by their multiplication tables, more compactly as permutation groups, or by so-called presentations. The course briefly discusses these differences but then focuses on permutation group algorithms, which often arise naturally when dealing with finite graphs.
Learning outcomes
The student will get an understanding of the state of the art methods concerning group isomorphism. The student will be able to explain different ways of representing groups, their impact on algorithmic questions, and present efficient isomorphism algorithms for particular types of permutation groups.
Syllabus
  • Groups are the mathematical objects that capture the symmetry of combinatorial objects. Algorithmic group theory investigates which computational tasks involving groups have efficient solutions. The goal is to develop theoretically and practically efficient algorithms. In contrast to graph theory, when it comes to questions of polynomial-time solvability in computational group theory, the way we encode the groups in the computer is crucial. Groups can for example be represented explicitly by their multiplication tables, more compactly as permutation groups, or by so-called presentations. The course briefly discusses these differences but then focuses on permutation group algorithms, which often arise naturally when dealing with finite graphs. For permutation groups, many non-trivial polynomial-time algorithms have been developed. We will discuss efficient algorithms for various tasks. Some are seemingly easy at first sight but need clever techniques. An example is the membership problem, which asks us to decide whether a given permutation is contained in a permutation group given by generators. The course will also hint at how algorithms for permutation groups are used to develop fast algorithms for the graph isomorphism problem. This is for example done in Luks's polynomial-time algorithm for isomorphism of bounded degree graphs and Babai's quasipolynomial-time algorithm.
Teaching methods
The course will be delivered as an intensive one week course in the period June 26-30 with lectures complemented by tutorial sessions.
Assessment methods
To pass the course, the student will have to prepare a short summary demonstrating their knowledge of the presented material acquired during the course.
Language of instruction
English
Further Comments
The course is taught only once.
The course is taught: in blocks.
Teacher's information
https://www.fi.muni.cz/research/dimea/algomanet2023local.html.en
  • Enrolment Statistics (recent)
  • Permalink: https://is.muni.cz/course/fi/spring2023/J013