-
Interior Point Methods for Maximum Flow
Introduction 2021년 Maximum Flow는 Almost-Linear Time에 풀린다는 결과가 발표되었다 (이는놀랍게도 Minimum cost Flow에 대해서도 성립하는 명제이다). 이에 관련하여 공부할 수 있는 자료로는 Rasmus Kyng의 Advanced Graph Algorithms and Optimization 강의가 있어 이에 대한 스터디를 진행하였다. 이 강의의 Chapter 17인 “Interior point mehods for maximum flow” 를 정리해서 소개하려고 한다. 17장에서는 16장까지 다루었던 테크닉을 통해 undirected graph의 maximum flow 문제를 $\tilde{O}(m^{1.5})$ 시간에 해결하는 알고리즘을 제시한다. 16장까지 많은 정보가 소개된 만큼, 이 글은 self-contained되지 않았다. 그러니 어떤...
-
트리 압축의 다른 접근
문제 상황 아래의 문제 상황은 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의 구조에 대해서만 설명하려고 합니다. 저번...