-
Near-Linear time Laplacian Equation Solver
Introduction Graph $G$의 Laplacian은 많은 graph problem에 관여하는 중요한 object입니다. 과거 Matrix-Tree theorem에 대해 다룬 글에서 볼 수 있듯 Laplacian의 determinant는 $G$의 스패닝 트리 개수와도 관계가 있고, 오늘 다룰 Laplacian system을 푸는 것도 굉장히 중요한 문제입니다. 또한 Laplacian의 고유값(eigenvalue)들 또한 graph의 well-connectedness와 관련이 있는 유의미한 지표로 사용할 수 있습니다. 정점이 $n$개, 간선이 $m$개인 무방향 그래프 $G$의 Laplacian $L _ {G}$는 $D - A$로 정의합니다. 여기서 $D$는 $D _ {i, i} = \deg(i)$를 만족하는 대각행렬이고, $A$는...
-
ZKP and Block Hash Oracles
이 내용은 ZK-School에서 멘토링한 자료에 기반합니다. ZKP의 목표 영지식 증명, Zero Knowledge Proof는 기본적으로 일련의 계산이 제대로 되었음을 간단하게 증명하는 것을 목표로 하고 있습니다. Zero Knowledge라는 부분도 중요하지만, 가장 핵심은 보통 Proof에 있습니다. 일단 Proof가 되어야지 Zero Knowledge를 이야기를 하겠죠? 그래서 대강 압축을 하자면, Alice가 $f(x)$라는 값을 알고 싶은데 이를 직접 계산하기에는 컴퓨팅 파워가 부족하다면, 그 컴퓨팅 파워가 있는 Bob이 $f(x)$를 직접 계산해서 $y = f(x)$라는 사실을 알아내고, Alice에게 단순히 $y$의 값을 넘기는 것이 아니라,...
-
GKR protocol and Linear Prover
Preliminaries Multilinear Extension $f(x_1, \cdots ,x_v) = \lbrace 0,1 \rbrace^v \rightarrow \mathbb{F}$ 에 대해, $f$의 domain $\lbrace 0,1 \rbrace^v$ 내에서 $f(x_1, \cdots ,x_v) = g(x_1, \cdots ,x_v)$가 성립하는 multivariable polynomial $\overline{f}$가 각각의 variable $x_1, \cdots, x_v$에 대해 linear일 때 $\overline{f}$를 $f$의 multilinear extension이라 합니다. How to build Multilinear Extension \[\overline{f}(x_1, \cdots, x_v) = \sum_{(a_1, \cdots, a_v) \in \{0,1\}^v} f(a_1, \cdots, a_v) \prod_{i=1}^v (a_ix_i + (1-a_i)(1-x_i))\] 위 식에서 $x_1, \cdots, x_v \in {0,1}^v$ 인 경우 모든...
-
A Bayesian Perspective on Federated Learning (2)
Introduction 지난 글에서는 FL을 probabilistic inference problem으로 볼 수 있다는 관점을 제시한 FedPA 알고리즘에 대해서 살펴보았습니다. FedPA는 FL에서 주로 발생하는 local device overfitting 문제를 해결하기 위해 Bayesian 방법론을 적용하였습니다. 이번 글에서는 local device에서 빈번히 발생하는 overfitting 문제가 아닌, server에서 aggregation 시 발생하는 문제를 Bayesian 방법론을 적용하여 완화한 FedBE 알고리즘을 소개해보려고 합니다. FedAvg 본 논문 또한 지난 글의 FedPA와 유사하게 FedAvg의 문제점을 제시하고 그를 Bayesian 방법론으로 완화한 논문입니다. FedAvg가 어떤 것인지는 다루지 않고 FedAvg가 가지는 문제점들에...
-
Knapsack
--- layout: post title: "Knapsack Algorithm의 여러 응용" author: knon0501 date: 2023-03-18 tags: [dynamic-programming] --- Introduction 배낭 문제란 무게제한이 있는 가방에 고유한 무게와 가치를 가지는 물건들을 채워넣을 때 어떻게 해야 최대 가치를 가방에 넣을 수 있을지 계산하는 문제입니다. 무게에 별다른 제한이 없을 경우 물건이 총 $N$개일 때 $O(2^N\times N)$정도의 시간복잡도로 계산할 수 있으며 NP-complete 임이 알려져 있습니다. 물건의 무게가 정수이고 가방의 무게제한이 $W$일 경우 동적계획법으로 $O(NW)$에 해결할 수 있습니다. 이 글에서는 독자가 동적계획법으로 배낭 문제를...