-
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)의 개수를 계산합니다. 처음 보면 이 문제는 꽤 난감해 보입니다. 이유는 단순합니다. 어떤 차수 정점을 몇 개 쓸지부터 경우가 갈립니다. 같은 정점 개수를 써도 외부 다리 배치와 내부 연결 방식이 많습니다. 같은 모양을 중복으로 세지 않도록 정리해야 합니다. 하지만 생성함수 방법을 쓰면 이 문제가 한 줄짜리 함수방정식으로 정리되어 쉽게 해결할 수 있고, 이 과정에서 역함수를 테일러전개하는...
-
A game of cops and robbers with helicopter
서론 이전 글에서는 평면그래프에서 Cops and Robber 게임에 대해 다루었다면, 이번 글에서는 일반 그래프에서 새로운 버전의 Cops and Robber 게임에 대해 다룬다. Treewidth라는 개념을 가져와 새로운 버전의 Cops and Robber 게임과 밀접한 관련이 있음을 보인다. 1. Cops and Robber 게임의 규칙 1.1 기본 설정 유한 단순 무방향 그래프 $G$를 고정한다. 정점 집합을 $V(G)$로 표기한다. 정수 $m \ge 1$을 경찰의 수로 둔다. 게임에는 두 플레이어가 있다. 경찰: 동시에 최대 $m$개의 정점을 점유할 수 있다. 도둑: 그래프...