-
Degree Bounded Travel Salesman Problem
1. Introduction 우리가 아는 일반적인 TSP(Travel Salesman Problem) 문제는 간선에 가중치가 있는 연결 그래프 $G = (V, E, c) (c : E \to \mathbb{R}_{\ge 0})$ 가 주어질 때 아무 정점에서 시작해 다른 모든 정점을 방문하고 다시 시작 정점으로 돌아오는 최소 비용의 이동 방법을 구하는 문제이다. 이 글에서는 Degree Bounded TSP 문제에 대해 ISAAC 2022에서 발표된 내용을 다룬다. 이 문제에서는 각 정점에 차수 제한 $b_v \ge 0 (v \in V)$ 가 추가적으로 주어진다. (단, $b_v$는 짝수인...
-
CUDA #01: Introduction to Many-Core Programming
Introduction Many-Core Programming Many-core processor는 많은 수의 core를 가져 대규모의 병렬 연산이 가능한 프로세서를 의미하며, 이를 활용하는 것을 many-core programming이라고 부른다. 유사한 용어인 multi-core는 수~수십 개 정도의 core들에 대한 의미를 주로 포함하는 것과는 달리, many-core는 그보다 훨씬 많은 수천~수만 개의 core들에 대하여 사용한다. 최근 many-core programming은 GPU(Graphics Processing Unit)가 게임, 계산과학, 인공지능 등 다양한 workload들을 처리하기 시작하면서 매우 중요해지고 있는 추세이다. 특히 GPT, ViT 등 Transformer 기반의 거대 AI 모델들은 실수의 행렬곱이라는 병렬화가 매우 잘...
-
Communication complexity
Introduction two-party model of deterministic communication (늘 그렇듯이) Alice와 Bob이라는 이름의 두 사람이 있다. 함수 $f: X \times Y \rightarrow Z$에 대해, Alice는 $x \in X$, Bob은 $y \in Y$를 알고 있을 때 두 사람이 $f(x,y)$를 최소 bit의 커뮤니케이션으로 알아내는 것이 목표이다. 즉, 목표는 $f(x,y)$의 값을 두 명이 알아내는 것이고, cost가 주고받은 bit의 개수일 때 cost를 minimize하는 문제이다. 먼저 여러 가지 $f$의 예를 살펴보며 각각 어떤 방식으로 해결하는 것이 확인해 보자. Example 1. $EQ_n: \{...
-
플로우 그래프 커팅
개요 Problem Solving을 하다 보면, 주어진 문제에서 플로우 그래프를 모델링했을 때 그래프의 크기가 너무 커서 단순히 플로우 알고리즘을 사용할 경우에 시간 초과를 받게 되는 상황이 종종 발생합니다. 이 글에서는 위와 같은 상황에서 추가적인 관찰을 통해 플로우 그래프의 크기를 줄이는 몇 가지 방법을 소개합니다. 문제마다 필요한 관찰과 해결 방법이 제각기 다를 수 있으므로 다양한 연습 문제를 예시로 들어서 설명하겠습니다. 디닉 알고리즘의 구현체를 통일하기 위해 AtCoder Library의 MaxFlow를 사용하겠습니다. 연습 문제 AtCoder Beginner Contest 320 G. Slot...
-
Secure Matrix Multiplication with Homomorphic Encryption - 1
Introduction 동형암호 (Homomorphic Encryption)은 암호문간의 연산을 평문의 정보유출 없이 가능하게 하는 암호 scheme입니다. 간단하게 말해서, 어떤 두 plaintext $m_0, m_1$을 encrypt한 것이 $ct_0, ct_1$이라고 할 때, $dec(ct_0+ct_1) = m_0 + m_1$이 성립합니다. 동형암호 scheme 중에서도, 두 가지 연산, 즉 addition과 multiplication을 제한 없이 사용할 수 있다면 그런 동형암호 scheme을 Fully Homomorphic Encryption, 줄여서 FHE라고 부릅니다. 현재 나와 있는 대부분의 동형암호 scheme의 경우, RLWE problem의 Hardness에 의존하고 있습니다. 대표적인 FHE scheme으로는 BGV, BFV, CKKS, TFHE 등이...