-
Phase Transitions in Networks: Scale-free Networks
0. Introduction 상전이(phase transition)는 물리학에서 나온 개념으로, 어떤 임계점을 기준으로 양쪽에서 행동이 달라지는 것을 말합니다. 물리학을 공부하는 경우 이러한 현상을 학습하게 되는데요, 대표적인 예시로 2차원 이징 모델이나 란다우 긴즈버그 모델 등이 있습니다. 놀랍게도 어떤 랜덤하게 구성한 네트워크들에 대해서도 이와 비슷한 상전이 현상이 일어남이 알려져 있습니다. 이전 글에서는 랜덤 네트워크 모델 중 모든 가능한 간선들이 연결되어있을 확률이 $p$로 일정한, 가장 간단한 모델인 Erdős–Rényi 모델에서 일어나는 상전이에 대해 알아보았습니다. 또한 이 모델이 클러스터링 문제(두 이웃이 서로 이웃일...
-
Concurrent Queue - LCRQ
Intro Concurrent queue는 locks, databases, load balancers / task schedulers, transaction logging, HFT, network packet processing 등에서 사용됩니다. 수십 개의 스레드가 동시에 enq/deq를 수행하면서 좋은 throughput을 유지하도록 조율하는 것은 쉽지 않습니다. 작년 기준으로 LCRQ는 가장 성능이 좋은 알고리즘으로 알려져 있습니다. LCRQ가 어떻게 동작하는지 살펴보겠습니다. Original LCRQ Paper Baseline & Simple approaches Reminder & notations 큐를 위해서는 enqueue(x)와 dequeue() -> x를 지원해야 합니다. Array-based queue에서는 enq는 tail을, deq는 head를 1씩 증가시킵니다. CAS, FAA, linearizability, correctness, Cell...
-
F-deletion 문제의 최적 알고리즘
1. 서론 지난 글에서는 $\mathcal{F}$-deletion 문제의 FPT(Fixed-parameter tractable) 알고리즘에 대해 살펴보았다. 해당 알고리즘은 treewidth가 $t$ 이하로 bounded인 그래프에서 $2^{2^{O(t \log t)}} n$ 시간에 동작하였다. $\mathcal{F}$-(M-)deletion 문제는 널리 믿어지는 Exponential Time Hypothesis 하에서 일반적인 그래프 클래스($\mathcal{F}$가 chair 및 banner로 불리는 작은 크기의 그래프의 contraction으로 나타낼 수 없는 연결 그래프를 포함하는 경우)에 대해 $2^{o(t \log t)} poly(n)$ 시간에 해결될 수 없음이 밝혀져 있다. 이 글에서는 2023년 논문 [1]에서 제시한 $2^{O(t \log t)} n$ 시간에 $\mathcal{F}$-(M-)deletion 문제를 해결하는...
-
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: 비결정론적 튜링 머신이 ‘다항 시간’ 내에 ‘검증’할 수 있는 문제들의 집합입니다. 즉, 어떤 해답이 주어졌을 때, 그 해답이 올바른지 빠르게 확인할 수...