-
ainta's profile image
ainta
January 29, 2024
Garbled Circuit and Functional Encryption
Introduction 이 글에서는 Multi-party computation(MPC)에서 사용되는 Garbled Circuit과 Oblivious Transfer에 대해 알아볼 것입니다. 그 뒤에는 public key encryption을 확장한 개념인 Functional Encryption이라는 개념을 소개할 것입니다. 배경지식이 크게 필요하지 않도록 작성했기 때문에, 암호학에 관심이 있는 독자들에게 흥미를 줄 수 있기를 바랍니다. Garbled Circuit Garbled Circuit(GC) 는 두 사람 $Alice$와 $Bob$이 각각 input $x$와 $y$를 갖고 있을 때, 서로에게 자신의 input을 노출하지 않고 $f(x,y)$를 계산하는 two-party computation을 위해 고안되었습니다. 이는 필자의 직전 포스트인 two-party communication 모델과 동일하지만,...
-
ainta's profile image
ainta
December 26, 2023
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: \{...
-
ainta's profile image
ainta
October 30, 2023
Maximum matching in CONGEST model
Introduction 이전에 작성한 글 A Near-Optimal Deterministic Distributed Synchronizer에서 잠깐 언급하였듯이, Distributed Graph Algorithm에서는 어떠한 모델을 가정하고 있는지에 따라 문제를 접근하는 방법이 달라지게 된다. 해당 포스트에서는 Asynchronized model을 가정하고 synchronized model처럼 문제를 해결할 수 있도록 도움을 주는 synchronizer에 대한 내용을 작성하였다. 이번 포스트에서는 synchronized model 중 하나인 CONGEST model을 가정하고, graph theory의 중요한 문제 중 하나인 maximum matching problem이 어떤 식으로 해결 가능한지에 대해 알아보도록 할 것이다. Synchronized message-passing model 분산 컴퓨팅 네트워크를 undirected graph...
-
ainta's profile image
ainta
September 24, 2023
Interior Point Methods for Maximum Flow
Introduction 2021년 Maximum Flow는 Almost-Linear Time에 풀린다는 결과가 발표되었다 (이는놀랍게도 Minimum cost Flow에 대해서도 성립하는 명제이다). 이에 관련하여 공부할 수 있는 자료로는 Rasmus Kyng의 Advanced Graph Algorithms and Optimization 강의가 있어 이에 대한 스터디를 진행하였다. 이 강의의 Chapter 17인 “Interior point mehods for maximum flow” 를 정리해서 소개하려고 한다. 17장에서는 16장까지 다루었던 테크닉을 통해 undirected graph의 maximum flow 문제를 $\tilde{O}(m^{1.5})$ 시간에 해결하는 알고리즘을 제시한다. 16장까지 많은 정보가 소개된 만큼, 이 글은 self-contained되지 않았다. 그러니 어떤...
linear algebra combinatorial optimization convex optimization
-
ainta's profile image
ainta
August 20, 2023
Introduction to Bilateral Trade
Bilateral Trade Bilateral Trade란 기본적으로 구매자 한 명과 판매자 한 명이 item을 거래하는 것입니다. 즉, 다음과 같은 구성 요소로 이루어진다고 볼 수 있습니다: 두 agent: 구매자와 판매자 구매자의 item에 대한 평가(valuation) $B \sim F_B$, 판매자의 평가 $S \sim F_S$ 여기에서 $F_B$와 $F_S$는 각각 $B$와 $S$가 선택되는 확률분포를 뜻합니다. Bilateral Trade Mechanism Bilateral Trade에서의 Mechanism이란 다음 두 가지 함수를 어떻게 설정하는지를 뜻합니다. 할당 함수(allocation function) $A:\mathbb{R} \times \mathbb{R} \rightarrow { 0, 1 }$. 두 reported valuation...
-
ainta's profile image
ainta
July 24, 2023
Faster Matroid Intersection - Part 2
이번 포스트에서는 전 글에서 subquadratic approximation algorithm의 결과를 얻었다고 소개했던 Faster Matroid Intersection(2019)에 대해 다룬다. Preliminaries 전 글과 동일하게, matroid $\mathcal{M_1} = (V, \mathcal{I_1}), \mathcal{M_2} = (V, \mathcal{I_2})$가 주어진 세팅이다. 이제 본격적으로 Matroid Intersection 알고리즘에 들어가기 전에 필요한 성질들에 대해 먼저 알아보자. Submodularity of rank. $A, B \subset V$에 대해, $rank(A \cup B) + rank(A \cap B) \le rank(A) + rank(B)$가 성립한다. Proof. $rank(A \cup B) - rank(A) \le rank(B) - rank(A \cap B)$를 보이면...
-
ainta's profile image
ainta
June 25, 2023
Faster Matroid Intersection - Part 1
0. Introduction 필자는 Matroid를 소개하는 글 및 Matroid Intersection을 소개하는 글을 2019년에 작성한 바 있다. Matroid Intersection은 해당 글에도 나와 있듯 다양한 문제들을 해결할 수 있는 툴이 되며, 이에 따라 많은 연구가 진행되었다. 특히, 2019년을 기점으로 하여 Matroid Intersection을 어떻게 하면 빠르게 할 수 있을지에 대해 여러 논문의 결과가 발표되기 시작했다. 대표적인 예시로 다음과 같은 4가지 논문이 존재하고, 앞으로는 다음 논문들의 결과에 대해 다룰 것이다. A note on Cunningham’s algorithm for matroid intersection(2019) Faster Matroid...
-
ainta's profile image
ainta
May 21, 2023
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 모델: 메시지의 크기에 제한을 두지 않음...
-
ainta's profile image
ainta
April 24, 2023
Linear-Time Encodable Linear Code
Error-correcting code $[n, k, d]$ code: 길이 $k$인 message $m$을 길이 $n$인 codeword $Enc(m)$으로 인코딩하는 $Enc$에 대해, 서로 다른 두 message의 codeword의 hamming distance (서로 다른 entry의 개수)가 항상 $d$ 이상일 때 이를 $[n, k,d]$ code라 합니다. 이 때 가장 가까운 두 codeword가 서로 다른 비율을 나타내는 $\Delta = \frac{d}{n}$을 code의 relative distance라고 부릅니다. Example: Repitition code 예를 들어, “0101”을 “000111000111”로 encoding하는, 원래의 비트를 세 번씩 반복하는 repitition code의 경우 이는 $[3k, k, 3]$ 코드이고,...
-
ainta's profile image
ainta
March 19, 2023
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$ 인 경우 모든...
-
ainta's profile image
ainta
February 19, 2023
SOAP: Schedule Ordered by Age-based Priority
Introduction Scheduling Policies 우리는 흔히 일상 생활에서 효율적인 일처리를 위해 todo list를 만들거나 시간 단위로 스케줄을 나누어 계획을 세우곤 합니다. 또한, 컴퓨터의 CPU는 여러 개의 처리해야 할 task이 있을 때 어떤 일부터 처리해야 할지 정하고 task를 수행합니다. 이 때 어떤 일부터 처리할지를 잘못 결정한다면 특정 일은 처리하는 시간이 너무 늦어지는 현상이 발생합니다. 이에 대한 결과로 과제를 늦게 제출하거나, 컴퓨터 화면이 멈춰버리는 등의 불상사가 발생하곤 합니다. 처리하는 주체를 server, 처리되어야 하는 일을 job, job들의 대기열을 queue이라고...
-
ainta's profile image
ainta
January 18, 2023
Geometric Deep Learning
Introduction 먼저, geometric deep learning에 대해 좀 더 알아보고 싶으신 분은 이 분야의 founder들이 작성한 놀라울 정도로 잘 쓰인 글이 있기 때문에 일독을 권합니다. 앞으로 이 글의 거의 대부분의 내용들은 위 자료를 따릅니다. 지난 10여년간 딥러닝은 엄청나게 빠르게 발전하며 컴퓨터 비전을 비롯하여 chatgpt에 이르기까지 다양한 산업에 수많은 변화를 가져왔습니다. 그리고 아직도 매일같이 수많은 논문이 쏟아져 나오고 있습니다. 각 논문들에서는 학습하는 데이터에 최적화된 각기 다른 neural network 구조를 사용하고 있고, 결국 우리는 성공적으로 동작하는 CNN, RNN,...
-
ainta's profile image
ainta
December 18, 2022
Isogeny-based cryptography
Introduction 현재 사용되고있는 공개키 암호 시스템은 많은 수가 기본적인 RSA의 변형으로 discrete logarithm problem(이산로그) 또는 integer factorization problem 문제의 어려움을 기반으로 하고 있으며, 타원곡선 상에서의 연산에 기반한 시스템 역시 elliptic-curve discrete logarithm problem(ECDLP)을 기반으로 합니다. 이 3가지 문제들은 모두 양자컴퓨터상에서 Shor’s algorithm으로 빠른 시간에 풀 수 있음이 알려져있기 때문에, 양자컴퓨터가 등장하더라도 그 안전성을 보장할 수 있는 post-quantum cryptography algorithm이 필요하게 되었습니다. NIST(미국 국립표준기술연구소) 에서는 양자컴퓨터의 출현에도 안전한 Post-Quantum Cryptography의 표준화를 위해 여러 알고리즘들을 제출받아서 보안성과...
-
ainta's profile image
ainta
October 20, 2022
SAT problem의 변형과 Schaefer’s Dichotomy Theorem
Boolean Formula, SAT $(x \lor \neg y) \land (\neg x \lor z)$와 같은 식을 Boolean formula라 한다. Boolean formula의 변수(variable)는 True/False (또는 1/0이라고도 한다)의 두가지 값만을 가질 수 있다. 위 boolean formula의 variable은 $x, y, z$이다. 각 연산자에 대해 알아보면 $\lor$ 와 $\land$는 각각 logical OR(disjunction)/ logical AND (conjunction)를 나타내고, $\neg$(negation)는 NOT을 나타내는 연산자로 피연산자가 True였다면 False로, False였다면 True로 바꿔주는 역할을 한다. 식에서 각각의 항 $x, \neg y, \neg x, z$는 literal이라 한다. $x, y$와...
-
ainta's profile image
ainta
September 18, 2022
Low degree optimal polynomial의 계산기하적 접근
Optimal Polynomial 일반적으로 함수 $f(x)$와 차수 $d$가 주어졌을 때, $\lvert P(x) - f(x) \rvert$의 최댓값 를 최소화하는 $d$차 다항함수를 $f$에 대한 degree $d$의 optimal polynomial 이라 합니다. 그러나 이러한 $P$를 구해야 하는 상황에서는 보통 함수 $f$를 모르는 상태에서, $f$가 $d$차 이하의 다항식일 것이라고 가정한 후 $P$를 추측해야 하는 경우가 잦습니다. 몇 개의 $x_i$에 대해 $f$의 실험값 $y_i = f(x_i) + \epsilon_i$ 가 주어져있을 때 오차 $\max (\lvert P(x_i) - y_i \rvert)$를 최소화하는 $P$를 어떻게 구할...
-
ainta's profile image
ainta
August 21, 2022
Formal Power Series와 Operation의 빠른 계산 방법
Introduction Polynomial Ring Field $\mathbb{F}$에 대해 Polynomial Ring $\mathbb{F}[x]$는 다항식(polynomial)들의 집합으로 정의되며, 다항식들은 각 계수 $p_i$가 $\mathbb{F}$의 원소인 $p = p_0 + p_1x + … + p_mx^m$ 꼴로 표현됩니다. 여기에서 Ring이란 간단히 말해서 덧셈과 곱셈이 정의되어 있고 해당 연산들에 대해 결합법칙이 성립하고 항등원이 정의되어 있으며 덧셈에 대해서는 교환법칙이 성립하는 집합을 말합니다. Field는 여기에 0을 제외한 모든 원소에 대해 곱셈에 대한 역원이 존재하는 경우입니다. Polynomial Ring 같은 경우는 다항식의 곱셈과 덧셈으로 자연스럽게 정의됨을 알 수 있습니다....
-
ainta's profile image
ainta
July 17, 2022
IND-CCA2 Encryption schemes and Fujisaki-Okamoto transform
Introduction 암호의 안전성 암호는 수천년 전에 로마나 고대 그리스에서 사용하던 고전암호로부터 시작해 20세기 초에는 상당히 발전되어 전쟁에서 사용되기도 했으며, 그 후 현재까지 쓰이고 있는 대칭키 암호(symmetric key cryptography) 및 공개키 암호(public key cryptography)가 개발되었습니다. 현재는 그 외에도 Lattice-based cryptography 등의 여러 암호가 활발하게 연구되고 있습니다. 초창기의 암호 중 몇몇은 하나의 문자가 하나의 문자에 대응되는 형식을 띠고 있습니다. 이러한 암호의 경우 문자마다 실제 단어에 사용되는 빈도가 달라 암호문이 충분히 주어진다면 그 빈도를 파악하여 대응되는 문자를 파악하여...
-
ainta's profile image
ainta
June 20, 2022
Gomory-Hu Tree in Subcubic Time
Introduction mincut terminology 무방향 그래프 $G = (V,E)$ 의 각 edge에 대해 양의 정수 weights $w: E \rightarrow Z_{+}$ 정의되어 있다고 하자. 정점들의 집합 $S$가 $s \in S, t \notin S$를 만족할 때 $S$를 $(s,t)$-cut 이라 한다. 이 때, $S$의 weight $\delta(S) = \Sigma_{e\in E(S, V \setminus S)} w(e)$ 가 최소인 경우를 ($s$,$t$)-mincut 이라 하고, 그 weight를 $\lambda(s,t)$라 한다. Gomory-Hu Tree Gomory-Hu Tree는 모든 $(s,t)$에 대한 mincut을 encoding하는 Tree이다. 다음과 같은 두 definition으로 정의 가능하다....
-
ainta's profile image
ainta
April 19, 2022
Compressed Sensing
Introduction Compressed Sensing(CS)이란 어떠한 신호(signal)를 효율적으로 수집 및 복원하는 기법으로, 이미지 압축이나 복원, 카메라 센서 등에 사용되는 기술이다. 간단히 예를 들어 설명하자면, N개의 픽셀로 이루어진 사진을 얻기 위해서는 N번의 observation이 필요하다고 생각하는 것이 일반적이라면 CS를 이용하는 경우 훨씬 적은 측정으로도 이를 loss 없이, 또는 매우 적은 loss로 얻을 수 있다. 이 글에서는 CS 이론의 배경과 기반 및 실제 적용에 대해 간략히 살펴본다. History Nyquist-Shannon sampling theorem $f(t)$ 가 $B$ 헤르츠 이상의 주파수를 가지지 않을 때,...
-
ainta's profile image
ainta
March 20, 2022
Casual Inference and Diagram
Introduction Simpson’s Paradox 한 제약회사가 어떤 질병에 대해 치료제를 개발한 후 이 치료제가 실제로 효과가 있는지 700명의 환자들을 대상으로 실험을 진행하였다. 환자들의 3개월간 회복 경과를 지켜본 결과 아래와 같이 나타났다. 치료제 사용 치료제 미사용 남성 81/87 회복 (93%) 234/270 회복 (87%) 여성 192/263 회복 (73%) 55/80 회복 (69%) 합산 273/350 회복 (78%) 289/350 회복 (83%) 각각의 성별에 대해서는 분명 치료제를 사용한 경우에 더 회복률이 높았지만, 합산 회복률은 치료제를 사용하지 않았을 때 오히려 더 높게...
-
ainta's profile image
ainta
June 20, 2021
Perfect Graph
Perfect Graph Graph Theory에서 유명한 그래프 종류 중에 하나로 완전그래프(Complete Graph)를 꼽을 수 있을 것이다. 완전그래프는 모든 vertex 쌍 사이에 edge가 하나 존재하는 그래프이다. 그렇다면 Complete와 비슷하게 또 완전하다, 완벽하다라는 뜻을 가진 perfect 라는 형용사가 붙는 Perfect Graph는 무슨 뜻일까? 안타깝게도 Perfect Graph는 Complete Graph처럼 직관적인 종류의 그래프는 아니다. Perfect Graph에 대해 정의하기 전에 다음을 정의하자. vertex set이 $V$, edge set이 $E$인 그래프를 $G = (V,E)$ 라고 표기한다. $V’ \subset V$ 에 대해, $E’ =...
-
ainta's profile image
ainta
December 13, 2020
IOI 2020 및 SNUPC 2020 출제후기
SNUPC 2020 출제후기 SNUPC 2020에는 Div.1의 총 9문제중 절반 정도에 해당하는 4문제를 출제하였다. 재미있는 문제를 낼 수 있어서 만족스러웠다. 그리고 imeimi2000, TAMREF 등 여러 출제진 검수진들이 고생해 준 덕분에 문제 데이터와 지문의 퀄리티가 올라가서 성공적인 대회가 될 수 있었던 것 같다. 9문제 중 대부분이 자명하지 않고 아이디어를 필요로 하는 문제들이라서 아직 풀어보지 않은 분들은 시도해 보고 나서 글을 보면 좋을 것 같다. 자세한 풀이는 여기 에 있으니 여기에는 담지 않는다. A. 빈 문자열 만들기 링크...
-
ainta's profile image
ainta
December 15, 2019
Cactus graph realization of degree sequence
Degree sequence 그래프에서, Degree sequence란 undirected graph의 각 정점의 차수(degree)를 늘어놓은 수열을 말한다. Graph realization problem이란, 수열이 주어졌을 때 그 수열을 degree sequence로 갖는 그래프를 실제로 construct하는 문제를 말한다. 여기서 다루는 그래프는 self-loop나 multiedge가 존재하지 않는 simple graph이다. 어떤 Degree sequence가 주어졌을 때, 이를 만족하는 simple graph가 존재할 조건은 Erdos - Gallai theorem 으로 널리 알려져 있다. 정리 1 (Erdos - Gallai theorem). $d_1 \ge d_2 \ge … \ge d_n \ge 0$ 가 finite simple...
-
ainta's profile image
ainta
November 17, 2019
2018 ICPC world Finals C. Conquer the world와 Tree DP optimization
2018년 World Finals에서 어느 팀도 풀지 못했던 문제인 Conquer the world(https://www.acmicpc.net/problem/15691) 문제에 대한 풀이와 사용된 아이디어에 대해 간단히 소개한다. 문제 문제 자체는 굉장히 간단하다. edge마다 이동할 때 드는 cost가 있는 트리가 있고, vertex $i$에 현재 $X_i$명이 있으며 최종 상태에는 적어도 $Y_i$명이 있어야 할 때, 사용해야 하는 cost를 minimize하는 문제이다. Heavy-Light Decomposition 이미 상당히 유명해진 트릭인 heavy-light decomposition에 대해 먼저 간략히 설명하고 넘어갈 것이다. rooted tree에서 heavy edge란, vertex $v$의 자식들 중 가장 subtree의 크기가 큰(vertex...
algorithm dynamic-programming ICPC data-structure optimization
-
ainta's profile image
ainta
September 17, 2019
Counting the number of topologies on a finite set
Topology 수학에서, topological space란 다음 조건을 만족하는 집합 $X$와 $X$의 subset들의 collection $\tau$에 대해 ordered pair $ (X, \tau) $ 를 말한다. $ \phi, X \in \tau $ Any arbitrary union of members of $ \tau$ still belongs to $ \tau$. ($ \tau$의 원소들의 합집합은 $ \tau $의 원소이다) The intersection of any finite number of members of $ \tau$ still belongs to $ \tau$. ($ \tau$의 원소 유한개의 교집합은 $ \tau $의 원소이다) 이때...
-
ainta's profile image
ainta
June 17, 2019
Matroid Intersection
Matroid Intersection Recall matroid $\mathcal{M} = (S, \mathcal{I})$ 에서 $S$는 유한집합, $ \mathcal{I} \subset 2^S$ 는 독립집합(independent set)들의 collection이다. 이 때, $I$는 다음 세 가지 조건을 만족하여야 한다. $\phi \in \mathcal{I}$ $Y \subset X, X \in \mathcal{I} \Rightarrow Y \in \mathcal{I}$ $X, Y \in \mathcal{I}, \lvert X \rvert < \lvert Y \rvert$ 이면 $X + y \in \mathcal{I}$ 를 만족하는 $y \in Y \setminus X$가 존재 매트로이드는 다양한 집합에서 정의될 수 있다. 그 중 대표적인...
-
ainta's profile image
ainta
May 15, 2019
Introduction to matroid
Matroid 정의 1. matroid $\mathcal{M} = (S, \mathcal{I})$ 에서 $S$는 유한집합, $\mathcal{I} \subset 2^S$ 는 독립집합(independent set)들의 collection이다. 이 때, $I$는 다음 세 가지 조건을 만족하여야 한다. $\phi \in \mathcal{I}$ $Y \subset X, X \in \mathcal{I} \Rightarrow Y \in \mathcal{I}$ $X, Y \in \mathcal{I}, \lvert X \rvert < \lvert Y \rvert$ 이면 $X + y \in \mathcal{I}$ 를 만족하는 $y \in Y \setminus X$가 존재 매트로이드는 다양한 집합에서 정의될 수 있다. 그 중 대표적인 예...
-
ainta's profile image
ainta
March 10, 2019
Perfect Elimination Ordering in Chordal Graph
개요 Chordal Graph Chordal Graph란, 길이 4 이상의 모든 simple cycle이 chord를 포함하는 그래프를 말한다. 여기서 chord란 cycle에 포함되는 edge는 아니지만 cycle에 포함하는 두 vertex를 잇는 edge를 뜻한다. 즉, 어떤 4개 이상의 vertex를 고르더라도 그 vertex들로 이뤄진 induced subgraph가 simple cycle이 되지 않는 그래프이다. 두 겹치는 구간을 edge로 연결한 Interval graph가 Chordal graph의 한 예이다. 위는 chordal graph의 예이다. 임의의 길이 4 이상인 cycle이 chord를 포함함을 쉽게 알 수 있다. 위는 chordal graph가 아닌 그래프의...