-
다양한 생성함수와 그 응용 (2)
개요 본문은 아래의 포스트와 내용이 이어지며, 다음 포스트의 내용을 부가적인 설명 없이 서술한다. 다양한 생성함수와 그 응용 (1) 이번에는 생성함수를 어떻게 실제 PS 문제에 적용할 수 있는지 살펴본다. 다변수 생성함수 이항계수의 생성함수 이항계수 $\displaystyle \binom{n}{k}$의 OGF를 유도하자. 먼저, 이항계수와 같은 값을 가지는 함수 $f(n, k)$를 귀납적으로 정의하자. 다음은 이항계수의 일반적인 귀납적 정의이다: 다음을 만족하는 함수 $f : \mathbb{Z}_{\ge 0}^2 \rightarrow \mathbb{R}$은 모든 음이 아닌 정수 $n$, $k$에 대하여, $\displaystyle f(n, k) =...
-
Zero-Knowledge from MPC
1. Introduction 드디어 Zero-Knowledge에 도달했습니다. 암호학에 그다지 관심이 없었다고 하더라도 최근 Zero-Knowledge가 모네로, 지캐시와 같은 프라이버시 코인에 쓰임으로 인해 Zero-Knowledge라는 단어 혹은 간단한 개념 정도는 익숙한 분이 그럭저럭 있을 것으로 보입니다. 맨 처음에는 게시글 하나를 할애해 Zero-Knowledge에 대한 설명을 하려고 했으나 evenharder님이 작성하신 대화형 증명 시스템과 영지식 증명에 설명이 잘 되어있어서 자세한 설명은 저 글로 대신하고 간단한 요약만 작성하겠습니다. 먼저 $\text{SHA256}(x) = 0^{256}$을 만족하는 $x$를 증명자가 알고 있고, 알고 있다는 사실을 검증자에게 증명하면서도 $x$ 자체는...
-
Stoer-Wagner Algorithm
안녕하세요? 오늘은 Stoer-Wagner 알고리즘에 대해 살펴보겠습니다. Stoer-Wanger 알고리즘은 그래프의 Global Minimum Cut을 찾는 알고리즘입니다. Introduction 그래프를 두 집합 $S$, $T$로 나누는 것을 그래프의 cut이라고 합니다. 간선에 weight가 있는 그래프에서, 두 점 $s$와 $t$가 주어졌을 때 $s \in S$, $t \in T$를 만족하도록 그래프를 cut하는 상황을 생각해봅시다. 한 쪽 노드는 집합 $S$에, 다른 한 쪽은 $T$에 포함된 모든 edge들의 weight의 합을 cut의 크기라고 합니다. 이 때 크기가 가장 작은 최소 cut은 최대 유량과 같다는 사실(Min-cut Max-flow...
-
Deterministic Mincut in Almost-Linear Time
Introduction 지난 3월 포스팅 “Minimum Cuts in Near Linear Time”에서 Weighted min-cut을 near-linear time에 구해주는 Karger의 Monte-Carlo algorithm을 소개한 적이 있었습니다. 이 글에서는 Karger의 알고리즘을 almost-linear complexity로 유지하며 derandomize하는 데 성공한 Jason Li의 2021년 논문 Determinstic Mincut in Almost Linear Time을 리뷰합니다. 논문 자체가 기술적으로 복잡한 부분이 많은 만큼, 깊숙한 디테일을 모두 다루기보다는 특별한 경우에 대해 이 논문에서 소개한 방법론이 어떻게 적용되는지를 다루어보도록 합니다. Terminologies 일부는 3월 포스팅과 동일하지만, Li (2021)의 문법을 대체로 따르면서 변화한...
-
2-connectivity
Connectivity Problem $k+1$개 이상의 정점을 가진 그래프 $G$가 임의의 $k-1$개의 정점을 제거하더라도 남은 그래프가 connected graph를 유지한다면 그래프 $G$를 k-vertex-connected 라고 합니다. 이때 이를 만족하는 $k$ 중 가장 큰 값을 $G$ 의 vertex connectivity 라고 합니다. 비슷한 방식으로 간선의 경우도 $k-1$개의 간선을 제거하더라도 남은 그래프가 connected graph인 경우 k-edge-connected 라고 표현하고, 그중 가장 큰 $k$ 를 $G$의 edge connectivity 라고 합니다. 아래 그림은 2-vertex-connected 그래프의 예시입니다. 어떤 정점을 삭제하더라도 남은 그래프가 연결 그래프로 유지되기 때문입니다....