-
라틴 직사각형과 홀의 결혼 정리
라틴 방진과 스도쿠 라틴 방진 (Latin Square)은 서로 다른 $n$가지 기호로 구성되며, 각 행과 열에 $n$가지 기호가 모두 한 번씩 등장하게 만든 $n\times n$ 행렬입니다. 편의를 위해 $n$가지 기호 대신 $1$부터 $n$까지의 수 배열이라고 생각합시다. 라틴 방진을 만드는 방법은 여러 가지가 있는데, 가장 간단하게 생각할 수 있는 방법은 다음과 같습니다. 첫 번째 행에 $1$부터 $n$까지의 수를 순서대로 적는다. $k$번째 행에는 $k-1$번째 행을 왼쪽으로 한 칸 회전한 배열을 적는다. $(2 ≤ k ≤ n)$ 왼쪽으로 한...
-
Graph Distance Labeling Problem
Introduction 정점이 $N$개인 무방향 무가중치 그래프가 주어졌을 때, 아무 두 정점 $u, v$ 사이의 최단 경로의 길이를 질문(query)할 수 있는 자료구조를 만들고 싶다고 합시다. 일반적인 상황이라면 이 질문에 대한 답은 매우 간단합니다. Floyd-Warshall 알고리즘 등으로 정점의 최단 경로를 크기 $N \times N$ 배열 (lookup table) $d$에 저장하고, $d(u, v)$를 $O(1)$ 시간에 찾아주면 됩니다. 하지만 어떤 이유로 Lookup table $d$를 유지할 수 없다고 합시다. query time에 $d$를 접근하는 비용이 너무 큰 상황이나, 분산 네트워크 환경에서 중앙화된...
-
USACO 활용하여 문제 풀어보기
서론 USACO란 미국의 정보올림피아드로, 어렵지 않은 알고리즘을 이용하여 문제를 출제됩니다. 학생들은 등급별로 3개의 문제를 풀며 Bronze부터 Platinum 까지 승급하며 올라가는 방식입니다. 이번에는 2021년 12월에 진행되었던 USACO Silver, Gold 시험의 1번문제의 풀이를 하려 합니다. Closest Cow Wins (USACO Silver #1) 이 문제는 $K$개의 풀밭이 각각 $p_i$ 위치에 $t_i$의 맛을 가지고 있습니다. Nhoj와 John은 소를 배치하는데, 각 풀밭은 가까이에 있는 소에게 먹히게 됩니다. Nhoj의 소와 John의 소가 풀밭에서 같은 거리에 있을 때에는, Nhoj의 소가 먼저 먹게 됩니다....
-
Reverse Engineering of Generative Models
Introduction 이번 글에서는 페이스북 AI Research가 작성한 Reverse Engineering of Generative Models: Inferring Model Hyperparameters from Generated Images 논문을 소개하고자 합니다. 이 논문은 최근 딥러닝 기술의 발달로 딥페이크가 악용되고 있는 상황에서, 딥페이크를 추적하는 기술이 어떤 것이 있나 조사하는 과정에서 알게 되었습니다. 본 논문은 딥페이크 판별과 더불어 딥페이크 이미지를 생성한 모델의 property까지 추론한다는 점에서 다른 딥페이크 탐지 기술과 차별화됩니다. 또한 AI 모델의 연구 진행 과정이 잘 보이는 것 같아서 소개하게 되었습니다. 작성된 내용은 논문과 저자들 중...
-
Zero Knowledge and Groth16 Protocol
서론 최근 회사에서 Groth16, Powers of Tau, Tornado Cash에 대한 세미나를 진행했습니다. 이번 글에서는 해당 세미나의 첫 주제인 Groth16에 대해서 정리하는 시간을 갖겠습니다. 세미나 발표자료는 https://github.com/rkm0959/rkm0959_presents/blob/main/TornadoCash.pdf 에서 확인하실 수 있습니다. Zero Knowledge Proof (ZKP) Zero Knowledge Proof란, 비밀키의 소유를 증명하고자 하는 사람이 자신의 소유 사실에 대한 증명을 하되, 이를 넘어선 다른 정보는 아예 공개되지 않도록 하는 방법론입니다. 예를 들어서, Discrete Logarithm 문제가 있다고 합시다. $G$는 $\lvert G \rvert =q$가 소수인 generic group이고, $g, h$가 $G$의...