-
Dilworth's Theorem
Introduction 딜워스의 정리(Dilworth’s Theorem)는 부분 순서 집합(partially ordered set)에서 최대 반사슬(antichain)의 크기는 사슬 분할의 최소 개수와 같다는 정리입니다. 먼저 용어들을 설명하겠습니다. 부분 순서 집합이란 말 그대로 순서가 부분적으로 정의된 집합입니다. 예를 들어 자연수 집합 $S$에서 $x$가 $y$로 나누어 떨어질 때 $x\geq y$로 정의하는 경우 $S$를 부분 순서 집합이라고 생각할 수 있습니다. 여기서 6과 3은 비교 가능하지만 6과 5는 비교 불가능합니다. 다른 예시는 2차원 좌표를 원소로 하는 집합에서 $x_1\leq x_2,y_1\leq y_2$이면 $(x_1,y_1)\leq(x_2,y_2)$로 정의하는 것입니다. 여기서는 (1,5)와...
-
BFV scheme에 대한 소개 - 2
Introduction 저번 글에서 BFV scheme에 대해서 소개하는 글을 썼습니다. 이 글에선 저번 글에서 사용한 notation들을 따와서 설명을 할 것이기 때문에, 이전 글을 다시 한번 읽고 오시면 이해가 더 쉬울 것입니다. 이번 글에서는 BFV scheme의 실제적인 구현을 위한 알고리즘들을 좀 더 설명하는 글을 쓰도록 하겠습니다. 이 글에서 사용한 Microsoft SEAL의 코드 구현은 이 글이 쓰여진 시점에서 최신 version의 SEAL(206648d)의 구현을 따릅니다. RNS representation Definition 본격적으로 설명하기에 앞서, RNS representation에 대해 먼저 설명을 하도록 하겠습니다. RNS(Residue Number...
-
Suffix Automaton
Suffix Automaton 문자열의 부분문자열에 대한 복잡한 문제를 풀 때 Suffix Array와 같은 접미사 구조 는 아주 강력한 도구가 된다. SCPC 2021 3번, 서울 리저널 2022 H 등 여러 중요한 대회에서도 이러한 접미사 구조를 응용한 문제들이 정말 많이 나온다. 한국에서 많은 사람들이 알고 있는 접미사 구조로는 Suffix Array 가 있다. Suffix Array는 모든 문자열의 접미사를 정렬한 순열로, 흔히 부분문자열 탐색 쿼리를 빠르게 처리하거나 두 접미사의 LCP를 구할 때 많이 쓰인다. 문자열 접미사 구조 중 알려진 자료구조는...
-
Exploring Simulated Annealing for Derivative-free Optimization 2
Exploring Simulated Annealing for Derivative-free Optimization 2 이전 포스트 Exploring Simulated Annealing for Derivative-free Optimization 1에 이어서 기존 Simulated Annealing을 여러 방면으로 개선시킨 방법론들에 대해 이야기하겠습니다. Fast Simulated Annealing 기존의 온도 쿨링의 경우, 쿨링되는 과정이 너무 느려서 실제로 converge할 때까지 시간이 너무 오래걸린다는 단점이 있습니다. 이러한 문제를 해결하기 위해서 새롭게 제안된 방법이 바로 Fast Simulated annealing입니다. 기존의 SA의 경우, 새로운 상태를 채택할지에 대한 확률을 exponential function을 통해서 결정했습니다. 즉, exponential function을 사용하기 때문에, 새로운 상태의...
-
Deterministic Almost-Linear Time Edge Connectivity, with and without expander decomposition
Introduction 이곳에 글을 연재하기 시작할 즈음 두 개의 포스트에서 Minimum Cut 문제의 state-of-the-art라고 볼 수 있는 두 알고리즘을 소개했습니다. 하나는 적절한 random sampling을 통해 모든 min-cut을 sparse한 cut으로 근사한 Karger 2000에 대해 다루었고, 다른 하나는 almost-linear time complexity를 달성한 최초의 알고리즘인 Li 2021 에 대해 다루었습니다. 둘 다 “seminal work”이라는 표현이 아깝지 않을 만큼 좋은 논문이지만, 이 중 Li에 대해서는 Expander Decomposition에 대한 제 이해가 부족하여 논문의 outline만 짚고 넘어갔습니다. Li의 논문을 리뷰하며 스스로 느꼈던...