Graduate Seminar on Discrete Optimization (S4C1)
Summer 2020
Graph isomorphisms in quasi-polynomial time
The talks in this seminar will be based mainly on the following papers:
-
Graph Isomorphism in Quasipolynomial Time, L. Babai, 2016
-
Monte-Carlo algorithms in graph isomorphism testing, L. Babai, 1979
-
Finite Permutation Groups and Finite Simple Groups, P.J. Cameron, 1980, Bulletin of the London Mathematical
Society, 13, 1-22
-
An Examination of the Different Possible Solutions of a Problem in complete blocks, R.A. Fischer, 1940.
-
On the Combinatorial Power of the Weisfeiler-Lehman Algorithm, M. Fürer, 2017
- Algebraic Graph Theory, C. Godsil, G. Royle, 2001.
-
Graph Isomorphisms in Quasi-Polynomial Time, H.A. Helfgott, 2017
(with an appendix by J. Bajpai and D. Dona)
-
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.
-
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