The 2026 Summer School on Combinatorics and Algorithms is a venue for students and early-career researchers to learn selected topics in theoretical computer science and discrete mathematics. It will be a great opportunity for young and aspiring researchers to study topics which are important but not covered during the lectures in the university classes.
Speakers
Daniel Dadush
CWI, Amsterdam
Magnus Wahlström
Royal Holloway, University of London
Program
Daniel Dadush
Algorithms & Geometry of Linear Programming
Linear programming (LP) is the task of solving optimization problems of the form min c x, Ax <= b, a fundamental model with innumerable applications in mathematics, operations research and computer science.
Read moreShow less
There are many mysteries surrounding the complexity of linear programming and its underlying geometry. Is there a polynomial bound on the combinatorial diameter of a polyhedron? Why is the simplex method so effective in practice despite exponential worst-case complexity? Why do interior point methods seem to converge in an essentially constant number of iterations? Is there a strongly polynomial algorithm for LP?
In this course, we will give an introduction to these topics and highlight recent progress, with a focus on the geometry the simplex and interior point methods.
Magnus Wahlström
Matroids, delta-matroids, and applications
This lecture series will cover theory and applications of linear matroids and delta-matroids, especially recent advances on linear delta-matroids, with applications in parameterized complexity.
Read moreShow less
Matroids are combinatorial abstractions which capture common features of notions of “independence” from linear algebra and other areas of combinatorics and graph theory. Structures captured by matroids include cycle-free edge sets in graphs, bipartite matchings, cuts in digraphs, and more. Matroids have many applications in computer science and discrete mathematics, especially due to their role as algorithmic abstraction, such as the greedy algorithm, generalizing algorithms for min-cost spanning trees, and more abstract problems such as matroid intersection, which generalizes maximum bipartite matching.
Of particular interest are linear matroids, i.e., matroids whose structure can be encoded into linear vector spaces. These allow for a linear-algebraic representation of purely combinatorial information, which can have unexpected consequences. For example, in parameterized complexity, linear matroids underpin methods such as:
- faster dynamic programming, via representative sets
- fast algebraic algorithms, such as the recent determinantal sieving method
- multiple applications in kernelization, such as the polynomial kernel for Almost 2-SAT and the efficient representation of cuts in terminal networks (the cut-covering sets lemma)
Delta-matroids are a generalization of matroids that captures a broader class of objects. Where matroids are defined around the notions of “independent sets” or “bases”, delta-matroids are defined around a more generic notion of “feasible sets”, which generalises both. Examples of structures captured by delta-matroids include matchings in non-bipartite graphs, “twistings” of matroids, structures in embedded graphs, and path-packing systems such as Mader’s S-path packings and alternating path-packings in red-blue graphs. As with matroids, there is also a notion of linear delta-matroids, with additional applications such as algorithms for packing feasible sets, delta-matroid intersection and parity problems. Delta-matroids are especially interesting in that they are very flexible structures; there are many ways of modifying and combining delta-matroids, such as the powerful delta-sum operation, which have no correspondence in matroids.
Many of the results for linear matroids, including the more advanced applications in parameterized complexity, can be directly generalized to linear delta-matroids. We will cover some of these generalizations, and especially applications of the more recent, and arguably more natural, “contraction representation” of a linear delta-matroid.
No prior knowledge about matroids or related topics is assumed, beyond basic concepts from linear and abstract algebra.
Schedule
- Start: Monday, August 10, 2026, 2:00 PM
- Check-in to the Dorm: Monday, 5:30 PM
- Banquet: Thursday evening
- End: Friday, August 14, 2026, 5:00 PM
| Monday | Tuesday | Wednesday | Thursday | Friday | ||
|---|---|---|---|---|---|---|
| 09:30 | Lecture A2 (1hr) |
Lecture A4 (1hr) |
Lecture A6 (1hr) |
Lecture A8 (1hr) |
09:30 | |
| 09:45 | 09:45 | |||||
| 10:00 | 10:00 | |||||
| 10:15 | 10:15 | |||||
| 10:30 | 10:30 | |||||
| 10:45 | Lecture B2 (1hr) |
Lecture B4 (1hr) |
Lecture B6 (1hr) |
Lecture B8 (1hr) |
10:45 | |
| 11:00 | 11:00 | |||||
| 11:15 | 11:15 | |||||
| 11:30 | 11:30 | |||||
| 11:45 | 11:45 | |||||
| 12:00 | Lunch | 12:00 | ||||
| 12:15 | 12:15 | |||||
| 12:30 | 12:30 | |||||
| 12:45 | 12:45 | |||||
| 13:00 | 13:00 | |||||
| 13:15 | 13:15 | |||||
| 13:30 | Lecture A3 (1hr) |
Lecture A5 (1hr) |
Lecture A7 (1hr) |
Recitation (1hr) |
13:30 | |
| 13:45 | 13:45 | |||||
| 14:00 | Welcome | 14:00 | ||||
| 14:15 | Lecture A1 (1.5hr) |
14:15 | ||||
| 14:30 | 14:30 | |||||
| 14:45 | Lecture B3 (1hr) |
Lecture B5 (1hr) |
Lecture B7 (1hr) |
Lecture A9 (1hr) |
14:45 | |
| 15:00 | 15:00 | |||||
| 15:15 | 15:15 | |||||
| 15:30 | 15:30 | |||||
| 15:45 | 15:45 | |||||
| 16:00 | Lecture B1 (1.5hr) |
Group Discussion (1hr) |
Lecture B9 (1hr) |
16:00 | ||
| 16:15 | 16:15 | |||||
| 16:30 | 16:30 | |||||
| 16:45 | 16:45 | |||||
| 17:00 | Recitation (1hr) |
17:00 | ||||
| 17:15 | 17:15 | |||||
| 17:30 | Check-in to the Dorm |
17:30 | ||||
| 17:45 | 17:45 | |||||
| 18:00 | Banquet | 18:00 | ||||
| 18:15 | 18:15 | |||||
| 18:30 | 18:30 | |||||
| 18:45 | 18:45 | |||||
| 19:00 | 19:00 | |||||
| 19:15 | 19:15 | |||||
| 19:30 | 19:30 | |||||
| 19:45 | 19:45 | |||||
| 20:00 | 20:00 | |||||
Monday
Tuesday
Wednesday
Thursday
Friday
Registration
- Registration is closed. Registration information remains available on the Indico page.
- Accommodation support applications are also closed.
Accommodation support: We can provide KAIST dormitory accommodations on a first-come, first-served basis for those who need lodging support, either for 2 persons per room or 3 persons per room. If you need, you can apply for accommodation support by selecting the corresponding options during the registration.
Organizers
- Jungho Ahn (Department of Computer Engineering, Inha University)
- Eunjung Kim (KAIST School of Computing / IBS Discrete Mathematics Group)
- Eunjin Oh (POSTECH CSE)
- Sang-il Oum (IBS Discrete Mathematics Group)
Local Information
Other Years
