-
Quantum Graph
서론 그래프는 수학과 컴퓨터 과학에서 굉장히 중요하게 다루는 내용이다. 알고리즘 문제풀이만 하더라도 그래프와 관련된 알고리즘이 수 없이 많다. 이러한 그래프 이론은 최단 경로, 효율적인 네트워크 구조, 데이터 분석 등에 폭넓게 응용된다. 다들 기존에 자주 보던 그래프 (고전 그래프)에 대해서는 어느정도 익숙할 것이라 생각한다. 양자 컴퓨팅 분야가 발전하면서 고전 컴퓨팅에 존재하던 다양한 개념들을 양자 컴퓨팅으로 옮겨오는 연구들도 많이 진행되었다. 이는 한 학문이 발전하면서 흔히 보이는 현상이다. 본 글에서는 Graph의 개념을 옮겨온 Quantum Graph에 대해 소개해 보고자...
-
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가 가지는 문제점들에...