Advanced Graph Algorithms and Optimization Seminar, Fall 2025

263-4410-00L

Instructor: Rasmus Kyng

Assistants:

• Maximilian Probst Gutenberg
• Simon Meierhans
• Aurelio Sulser
• Christoph Grunau
• Deeksha Adil
• Gernot Zöcklein
• Ioannis Dorkofikis
• Sorrachai Yingchareonthawornchai
• Weixuan Yuan
• Yves Baumann

ECTS credits: 2 credits

Course catalogue entry: VVZ link

Course Objective and Content: This seminar is held once annually and is a supplement to the Advanced Graph Algorithms and Optimization course (AGAO25). In the seminar, students will study and present original research papers, with a focus on recent research developments. The core aim of the seminar is for students to get exposure to current research in the area and learn how to give a scientific presentation.

Prerequisites: As prerequisite we require that you passed the course "Advanced Graph Algorithms and Optimization". In exceptional cases, students who passed one of the courses "Randomized Algorithms and Probabilistic Methods", "Optimization for Data Science", or "Advanced Algorithms" may also participate, at the discretion of the lecturer.

Literature:

• AGAO25 course notes
• Convex Optimization by Stephen Boyd and Lieven Vandenberghe.
• This book is a helpful reference for convex optimization.
• Differential Calculus by Henri Cartan.
• If you have a powerful urge to learn all about multivariate calculus, you can start here. You shouldn't need it for the course though.
• Convex Analysis by Rockafellar.
• This is the classic text on basic convex analysis (not optimization). Again, you shouldn't need this.

Seminar Format

• The seminar is held in English.
• Each student will give a 45 min talk, with an additional 15 minutes for discussion.
• If circumstances permit, presentations will be held in person, otherwise they will be held online. Students will have the option to request an online presentation in any case.
• We strongly encourage whiteboard talks, or talks given using an iPad or similar writing device if online. We discourage the use of slides. If a student wishes to use slides for their presentation, they must request permission from the course instructor, by contacting their assigned supervisor.

Every participant is required to read, understand, and provide context for a selected research paper. This generally involves

• Providing an overview of related literature.
• Understanding and evaluating the background and motivation of the paper: What is the paper trying to do? Why it interesting and relevant?
• Having both a high-level and a detailed understanding of the paper.
• Selecting suitable and instructive elements of the paper for presentation.
• Presenting the chosen aspects of the paper in manner that is instructive and accessible to students who have mastered the AGAO25 course content.
• Being able to answer questions about the paper during the discussion section of the presentation.

Other Theory Institue professors have proceduced guidelines for giving talks which you may also find helpful. Note, however, that we encourage whiteboard talks instead of slides.

• Mittagsseminar talk guidelines
• Randomized Algorithms Seminar tips on on giving talks

Performance Assessment

• 95 % of the course grade is awarded for the final presentation. A more detailed breakdown of will follow soon.
• 5 % of the grade is for participation in other student presentations. To receive full credit, the student must ask a relevant question during at least one other presentation.
• Every student is required to attend (up to) five other student presentations. Failure to attend will result in grade reduction by up to 25 %, based on the fraction of missed presentations.

Paper Selection

Registered students will be contacted in late September with a list of available paper choices and asked to provide their ranked preferences for these papers. The course instructor will assign papers to the students, while trying to accommodate their preferences. Each student will be assigned one of the course assistants as their supervisor.

Schedule

More detailed scheduling information will be sent to registered students by late September once papers have been assigned.

• Students will have at least two preparatory meetings with their supervisor. The student will be in charge of scheduling these meetings by themselves, thoughout October and early November.
• Students will have a practice run of their presentation with one or more of the course assistants present.
• Final presentations will be held in late November/early December. The course instructor will contact students with scheduling options to limit conflict with other courses.