DE EN
Forschungsinstitut für
Diskrete Mathematik
Menü

Graduate Seminar on Discrete Optimization (S4C1)

← Semesterübersicht

Summer 2020

Graph isomorphisms in quasi-polynomial time

The talks in this seminar will be based mainly on the following papers:

  1. Graph Isomorphism in Quasipolynomial Time, L. Babai, 2016
  2. Monte-Carlo algorithms in graph isomorphism testing, L. Babai, 1979
  3. Finite Permutation Groups and Finite Simple Groups, P.J. Cameron, 1980, Bulletin of the London Mathematical Society, 13, 1-22
  4. An Examination of the Different Possible Solutions of a Problem in complete blocks, R.A. Fischer, 1940.
  5. On the Combinatorial Power of the Weisfeiler-Lehman Algorithm, M. Fürer, 2017
  6. Algebraic Graph Theory, C. Godsil, G. Royle, 2001.
  7. Graph Isomorphisms in Quasi-Polynomial Time, H.A. Helfgott, 2017 (with an appendix by J. Bajpai and D. Dona)
  8. Isomorphism of Graphs of Bounded Valence Can be Tested in Polynomial Time, E.M. Luks, 1981, Journal of Computer and System Sciences 25, 42-65.
  9. On t-Designs, D.K. Ray-Chaudhuri, R.M. Wilson, 1975, Osaka Journal of Mathematics, 12, 737-744.
There are two recommendable videos with László Babai about his graph isomorphism paper: see here and here.
Due to the current situation, some changes in the organization are necessary:
  • At least in the beginning, the talks will be held as zoom meetings
  • In order to test the technical setup and to discuss the organization of the seminar, there will be a first zoom meeting on Monday, April 20, 14:15. An invitation to the meeting will be sent to all participants.
  • On some days, we have two regular talks. In this case, the first talk starts as usual at 14:15 while the second talk starts at 15:30.
  • The approval talks follow the regular talks (see the schedule below).
  • The length of each talk should be between 50 and 60 minutes (plus 15 minutes for discussion).
  • We recommend to prepare slides for the presentation. A reasonable number of slides is between 30 and 40.

For further information, see also the the web pages of the Bachelor Master Office Mathematics and of the University of Bonn

This is a preliminary schedule. Talks and approval talks may be shifted by up to one week.

Number Approval Talk Talk Name Topic Mentoring
1 20.4.
14:45 		4.5.
14:15 		Felix Rosebrock Monte-Carlo algorithms (paper(2)) Benjamin Rockel
2 27.4.
14:15 		11.5.
14:15 		Tobias Paszkiet The Weisfeiler-Lehman Algorithm (paper (5)) Stefan Rabenstein
3 4.5.
15:30 		18.5.
14:15 		Andreas Gwilt Section 2.1 of (7) and Sections 1 and 2 of (8) Pietro Saccardi
4 4.5.
16:45 		18.5.
15:30 		Silas Rathke Section 2.2 of (7) and Sections 3 and 4 of (8) Anna Hermann
5 11.5.
15:30 		25.5.
14:15 		Tin Sum Cheng Sections 2.3 - 2.5 of (7) Anna Hermann
6 11.5.
16:45 		25.5.
15:30 		Daniel Blankenburg Sections 2.6 - 2.8 of (7) and (5) or (9) Anna Hermann
7 18.5.
16:45 		8.6.
14:15 		Hanjo Thiele Section 3 of (7) and (3) Benjamin Klotz
8 25.5.
16:45 		15.6.
14:15 		Annette Lutz Section 4 of (7) and Section 8 of (1) Tilmann Bihler
9 8.6.
15:30 		22.6.
14:15 		Susanne Armbruster Section 5 of (7) I Tilmann Bihler
10 8.6.
16:45 		22.6.
15:30 		Luise Puhlmann Section 5 of (7) II Tilmann Bihler
11 15.6.
15:30 		29.6.
14:15 		Ekin Ergen Section 6 of (7) Benjamin Rockel
12 22.6.
16:45 		6.7.
14:15 		Lars Friederichs Appendix A of (7) Benjamin Rockel
  • A regular participation in the talks and an active collaboration are mandatory for passing the seminar.
  • Each participant has to write a summary consisting of one or two pages.
  • Each participant has to give an approval talk (typically two weeks before the regular talk). Passing the approval talk is a prerequisite for giving the regular seminar talk.
Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Prof. Dr. S. Hougardy,
Prof. Dr. S. Held,
Dr. U. Brenner