-
Learning-augmented Algorithm 소개
서론 전통적으로 알고리즘을 생각해보자. 근사 알고리즘의 경우에는 근사비(approximation ratio), 온라인 알고리즘의 경우에는 경쟁비(competitive ratio)가 성능 측정의 지표가 되며, 최악의 경우(worst-case)의 성능 및 평균적인 기대 성능(average-case, under distributional assumption)을 guarantee 하는 것을 목표했다. 기계학습 기술의 발전으로, 현실에서는 종종 문제와 관련한 예측 값을 얻을 수 있다. 이것은 기계학습 모델이 주는 것일 수도 있고, 과거 데이터 기반 통계량일 수도 있다. 그러나, 현실에서 얻을 수 있는 예측 값은 대개 “얼마나 정확한지”에 대해 아무것도 보장된 게 없다. 예측이 있는 상황에서의...
-
Power Projection of Set Power Series
Introduction 이 글에서는 power projection of set power series를 $O(N^2 2^N+M)$에 계산하는 알고리즘에 대해 알아볼 것이다. 이를 이용해 정점이 $N$개인 그래프의 chromatic polynomial을 $O(N^2 2^N)$에 계산하는 알고리즘도 함께 다룬다. 이 글에서는 Operations on Set Power Series의 내용을 모두 이해했다고 가정하고 설명한다. Power Projection of Set Power Series Set $G = { g_0, g_1, \cdots, g_{N-1} }$과 commutative ring $R$에 대해 정의된 set power series $\mathcal S_G(R)$에 대해 생각하자. 주어진 $a,w \in \mathcal S_G(R)$와 $M \in...
-
Parallel Algorithm for Bipartite Graph Perfect Matching
매칭을 바라보는 새로운 시각 그래프 이론에서 이분 그래프 매칭은 두 개의 독립된 정점 집합 사이에서 간선이 겹치지 않게 연결 쌍을 만드는 고전적인 문제입니다. 우리는 보통 이 문제를 접할 때, 정점 하나하나를 거쳐 가며 비어 있는 짝을 찾아가는 Augmenting Path 방식에 익숙해져 있습니다. DFS/BFS 기반의 알고리즘은 $O(VE)$의 시간에 작동하며, 이를 최적화한 Hopcroft-Karp 알고리즘은 $O(E\sqrt{V})$라는 준수한 성능을 보여줍니다. 이번에 소개할 알고리즘은 그래프를 행렬로 변환한 뒤 행렬식을 구함으로써, perfect matching의 존재성을 행렬 곱셈 시간복잡도인 $O(n^\omega)$ ($\omega \approx 2.37$)...
-
QAC0 and PARITY
Introduction 이 글은 Quantum Complexity의 후속편입니다. 지난 글에서 QAC$^0$, QAC$^0_f$, PARITY 문제의 배경을 소하고, fourier analysis 를 소개했다면, 이번 글에서는 QAC$^0$ 회로가 PARITY를 풀수 있는지 없는지에 대한 현재까지의 연구를 소개하는게 목표입니다. 이번 글에서 다룰 것들 먼저 문제의 세팅을 짚고 넘어갈 예정입니다. QAC$^0$, QAC$^0_f$ 와 같은 복잡도 클래스를 간단히 다루고 PARITY 문제를 다시 소개합니다. QAC$^0$가 PARITY를 계산할 수 있는지 없는지는 아직까지 Open problem입니다. 이와 관련되어 lower bound, upper bound를 증명하는 연구들을 소개하겠습니다. 이 내용에는 pauli analysis,...
-
Counting Trees with Fixed External Legs and Quantum Field Theory
0. Intro 이번 글에서는 다음 문제를 풉니다. 허용된 정점 차수 집합(예: 3차, 4차)이 주어졌을 때, 외부 다리가 $n$개인 트리($n$-point tree)의 개수를 계산합니다. 처음 보면 이 문제는 꽤 난감해 보입니다. 이유는 단순합니다. 어떤 차수 정점을 몇 개 쓸지부터 경우가 갈립니다. 같은 정점 개수를 써도 외부 다리 배치와 내부 연결 방식이 많습니다. 같은 모양을 중복으로 세지 않도록 정리해야 합니다. 하지만 생성함수 방법을 쓰면 이 문제가 한 줄짜리 함수방정식으로 정리되어 쉽게 해결할 수 있고, 이 과정에서 역함수를 테일러전개하는...