-
The Cut-Matching Game: Expanders via Max Flow
알고리즘에서 분할 정복 은 큰 문제를 부분 문제로 나누는 과정을 뜻한다. 이 때 부분 문제들이 가져야 하는 특징은, 원래 문제보다 쉬워야 하고, 부분 문제를 합칠 수 있어야 한다. 알고리즘 연구에서 분할 정복이 가지는 중요성은 어마어마하지만, 그래프에 대한 분할 정복에 대해서는 좋은 결과를 얻지 못했다. 오랜 시간 동안 이러한 분할 정복 은 트리, 평면 그래프, 혹은 이와 유사한 그래프에서만 가능한 것으로 알려져 있었다. 하지만, 그래프 알고리즘과 최적화 이론의 결합이 여러 의미 있는 성과들을 내면서, 이러한 분할...
-
2023 SCON
개요 지난 5월 20일에 진행된 2023 SCON이 성공적으로 종료되었습니다. SCON은 Soongsil Programming Contest의 약자로, 숭실대학교 IT대학 재학생들을 대상으로 하는 ICPC 성격의 3인 팀 대회입니다. 이 글에서는 2023 SCON에 출제된 문제의 풀이에 대해서 다룹니다. 대회 개최와 운영에 관한 이야기는 운영진의 블로그(링크)에서 확인하실 수 있습니다. 문제 목록 대회에는 아래 목록의 10문제가 사용되었고, 저는 이 중에서 3문제(E,F,I)를 출제했습니다. SCON에는 competitive programming 분야에 익숙하지 않은 학생들이 다수 참가하며 대회 시간이 3시간으로 짧은 편이고, 교내 ICPC 수상자가 모두 출제진으로 빠졌음을...
-
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라고 한다....