-
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)$에 해결할 수 있습니다. 이 글에서는 독자가 동적계획법으로 배낭 문제를...
-
BFV scheme에 대한 소개 - 3
Introduction 지금까지 BFV Scheme에 관한 설명글과, BFV scheme의 practical한 구현을 위해서 RNS module이라는 걸 사용한다는 것 그리고, RNS module에서 operations들이 기본적으로 어떻게 돌아가는지에 대해 설명하는 글을 썼습니다. 이번 글에서는 RNS module에서 구현하기 까다로운 연산들을 어떻게 처리하는지에 대해 설명하겠습니다. Backgrounds 저번 글에 좀 더 자세히 설명하고 있지만, Background를 한 번 더 짚고 넘어가겠습니다. RNS module은 널리 알려진 CRT(Chinese Remainder Theorem)에 기반하여 큰 범위의 수를 작은 수 여러 개로 표현하는 방식입니다. Homomorphic Encryption은 보안상의 이유 때문에 대부분...
-
Rust의 async/await
서론 지난 글에서 다양한 언어에서의 async/await에 대해 알아보았습니다. 이번 글에서는 Rust의 async/await에 대해 더 자세히 알아보겠습니다. std::future Rust의 async/await는 std::future::Future를 기반으로 합니다. std::future::Future trait은 std::future에 정의되어 있습니다. pub trait Future { type Output; fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output>; } Future trait은 poll 함수를 정의하고 있습니다. poll 함수는 Future가 준비되었는지를 확인합니다. Future가 준비되었다면 Poll::Ready를 반환하고, 아니라면 Poll::Pending을 반환합니다. 자세히 살펴보면 poll 함수는 self를 Pin<&mut Self>로 받고 있습니다. Pin의 정의를 볼까요? std::pin::Pin pub...