-
트리 압축의 다른 접근
문제 상황 아래의 문제 상황은 BOJ 16216번 문제에서 만나볼 수 있다. 정점이 가중치가 없는 트리 $T$가 주어진다. $T$는 $N$개의 정점과 $N-1$개의 간선을 가지고 있다. 정점들 가운데, 출발 정점 $v$와, 방문하고 싶은 $K$개의 정점들 $u_1, \cdots, u_K$이 주어진다. 정점 $v$에서 출발해서, $u_1, \cdots, u_K$ 중 1개, 2개, …, K개를 방문하는 가장 짧은 경로의 길이를 각각 구하여라. 아래부터 이 문제에 대한 풀이로 개념에 대한 설명을 시작하려 하니, 아직 이 문제에 대해 고민해보지 않았다면 (스포일러를 피하고 싶다면) 스크롤을...
-
Brakedown Overview
이 내용은 https://eprint.iacr.org/2021/1043 의 요약입니다. 이 논문의 목표는 Linear Code를 기반으로 한 Linear-Time PCS를 준비하고 이를 Spartan에 적용하여 Linear-Time Field-Agnostic SNARK를 얻는 것입니다. Spartan 계열 테크닉이 주목을 받는 시점에서 읽기 좋은 논문이라고 생각됩니다. 다만, 길이의 문제로 각종 증명들은 생략하도록 하겠습니다. Linear Time Polynomial Commitment Multilinear polynomial을 기준으로 생각하면, $g$의 Lagrange basis에서 coefficient를 $u$라고 했을 때 \[g(r) = \sum_i u_i \cdot \left(\prod_{k} (r_k i_k + (1 - r_k)(1 - i_k)) \right)\] 라고 쓸 수 있고, 대괄호...
-
Heavy-Light Decomposition Recursive DP
개요 Heavy-Light Decomposition Heavy-Light Decomposition(HLD)은 루트 있는 트리를 여러 개의 heavy chain으로 분할하는 알고리즘으로, 다음의 성질들을 만족합니다. 각 간선은 heavy edge 또는 light edge로 분류됩니다. 리프가 아닌 정점은 자식들 중 정확히 하나를 heavy child로 갖습니다. heavy child로 가는 간선은 heavy edge이고, 다른 자식으로 가는 간선은 모두 light edge입니다. heavy edge로 연결된 정점들의 묶음을 heavy chain이라 합니다. 각 heavy chain의 형태는 한 정점에서 출발해서 리프까지 내려가는 연속적인 경로가 되고, 모든 정점은 정확히 하나의 heavy chain에 속하게...
-
Multi Key Homomorphic Encryption - 1
Introduction 저번 글에서, Multi Party HE에 대해 간단하게 설명을 했습니다. 이번 글에서는 Multi Key HE에 대해서 간단히 설명하는 글을 쓰려고 합니다. 이번에 기준으로 한 논문은 여기에서 보실 수 있으며, 저자들의 이름을 따서 CDKS scheme이라고도 불립니다. 논문에서는 기본적인 Multi Key HE에 대한 설계를 바탕으로, BFV, CKKS에 적용시켜 Multi Key BFV, Multi Key CKKS 역시 설명하고 있으나, 이번 글에서는 아직 CKKS를 자세히 설명한 적도 없고, 적용도 그렇게 어렵지 않으므로, Multi Key HE의 구조에 대해서만 설명하려고 합니다. 저번...
-
Facebook의 설정 관리 시스템
이 글에서는 SOSP 2015 논문에 소개된 Facebook의 설정 관리 시스템을 살펴봅니다. Introduction 오늘날 대규모 웹서비스는 단순히 한대의 서버에서 돌아가지 않고, 수천대, 수만대 혹은 수십만대 이상의 서버로 이루어진 분산 환경에서 돌아갑니다. 이러한 상황에서 동일한 역할을 하는 서버들 사이에도 각 서버별로 다른 설정 값을 넣어줘야 하는 상황은 존재하며, 이를 “잘” 관리하는 것은 몹시 어려운 일입니다. 또한, 설정 값의 수정 또한 빈번한 경우에는 더더욱 어렵습니다. 예를 들어, 서버가 새로 시작하는 경우에만 설정 값을 읽어온다면, 새로운 설정을 적용하고 싶을...