-
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$개의 정점을 점유할 수 있다. 도둑: 그래프...
-
Irrelevant Vertex Technique
서론 지난 두 편의 글에서 $\mathcal{F}$-deletion 문제에 대해 살펴보았다. $\mathcal{F}$-deletion 문제의 optimal FPT 알고리즘에서는 큰 flat wall 중심부에 irrelevant vertex가 존재한다는 사실이 매우 중요한 요소로 사용되었다. Irrelevant vertex technique은 Graph Minor Theory에서 등장하는 일종의 ‘축소’ 기법으로, Robertson과 Seymour의 Graph Minors 논문 시리즈에서 처음 등장했다. 이는 그래프에서 특정한 패턴 혹은 구조를 찾는 문제들에서 활용되며, 다음의 아이디어에 기반한다: 어떤 문제에 대해 $G$ 안에 찾고자 하는 구조의 존재 여부에 전혀 영향을 주지 않는 정점 $v$가 존재한다면, $v$를 삭제해도...
-
Phase Transitions in Networks: Scale-free Networks
0. Introduction 상전이(phase transition)는 물리학에서 나온 개념으로, 어떤 임계점을 기준으로 양쪽에서 행동이 달라지는 것을 말합니다. 물리학을 공부하는 경우 이러한 현상을 학습하게 되는데요, 대표적인 예시로 2차원 이징 모델이나 란다우 긴즈버그 모델 등이 있습니다. 놀랍게도 어떤 랜덤하게 구성한 네트워크들에 대해서도 이와 비슷한 상전이 현상이 일어남이 알려져 있습니다. 이전 글에서는 랜덤 네트워크 모델 중 모든 가능한 간선들이 연결되어있을 확률이 $p$로 일정한, 가장 간단한 모델인 Erdős–Rényi 모델에서 일어나는 상전이에 대해 알아보았습니다. 또한 이 모델이 클러스터링 문제(두 이웃이 서로 이웃일...