-
BFV scheme에 대한 소개 - 5
Introduction 지금까지 BFV Scheme에 관한 설명글들을 썼고, 저번 글에서는 RNS form에서 처리하기 까다로운 연산 중에서 BFV Multiplication을 어떻게 처리하는지에 대해서 설명을 했습니다. 이번 글에서는 저번 글에서 다 하지 못한 설명을 마무리하도록 하겠습니다. Backgrounds 이번 글은 기본적으로 저번 글에서 설명한 내용을 이어서 하는 것이기 때문에, 따로 Background는 필요하지 않으나, 저번 글의 내용을 이해하는 것이 중요합니다. 특히 FastBConv 함수의 정의에 대해서 잘 기억해 주세요. Step 4. 앞의 step 3의 결과를 다시 불러와 봅시다. \[FastRNSFloor_q(t \cdot ct[j], B_{sk})...
-
WiSE-FT: Robust fine-tuning of zero-shot models (CVPR 2022)
WiSE-FT: Robust fine-tuning of zero-shot models (CVPR 2022) 본 논문은 대규모 pretrained model에 대한 zero-shot model과 fine-tuning model의 장점을 결합하는 방식인 wiSE-FT를 제안합니다. 이에 대한 더 나은 이해를 위해, 먼저 zero-shot model이 무엇인지에 대해 이야기하고, 해당 논문이 어떠한 방법을 제안하여 해당 문제를 해결하였는지 소개하도록 하겠습니다. Zero-shot model zero-shot이란 모델을 특정 데이터 셋 A에 대해 학습시킨 이후, 이에 대한 다른 추가 train이나 fine-tuning 없이 바로 이와 다른 distribution을 가지거나 혹은 없는 라벨을 포함한 데이터 셋 B에...
-
Poly-logarithmic Randomized Bellman-Ford (2/2)
Introduction 지난 글에 이어 Bringmann 2023의 near-linear time shortest single source path (SSSP) 문제를 해결하는 부분을 더 다루어보도록 하겠습니다. 간선의 가중치가 $-W^{-}$ 이상인 weighted digraph에 대해 $\mathcal{O}(\log^{2} n \log(nW))$ 번의 dijkstra algorithm으로 shortest path tree, negative cycle 중 하나를 반환하는 문제입니다. 지난 글에서는 다음의 특수한 조건을 만족하는 Restricted SSSP (RSSSP)를 $\mathcal{O}(\log^{2} n)$ 번의 dijkstra algorithm으로 해결하는 Las-Vegas algorithm을 소개하였습니다. Definition. Directed graph $G$에 어떤 정점 $s \in V(G)$가 존재하여 다음을 만족하면 $G$를 restricted graph라고 한다....
-
완전 매칭을 찾는 병렬 알고리즘
PRAM Model PRAM (Parallel Random Access Machine) 모델은 병렬 처리를 이론적으로 표현한 모델이다. $P$개의 프로세서와 크기 $M$의 공통 메모리로 이루어져 있다. PRAM 모델에서 한 번의 (병렬) 연산은 다음과 같은 과정을 통해 이루어진다: 공통 메모리의 어떤 위치에 있는 값을 읽는다. 간단한 (unit-step) 연산을 실행한다. 공통 메모리의 어떤 위치에 값을 쓴다. 여러 개의 프로세서가 동시에 연산을 수행할 때 총돌할 가능성을 배제하기 위해, 다음과 같은 가정을 한다. 먼저, 모든 프로세서가 값 읽기 (1.)를 끝낸 다음에 연산 실행과 값...
-
A Near-Optimal Deterministic Distributed Synchronizer
Synchronized message-passing model 분산 컴퓨팅 네트워크를 undirected graph $G=(V,E)$ 로 표현하자. 각 Node는 하나의 컴퓨터 또는 프로세서의 역할을 한다. Synchronized setting에서 계산 및 커뮤니케이션은 synchronous round에 이루어진다. 각 라운드마다 각 노드는 가지고 있는 데이터로 계산을 한 후 neighbor에 하나의 메시지를 보낼 수 있고, 이 때 보낼 수 있는 메시지의 크기에 따라 두 가지 모델로 나뉜다. CONGEST 모델: 보낼 수 있는 메시지의 크기를 $O(\log N) = B$ bit로 가정 LOCAL 모델: 메시지의 크기에 제한을 두지 않음...