-
Phase Transitions in Networks: Erdős–Rényi Model
0. Introduction 상전이(phase transition)는 물리학에서 나온 개념으로, 어떤 임계점을 기준으로 양쪽에서 행동이 달라지는 것을 말합니다. 물리학을 공부하는 경우 이러한 현상을 학습하게 되는데요, 대표적인 예시로 2차원 이징 모델이나 란다우 긴즈버그 모델 등이 있습니다. 놀랍게도 어떤 랜덤하게 구성한 네트워크들에 대해서도 이와 비슷한 상전이 현상이 일어남이 알려져 있습니다. 본 글에서는 그 중에서도 가장 간단한 모델인 Erdős–Rényi 모델에서 일어나는 상전이에 대해 공부해보려 합니다. 본 글은 KIAS-SNU Physics Winter Camp 2025 중 고등과학원 계산과학부 이덕선 교수님의 “Phase Transitions in Networks”...
-
Quantum Complexity
Introduction 계산 복잡도 이론(Computational Complexity Theory)을 처음 접할 때, 우리는 대개 튜링 머신(Turing Machine) 을 기준으로 정의된 클래스들을 마주하게 됩니다. 아마도 가장 친숙한 이름들은 다음과 같을 것입니다. P: 결정론적 튜링 머신이 ‘다항 시간’ 내에 ‘풀’ 수 있는 문제들의 집합입니다. 보통 우리가 효율적으로 해결할 수 있는 문제라고 한다면 이 클래스에 속하는 문제들을 의미합니다. NP: 비결정론적 튜링 머신이 ‘다항 시간’ 내에 ‘검증’할 수 있는 문제들의 집합입니다. 즉, 어떤 해답이 주어졌을 때, 그 해답이 올바른지 빠르게 확인할 수...
-
Happy ending problem
서론 Extremal Graph Theory의 핵심 질문은 “무질서해 보이는 구조가 충분히 크다면, 그 안에 특정한 패턴이 필연적으로 존재하는가?”이다. 본 글에서는 이러한 ‘필연적 질서’에 대한 논의를 1차원 수열에서 시작하여 2차원 기하 영역으로 확장한다. 구체적으로 Erdős-Szekeres Theorem을 통해 수열에서의 단조 부분 수열의 존재성을 증명하고, 이를 일반화하여 평면 기하학의 난제 중 하나였던 Happy Ending Problem과 볼록 다각형의 존재성에 대한 상한과 하한을 논한다. 1. Erdős-Szekeres Theorem Extremal Graph Theory의 논의를 시작하기 위해, 가장 기초적이면서도 강력한 정리를 소개한다. 이는 1차원 수열...
-
K-Center Problem in Tree
1. Introduction k-center problem은 그래프에서 $k$개의 센터를 선택하여 모든 정점으로부터 가장 가까운 센터까지의 거리의 최댓값을 최소화하는 최적화 문제입니다. 이는 도시 내에 소방서나 응급 의료 센터와 같은 필수 시설을 배치할 때, 가장 가까운 시설까지의 거리가 일정 수준을 넘지 않도록 해야 하는 상황에서 주로 사용됩니다. 일반 그래프에서의 k-center problem은 NP-hard로 알려져 있으며, $P \neq NP$ 가정 하에 2-approximation보다 나은 근사 알고리즘 또한 NP-hard임이 증명되어 있습니다. 때문에 일반 그래프에서는 근사 알고리즘을 이용한 접근이나, 그래프의 특수한 구조를 이용하는 접근이...
-
Parallel Small Vertex Connectivity In Near-Linear Work and Polylogarithmic Depth
Introduction 이 글에서는 제가 Yonggang Jiang과의 공동 연구로 작성한 논문에서 다룬 문제인 k-vertex connectivity의 효율적인 병렬 알고리즘에 대해 설명합니다. 최근 유명한 그래프 문제들을 병렬/분산 환경에서 해결하는 연구에 많은 진전이 있었는데, 이 글을 통해 다양한 계산 모델에서 효율적인 알고리즘을 설계할 때 어떤 관점이 유용한지 제 나름의 직관을 풀어보고자 합니다. Preliminary 무방향, 무가중치 그래프 $G$가 주어졌을 때, $V(G)$의 분할 $(L, S, R)$이 $L, R \neq \emptyset$이고, $L$과 $R$ 사이에 간선이 없으면 이를 Vertex Cut이라고 합니다. 이때 가능한...