This information is intended only for students that are supervised by Tomáš Peitl. If you have a different supervisor, ignore the instructions.

Next steps

Hello, and welcome to the seminar! Please, take the following steps:

1. send me an email from your university address containing your

   • name,
   • Matrikelnummer,
   • topic name.

   A simple list with no formalities is OK.

2. fill out this poll to book an appointment for our initial meeting;

3. read the rest of these instructions and the section for your selected topic.

We will meet in my office at the time you select in the poll.

In case you have any questions or can’t pick a time in the poll, include them in the email. If you don’t have questions and picked a time, get acquainted with your selected topic and come to the meeting with a list of references that you have found.

Goals of this Course

You are expected to learn about your chosen topic and present it in an understandable way to your fellow students (and the supervisor).

In particular, you are not expected to come up with original research results.

Guidelines

Presentation

The goal of your talk is to explain the topic to the audience so that after the talk they have some idea about it, can ask questions, etc.

For the most part, keep the talk rather high level, the time is short for in-depth incursions. When in doubt, explain basic concepts; do not assume too much about the audience’s background. It is always fine to ask if everyone is familiar with X.

At the same time, your talk should have some deeper technical component: an algorithm, theorem, proof, or something similar, that you explain in a bit greater detail. What is suitable for this varies with the topic; we will talk about this in the initial meeting.

Some topics have a clear scope, others may be broad. If you have a broad topic, we will use the initial meeting to narrow down the scope and decide what to focus on.

It is important that you stay on time as we have a tight schedule; rehearse your presentation at least once. Aim for between 20-25 minutes, ideally somewhere in the middle of that range.

Paper

The paper should be a more formal version of the presentation. I will give you feedback on the presentation, possibly tell you to adjust the content.

The page limit is strict, do not go over. Shorter is better as says the famous quote attributed in various versions to various people over the centuries:

I have only made this [paper] longer because I have not had the time to make it shorter.

LaTeX Template

Use of LaTeX is mandatory for the paper and encouraged for the presentation. Download the template files here.

Use of AI

The general principle vis-a-vis generative AI is that you are responsible for the presentation and the paper. In addition the following rules apply.

The allowed uses of AI include

• search for information, having stuff explained;
• technical help with LaTeX, PowerPoint, etc.

Any use of AI to generate the content of the presentation or the paper is forbidden. This means, e.g., that you can ask an AI to help you with LaTeX formatting, but the AI must not write the words on the slides (or in the paper). This applies regardless of how you use AI (i.e., whether Claude Code or Codex edits your files or you just copy text from ChatGPT, using generated content is forbidden).

The reason for this policy is this. One of the goals of this course is to exercise the skill of understanding ideas and explaining them to others in speech and in writing. This requires the hard process of organising your thoughts into a coherent talk or text. If you let the AI do that for you, you defeat the purpose of the course. It is, however, not the goal of this course to learn the intricacies of LaTeX, so there AI use is allowed.

It is often easy to see that a piece of text was generated by AI. By the principle of responsibility stated above, you must be able to explain all of your content and you must be able to understand all of your slides. In particular, even if you break the rules and use AI to generate text, you’re still not allowed to admit it and lay blame on the AI, just like you wouldn’t be able to say that your friend made a mistake while they prepared your presentation.

A potentially gray area is figures (no pun intended), for which AI can be very useful, but there is hardly a meaningful distinction between the content of a figure and it’s technical layout. Therefore use of AI for figures is allowed, but the responsibility principle applies as before. Keep in mind that you absolutely can be creative with figures, including you can draw them by hand and scan if you want.

Grading

If you demonstrate that you have understood and are able to clearly communicate your topic in the talk and the paper, you will generally get an S1. The feedback after the talk will include a tentative grade that you are headed towards, along with a justification in case it’s worse than S1.

Note that the final grade for the whole course is composed of two parts, so even if you get S1 from me, you may still get a worse grade overall (and this is beyond my influence).

Topics (2026 WS)

Graph Isomorphism and Weisfeiler-Leman

Graph isomorphism (GI) is the problem of deciding whether the vertices of one input graph $G$ can be relabeled to obtain another input graph $H$. It is a fundamental problem with lots of applications in computer science, mathematics, and beyond. Testing isomorphism between any kinds of structures means testing if the objects are essentially the same, and graphs are so generic that they can represent almost any other structure.

