-
러스트로 PS를 해보았습니다.
서론 러스트가 신흥 프로그래밍 언어(?)로 뜨고 있습니다. 안전하면서도 빠른 실행, 자체적으로 지원하는 rustfmt와 Clippy 등의 유용한 개발 도구, Cargo를 통한 손쉬운 라이브러리 관리 등의 장점으로 큰 인기를 끌고 있고, 구글, 페이스북 등 여러 대기업이 제품에 러스트를 사용하기 시작했습니다. 대학원 연구를 위해 러스트를 배운 적이 있는데, “러스트가 미래다”라는 막연한 생각에 올해 약 반 년 동안 러스트로 백준 온라인 저지에서 문제 풀이를 진행해 보았습니다. 그 과정에서 구현한 자료구조 및 알고리즘과 전체적인 소감을 정리합니다. 스포일러: 러스트는 좋은 언어입니다....
-
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)$를 보이면...
-
Multi Party Homomorphic Encryption
Introduction Homomorphic Encryption (HE)는 secret key 가 없어도, ciphertext끼리의 evaluation이 가능한 scheme들으로, cloud computing등에 적합한 model이기 때문에 많은 관심을 받고 있습니다. Gentry가 처음으로 BGV를 제안안 이후, BFV, CKKS, TFHE 등의 scheme들이 제안됐습니다. 하지만 지금까지 제안되고, 널리 사용되는 scheme들에는 한 가지 공통점이 있는데, 그것은 하나의 고정된 secret key를 가진다는 것입니다. 얼핏 보면 당연할 수 있는 말이지만, 이는 HE scheme들이 가진 단점이기도 합니다. cloud computing 같은 걸 하면 여러 개의 party에 대해 data를 주고 받고, 해야 하는데,...
-
Fine-Tuning can Distort Pretrained Features and Underperform Out-of-Distribution (ICLR 2022 Oral)
Fine-Tuning can Distort Pretrained Features and Underperform Out-of-Distribution 최근 들어서 굉장히 많은 딥러닝 영역에서 대규모 pretrained model을 특정한 downstream task에 대해 fine-tuning 하는 방식으로 학습을 진행하는 경우가 많습니다. 이전에는 데이터 셋의 규모가 작고 지금과 같이 transformer 구조를 사용하지 않을 때에는 요즘과 같이 large pretrained model이 크게 유행하지 않았습니다. 이전에는 많은 경우에 ImageNet 정도 사이즈의 데이터 셋에서 학습한 pretraiend model의 parameter를 가져와서 이보다도 더 작은 downstream task로 fine-tuning 하였기에 특정 task들에 대해서는 transfer learning을 적용해도 성능이...
-
Erdös-Ginzburg-Ziv 정리의 O(n log n) 시간 해법 찾기
Erdös-Ginzburg-Ziv 정리는 임의의 길이 $2n-1$의 정수열에 대해 길이가 $n$이고 원소의 합이 $n$의 배수인 부분수열이 항상 존재한다는 정리입니다. 이전에 작성된 글에서는 $O(n^2/w)$ 풀이를 소개했지만, 최근에 공개된 이 부분수열을 직접 찾는 $\mathcal{O}(n \log n)$ 풀이에 대해서 소개합니다. Erdös-Ginzburg-Ziv 정리와 증명 Erdös-Ginzburg-Ziv 정리는 길이가 $2n-1$인 임의의 정수열 $A = { {a}_1, {a}_2, \cdots, {a}_{2n-1}}$에 대해 길이가 $n$이고 원소의 합이 $n$의 배수인 부분수열이 항상 존재한다는 정리입니다. $A$에 따른 $A$의 부분수열을 Erdös-Ginzburg-Ziv 정리의 해법이라고 부릅니다. Erdös-Ginzburg-Ziv가 간단한 증명을 제시했고, 이...