-
CDQ Divide and Conquer, Relaxed Convolution
개요 CDQ Divide and Conquer는 중국 프로그래머 CDQ의 이름을 딴 분할정복 기법의 일종입니다. 딱히 이름이 붙을 정도로 거창한 기법은 아니지만, 이후에 다룰 Relaxed Convolution의 이해를 돕기 위해 간단하게 소개하겠습니다. Relaxed Convolution은 CDQ Divide and Conquer를 사용해서 Convolution을 온라인으로 처리하는 알고리즘으로, Online Convolution, Online FFT, Relaxed Multiplication, Divide and Conquer FFT 등의 다양한 이름으로 불리기도 합니다. 이 글에서는 Relaxed Convolution이라는 용어를 일관적으로 사용하겠습니다. 이 글은 FFT의 작동 원리를 이해하지 않고 빠른 다항식 곱셈 라이브러리를 blackbox로 사용하더라도...
-
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에 속하게...