Theory of Computation

Theory of Computation Lab- POSTECH

(2024.12) A paper has been accepted to AAAI 2025.
(2024.10) Prof. Oh will serve as a program committee member for SoCG 2025
(2024.9) Two papers have been accepted to ISAAC 2024.
(2024.6) One paper has been accepted to ESA 2024.
(2024.5) 2nd Workshop on Combinatorial Algorithms is organized at POSTECH.
(2024.4) 통합과정 대학원생 조경진, 제1기 ‘대학원 대통령과학장학금’ 선정
(2024.2) Two papers have been accepted to SoCG 2024.
(2023.12) Prof. Oh will serve as a program committee member for EuroCG 2024
(2023.12) A paper has been accepted to AAAI 2024.
(2023.7) A paper has been accepted to ESA 2023.
(2023.5) Prof. Oh will serve as a program committee member for ISAAC 2023
(2023.5) Prof. Oh will serve as a program committee member for ESA 2023
(2023.4) A paper has been accepted to WADS 2023.

Planar and Surface Graphs
We stduy combinatorial properties of planar graphs and suface graphs with bounded genus and design algorithms using these properties.
Geoemtric Intersection Graphs
We study combinatorial properties of unit disk graphs, disk graphs, and outerstring graphs, and design algorithms using these properties.

Clustering Problmes
We study clusting problems including the k-center problem and k-means problems under various settings.
Range Searching Problems
We develop data structures for geometric problems such as range-clustering problems and shortest path problems.

Parameterized Algorithms
For NP-hard problems, our goal is to design efficient FPT algorithms.
Here, we measure the running time of an algorithm w.r.t. the input size and a parameter.
Polynomial-Time Algorithms
For problems in class P, our goal is to design linear/quadratic time algorithms.

Conditional Lower Bounds
Assuming P≠NP (or ETH), we prove lower bounds on the computation times for various algorithmic problems.
Matching Lower Bounds
Our main purpose of studying lower bounds is to show that our algorithms are optimal.

Office