-
TAMREF's profile image
TAMREF
November 8, 2022
The number of topological sorts in DAG, AND polytope centroid
Introduction 문제를 풀다 보면 “조건을 만족하는 해 $x$를 찾아라” 라는 문제는 쉽게 풀 수 있지만, “조건을 만족하는 해 $x$의 개수를 찾아라” 라는 문제가 유독 어려운 경우가 많습니다. 대표적으로 2-SAT은 다항 시간 안에 해를 찾을 수 있지만, 2-SAT의 조건을 모두 만족하는 해의 개수를 찾는 것은 매우 어렵다는 것이 알려져 있습니다. 비슷하게 이분그래프의 완전 매칭은 다항 시간 안에 찾을 수 있지만, 완전 매칭의 개수를 구하는 것은 permanent라는 계산하기 어려운 식과 동치가 됩니다. 오늘 다룰 주제는 Directed Acyclic...
-
TAMREF's profile image
TAMREF
October 20, 2022
Nearly optimal communication complexity of Bipartite Maximum Matching
Introduction Bipartite Maximum Matching (BMM)은 Bipartite graph $(V = X \sqcup Y, E \subseteq X \times Y)$에 대해 크기 $F$ 이상인 Matching이 존재하는지를 묻는 decision problem, 혹은 Maximum Matching의 크기를 계산하는 문제를 이야기합니다. 굉장히 오래 전부터 연구되어 온 문제이고, 정점이 $n$개, 간선이 $m$개인 BMM은 $m^{1 + o(1)}$ 시간 안에 해결할 수 있다는 것이 알려졌습니다. 원본 문제의 시간 복잡도가 subpolynomial 수준에서 사실상 optimum을 달성했기 때문에, 비전형적인 세팅에서 BMM을 해결하는 기법들이 등장하기 시작했습니다. 그 예시가 multi-party communication으로,...
-
TAMREF's profile image
TAMREF
September 9, 2022
Shortest Even Length Cycle in Digraphs
Introduction 문제 해결을 하다 보면 종종 몇 가지 조건들을 더하고 빼며 문제를 확장시키거나, 더 포괄적인 문제를 해결합니다. 지난 글 에서는 추상화를 통해 문제를 확장하는 일련의 과정을 느낄 수 있었습니다. 이번에는 반대로 원하는 답에 몇 가지 추가적인 조건을 덧붙여 구체화된 문제를 어떻게 해결하는지 들여다보도록 합시다. “단순 무방향 그래프 $G$에 사이클이 존재하느냐?” 라는 기초적인 질문에서 출발합니다. DFS를 이용하여 해결할 수 있는 문제죠. 이 문제만 해도 몇 가지 방향으로 확장할 수 있습니다. 최소 길이: “$G$에 길이가 $k$ 이하인...
-
TAMREF's profile image
TAMREF
August 18, 2022
Characteristic Polynomial in a Commutative Ring
Introduction $n \times n$ 정사각행렬 $A = (a _ {ij})$가 주어져 있을 때, $A$의 determinant $\det A$는 아래와 같이 계산할 수 있습니다. \[\det A = \sum _ {\sigma \in S _ {n}} \mathrm{sgn}(\sigma) \cdot \prod _ {i = 1}^{n} a _ {i \sigma _ {i}}\] 오늘은 $\det A$ 와, 그를 일반화하는 특성다항식(Characteristic polynomial) $\phi _ {A}(x) = \det(x I - A) = x^{n} - \mathrm{tr} (A) x^{n-1} + \cdots + (-1)^{n-1} \det A$를 계산하는 방법을...
-
TAMREF's profile image
TAMREF
June 19, 2022
ESPiRiT을 이용한 Sensitivity Computation
Introduction 지난 글에서는 MRI의 개괄적인 원리, 즉 장비에서 얻은 raw data를 어떻게 이미지로 변환하는지에 대해 다루어보았습니다. 또한 그 중에서 scan time을 줄이기 위한 기법인 Parallel imaging과, 그로 인한 이미지 퀄리티 저하를 보상하는 알고리즘 중 SENSE, GRAPPA, 그리고 PRUNO에 대해 간략히 다루었습니다. 현재 가장 두루 쓰이는 방법은 GRAPPA, SENSE이지만 이 둘은 벌써 고안된 지 20년이 넘어가는 classic한 알고리즘입니다. Practical하진 않지만, 연구나 다른 특수한 목적으로 개발된 고성능 알고리즘들이 쏟아져나왔죠. 오늘은 그 중에서 수학적으로도 흥미롭고, 꽤 재미있는 인사이트를...
-
TAMREF's profile image
TAMREF
April 19, 2022
Relevant points in Nearest-Neighbor Classification
Introduction $k$-nearest neighbor classification이란, $d$차원 공간 위의 point cloud들 (training set)과 그 class가 주어져 있을 때, 새로운 점의 class를 예측하는 한 가지 방법입니다. 자신과 가장 가까운 $k$개의 점의 label 중 가장 많은 것을 선택하는 방법으로, 고전적인 pattern recognition method 중 하나로 소개되었습니다. 오늘은 이 중 그나마 알고리즘의 시각에서 조명이 가능한 $k = 1$ case, 즉, nearest-neighbor classification에 대해 알아봅시다. 1-NN classification and Voronoi diagram $d = 2$인 경우, 어떤 점 $p$의 nearest neighbor가 $q$일 필요충분조건은...
-
TAMREF's profile image
TAMREF
March 20, 2022
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$를 접근하는 비용이 너무 큰 상황이나, 분산 네트워크 환경에서 중앙화된...
-
TAMREF's profile image
TAMREF
January 16, 2022
Faster Exponential Algorithm for Permutation Pattern Matching
Introduction “스택 수열”이라는 간단한 문제를 생각해 봅시다. https://www.acmicpc.net/problem/1874 이 문제는 스택을 이용한 시뮬레이션으로 해결할 수 있습니다. 요약하면, $[n] := {1, \cdots, n}$의 순열 $\sigma _ {1}, \cdots, \sigma _ {n}$이 주어졌을 때, $1, \cdots, n$을 순서대로 스택에 push(+)했다가 pop(-)하여 $\sigma _ {1}, \cdots, \sigma _ {n}$을 만들 수 있는지를 판별하는 문제입니다. 반대로 $\sigma _ {1}, \cdots, \sigma _ {n}$을 push-pop하여 $1, \cdots, n$으로 정렬할 수 있는지를 묻기도 하는데요, 이 경우에 $\sigma$를 stack-sortable permutation이라고 합니다. “스택...
-
TAMREF's profile image
TAMREF
December 19, 2021
MRI imaging과 Parallel Imaging Algorithm, 그리고 PRUNO
Introduction MRI (Magnetic Resonance Imaging)은 X-Ray, CT와 함께 널리 쓰이는 의료 영상 기법으로 손꼽힙니다. 이미지 특성 상 가장 좋은 연부 조직 대비 (soft matter contrast)를 보여줍니다. 즉, 근육이나 뇌 등 수분을 많이 포함하는 조직에 대해 가장 월등한 이미지 품질을 낼 수 있습니다. 다만 MRI의 경우 짧게는 30분에서 1시간 정도 되는 긴 촬영 시간이 단점으로 꼽히는데, 때문에 시간 단축을 위한 다양한 기법이 제시되고 있습니다. MRI는 촬영한 raw data가 전자기파 신호이기 때문에, 특이하게도 이를 푸리에 변환을 비롯한...
-
TAMREF's profile image
TAMREF
July 18, 2021
A Topological Approach to Evasiveness
스무고개 간단한 게임을 하나 생각해 봅시다. A와 B가 게임을 하는데, 아직 결정되지 않은 $n$자리 이진수가 있습니다. A는 B에게 $i$번째 비트가 $1$인지 물어볼 수 있고, B는 이를 답해줍니다. 질문을 $n$번보다 적게 써서 이 수가 $3$의 배수인지 맞힐 수 있다면 A의 승리, 그렇지 않다면 B의 승리입니다. 물론 B는 특정 수를 정해놓고 시작해야 하는 게 아니기 때문에, 질문에 따라 얼마든지 마음속으로 답을 바꿀 수 있습니다. 누가 승리할까요? leading zero 등의 제한 조건은 없습니다. 당연하게도, 이 게임은 B의 손쉬운...
-
TAMREF's profile image
TAMREF
May 16, 2021
Deterministic Mincut in Almost-Linear Time
Introduction 지난 3월 포스팅 “Minimum Cuts in Near Linear Time”에서 Weighted min-cut을 near-linear time에 구해주는 Karger의 Monte-Carlo algorithm을 소개한 적이 있었습니다. 이 글에서는 Karger의 알고리즘을 almost-linear complexity로 유지하며 derandomize하는 데 성공한 Jason Li의 2021년 논문 Determinstic Mincut in Almost Linear Time을 리뷰합니다. 논문 자체가 기술적으로 복잡한 부분이 많은 만큼, 깊숙한 디테일을 모두 다루기보다는 특별한 경우에 대해 이 논문에서 소개한 방법론이 어떻게 적용되는지를 다루어보도록 합니다. Terminologies 일부는 3월 포스팅과 동일하지만, Li (2021)의 문법을 대체로 따르면서 변화한...
-
TAMREF's profile image
TAMREF
April 18, 2021
Resistor Network와 Series-Parallel Graph Class
Introduction Childhood 중학교에서 전기 회로에 대해 배울 때를 떠올려 봅시다. “전압 $V$는 전류 $I$와 저항 $R$의 곱과 같다”는 옴의 법칙을 배운 뒤, 저항이 여러 개 연결되어 있을 때, 저항값이 같은 하나의 합성 저항으로 바꾸는 방법을 배웁니다. 바로 직렬 연결과 병렬 연결이죠. 직렬 연결. 저항 $R _ {1}$과 $R _ {2}$가 직렬로 연결되어 있다면, 합성 저항 $R _ {eq}$는 $R _ {eq} = R _ {1} + R _ {2}$를 만족한다. 병렬 연결. 저항 $R...
-
TAMREF's profile image
TAMREF
March 21, 2021
Minimum Cuts in Near-Linear Time
Introduction Weighted graph $G$에 대해, $G$의 min-cut 혹은 edge connectivity 는 $G$의 connected component가 둘 이상이 되도록 하기 위해 제거해야 하는 가중치 합으로 정의됩니다. 이름 그대로 네트워크를 단절시키기 위해 필요한 최소 비용으로, 수많은 파생과 응용이 가능합니다. 이 글에서는 $n$개의 정점, $m$개의 간선을 가진 weighted graph $G$의 min-cut을 near-linear time ($\tilde{O}(m)$)에 구하는 최초의 방법인 D. R. Karger의 Minimum Cuts in Near-Linear Time을 리뷰합니다. Definition 그래프 $G$는 non-negative weighted graph로 가정합니다. 즉, weight는 음 아닌 실수 값을...