-
Polya's Enumeration Theorem을 이용한 카운팅 문제 해결
개요 Polya’s Enumeration Theorem(포여 열거 정리)는 어떤 작용에 대한 equivalence class의 개수를 구할 때 사용됩니다. 대표적인 예시로 돌리거나 뒤집어서 같은 것을 하나로 볼 때, 서로 다른 목걸이의 개수를 구하는 문제가 있습니다. 이 글에서는 Burnside Lemma와 그것의 일반화인 Polya’s Enumeration Theorem을 소개한 후 이를 적용하여 문제를 해결하는 과정을 서술하겠습니다. 관련 문제는 백준 문제집 또는 알고리즘 분류에서 찾아볼 수 있습니다. 해당 태그를 가진 문제가 9문제에 불과한 만큼 CP에서 자주 등장하는 주제는 아닙니다. 그렇지만 특정 형태의 카운팅 문제를...
-
Concurrent Non-Blocking Binary Search Tree
Intro 이전의 글에서 Concurrent non-blocking linked list를 알아보았다. 이번에는 Linearlization 및 lock-free-locks의 개념과 함께, 조금 더 복잡하고 활용도가 있는 Binary search tree의 구현에 대해서 알아보자. Linearizability BST는 Linked List와 다른 구조를 가지고 있지만, 원하는 성질 자체는 비슷하다. 여러 개의 프로세서가 동시에 효율적으로 작업할 수 있고, 그 결과들이 모두 옳아야 한다. 그런데, 여기서 ‘옳음’의 정의가 모호하다. Sequential한 환경에서는 임의의 시점에 하나의 연산만 동작할 수 있지만, Parallel한 환경에서는 동시에 여러 개의 연산이 동작할 수 있기 때문이다. 예를...
-
PIOP Improvements for ZeroCheck
Circle STARK Part 2를 하기 이전에, 최근 읽은 논문 중 간단하면서도 강력한 게 하나 있어서 이를 공유합니다. 이번 글에서는 https://eprint.iacr.org/2024/108 의 내용을 정리합니다. Zero Check Multivariate Polynomial을 기반으로 한 proof system들은, 일반적으로 boolean hypercube $H_n$ 위에서 어떤 함수 $C(x)$가 전부 0으로 계산됨을 증명하는 것으로 문제를 환원시킵니다. 결국 최종적으로 \[C(x) = 0 \quad \forall x \in H_n\] 를 보여야 하는데, 이를 위해서 verifier는 랜덤한 $\alpha$를 정한다음 \[\sum_{x \in H_n} \tilde{eq}(x, \alpha) \cdot C(x) = 0\] 을...
-
Concurrent Non-Blocking Linked List
Intro Competitive Programming에서 다루는 대부분의 자료구조들은 Sequential한 환경을 기준으로 고안되고 구현된다. 하지만 이제 단일 프로세서의 성능 개선 한계에 가까워지면서, 멀티 프로세서를 잘 활용하는 것의 중요성이 더욱 더 커지고 있다. 기존에 단일 프로세서에서 동작하던 로직을 몇몇의 일반적인 Lock이나 Shared Message Queue등을 통해 멀티 프로세서에서 동작하도록 하는 것은 성능상의 한계가 있다. 그러한 기초적이고 일반적인 방법을 통해서는 여전히 많은 부분들이 Sequential하게 남아 있어, 프로세서의 개수를 많이 늘린다고 해서 성능 개선이 많이 증가하지 않기 때문이다. 관련 분석으로는 Amdahl의 법칙을...
-
Circle STARK Part 1: Circle FFT
ZKP를 위한 Underlying Field $\mathbb{F}_p$ ZKP의 패러다임을 다루거나, ZKP를 본격적으로 분류를 하게 되면 그에 대한 가능한 기준으로는 여러가지가 있습니다. 하지만 요즘 대부분이 생각하는 방식은 (수학적으로 엄밀하거나 완전하지는 않아도) $\mathbb{F}_p$ 위에서 ZKP가 작동을 할 때 $p$가 어떤 값을 가지냐를 가지고 많이 논의를 합니다. $p$가 256 bit 정도를 가지는 경우 $p$가 64 bit 정도거나 32 bit 정도로 작은 경우 $p$가 소수가 아니라 256 bit 정도의 2의 거듭제곱인 경우 여기에 추가적으로 $p$가 NTT를 지원한다던가, 타원곡선의 크기여야 한다던가 하는...