Sang-il Oum

IBS Discrete Mathematics Group

Courses on Discrete Math / Graph Theory at KAIST on Spring 2026

2026-02-11

essays kaist

Courses on Discrete Math / Graph Theory at KAIST on Spring 2026

Here is a list of some courses related to discrete mathematics and graph theory in the spring semester of 2026 at KAIST.

MAS59903 Advanced Discrete Topology

Convex polytopes are fundamental geometric objects which appear in a wide variety of mathematical disciplines. In this course we give an introduction to basic methods and modern tools of polytope theory, focusing on combinatorial aspects. We will learn important examples and constructions (e.g. zonotopes, Minkowski sums, non-rational polytopes, fiber polytopes, and the Lawrence construction) and discuss important results and concepts such as Steinitz’ theorem, f-vectors, h-vectors, the upper bound theorem, and oriented matroids.

CS49900B Algorithms for NP-hard Problem

Most computational problems are NP-hard, and we cannot expect to solve them (i) optimally (ii) in polynomial-time (iii) on all instances. In this course, we study algorithm design paradigms which relax some of the criteria (i)-(iii) for a desirable algorithm. Specifically, we present techniques for designing and analyzing algorithms in the frameworks of parameterized complexity, approximation and exact exponential algorithms. We examine how such techniques are implemented as algorithms for concrete problems using the structure of a problem instance or a solution. The notions of hardness, which says that there is a limit on how efficiently some problems can be solved under some computational complexity assumption, are introduced as well.

CS49900E Algorithmic Graph Theory

This course is intended to be an introduction to the world of structural and algorithmic graph theory. Many real world (optimisation) problems can be described in the language of Graph Theory. To overcome limitations imposed by the NP-hardness of any important problems, a widely adopted strategy is to restrict the input to structurally “well-behaved” graph classes. On the example of three classic graph classes, namely chordal graphs, circle graphs, and planar graphs, as well as related classes, we explore how structural properties can be utilised for the design of efficient algorithms. For all three classes we will discuss (1) structural characterisations, (2) recognition algorithms, and (3) the design of efficient algorithms.

CS49900F Introduction to Quantum Algorithms

This course provides a comprehensive introduction to the power and limitations of quantum computing. I will introduce quantum computing models, various quantum algorithms and lower bounds, and quantum complexity theory and cryptography.

CS49902 Seminar in Theoretical Computer Science

This course is a research seminar. In the beginning, each participant will be assigned a research paper from the areas of algorithmic graph theory and parameterized algorithms. Throughout the semester, participants will prepare and write a) a survey and summary of the assigned research topic, and b) a 60 minute presentation of their topic. Student presentations will be held throughout the semester. To give examples and insights on different ways to hold presentations, in the first weeks of the semester, guest lecturers have been invited to present their own research.

CS50000 Design and Analysis of Algorithm

The course aims to give a broad introduction of different fields of algorithm design and analysis. Using three fundamental problem families: Packing, Hitting Set, and Scheduling we investigate the landscape of different algorithmic challenges arising from the hardness of the problems and the settings in which we aim to design an algorithm. We discuss different methods of finding good algorithms and different models to evaluate the quality of the given algorithm: running time, approximation, competitiveness, etc.

Comments