-
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의 논문을 리뷰하며 스스로 느꼈던...
-
Geometric Deep Learning
Introduction 먼저, geometric deep learning에 대해 좀 더 알아보고 싶으신 분은 이 분야의 founder들이 작성한 놀라울 정도로 잘 쓰인 글이 있기 때문에 일독을 권합니다. 앞으로 이 글의 거의 대부분의 내용들은 위 자료를 따릅니다. 지난 10여년간 딥러닝은 엄청나게 빠르게 발전하며 컴퓨터 비전을 비롯하여 chatgpt에 이르기까지 다양한 산업에 수많은 변화를 가져왔습니다. 그리고 아직도 매일같이 수많은 논문이 쏟아져 나오고 있습니다. 각 논문들에서는 학습하는 데이터에 최적화된 각기 다른 neural network 구조를 사용하고 있고, 결국 우리는 성공적으로 동작하는 CNN, RNN,...