2026 조합론 및 알고리듬 여름학교는 이론 컴퓨터 과학과 이산수학 분야의 선별된 주제를 학생들과 초기 경력 연구자들이 배우는 장소입니다. 이는 대학 강의에서 다루지 않지만 중요한 주제를 공부할 수 있는 좋은 기회가 될 것입니다.
연사
Daniel Dadush
CWI, Amsterdam
Magnus Wahlström
Royal Holloway, University of London
프로그램
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.
일정
- 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
등록
- 등록이 마감되었습니다. 등록 정보는 Indico 페이지에서 확인할 수 있습니다.
- 숙박 지원 신청도 마감되었습니다.
숙박 지원: 숙박 지원이 필요한 분들 중 선착순으로 2인 1실 혹은 3인 1실로 카이스트 기숙사를 제공할 수 있습니다. 필요하신 경우 등록하실때 신청바랍니다.
조직위원
정보
다른 연도