The Weisfeiler-Leman (WL) algorithm is a polynomial-time algorithm that can often decide graph isomorphism, but sometimes fails to distinguish non-isomorphic graphs. It is based on the idea of color refinement: a process in which vertices receive colors so that any potential isomorphism must preserve colors. If the graphs $G$ and $H$, by color refinement, end up with color classes of different sizes, then they definitely cannot be isomorphic. Apart from Weisfeiler and Leman’s 1968 paper, references to graph isomorphism research can be found for instance in Babai’s Graph Isomorphism in Quasipolynomial Time or Babai and Luks: Canonical labeling of graphs.

This topic contains two subtopics: graph isomorphism in general, and the WL algorithm for it in particular. Your paper and presentation should also touch on both of these aspects.

On GI itself, important concepts to mention are computational complexity, including the complexity class GI and GI-completeness, and reductions between GI and the related problems around finding graph automorphisms and computing canonical forms (a labeling of vertices that can be computed for each graph and will be the same for isomorphic graphs). You should understand how to use graph isomorphism to compute graph automorphisms and vice versa, and how isomorphism and canonical form are related.

On WL, you should present the algorithm itself, including its higher-dimensional variants (coloring tuples of vertices instead of individual vertices). An example worth mentioning is the Weisfeiler-Leman dimension of a graph (how big tuples are needed for color refinement to successfully distinguish the graph from any other non-isomorphic graph) and that trees and forests have Weisfeiler-Leman dimension 1, and random graphs have bounded WL dimension with high probability (think in detail what this means). WL is also related to expressivity of graph neural networks.

This is an example of a broad topic, and there is some freedom to explore what interests you.

Karger’s Algorithm for Minimum Cut

A cut in an undirected graph is a partition of the set of vertices into two subsets. The corresponding cutset is the set of edges going from one subset to the other. The minimum cut problem asks for the cut with the smallest cutset.

Minimum cut is related to maximum flow via the min-cut-max-flow theorem. Karger’s algorithm is a randomized algorithm based on the notion of edge contraction that computes minimum cut. It was introduced by David Karger in 1993. The Karger-Stein algorithm is an extension that achieves and order-of-magnitude speedup.

Apart from the algorithm itself, you are invited to explore the wider landscape of cuts, flows, and related notions.

The Secretary Problem

Imagine that you are supposed to hire an employee. A sequence of candidates $x_1, \dots, x_n$ shows up for interviews in this order. Upon hearing the candidate $x_i$, you establish how that candidate compares to all other candidates seen. You know that there will be $n$ candidates and you want to hire the best candidate. The caveat is that after hearing each candidate, you must immediately decide to hire or reject. If you decide to hire, you are done. If you decide to reject, you will not be able to hire that candidate anymore in the future, even if you determine that the candidate was best. What strategy to pick?

This and similar problems form the area known as Optimal Stopping theory. Think about or look up the answer for yourself. Does it match your intuition?

One natural extension of this problem is when you don’t necessarily need the best candidate, but simply want to maximize the quality.

This topic intersects with the idea of online algorithms: algorithms that process a sequence of inputs attempting to maximize an objective, but having to take decisions without seeing the whole input at once. Other problems from this area may be within the scope of this topic if you’re interested. This is also a topic that is more math-heavy, in particular in probability theory.

The Skip List

When representing a set or a mapping, one needs a data structure that allows for retrieval of information based on some key (is the key in the set? To what value does the key map?), which may be an arbitrary piece of data. The standard solutions to this problem are hash tables, binary search trees, and B-trees, each with their own strengths and tradeoffs. The skip list, introduced by William Pugh in 1989, is another data structure that allows search for arbitrary keys.

The basic idea of skip lists is to maintain a sorted linked list along with layers of shortcuts. The $i$-th layer will be a linked list of every $2^i$-th element, skipping over the elements in between. The choice of how to maintain the shortcut layers (dynamically under insertions and deletions) is typically randomized. Skip lists are thus an example of a probabilistic data structure, achieving average logarithmic complexity on the standard search, insert, and delete operations. Their advantage lies in faster algorithms (in terms of the constants), greater simplicity, handling of concurrent accesses, and space efficiency.