-
Moving Least Squares Projection
Point Based Graphics Point Based Graphics는 컴퓨터 그래픽스의 한 분야로, 기존의 다각형 기반으로 형상을 모델링하는 기법인 Polygon Based Graphics와 달리 점들을 사용하여 3D 객체의 표면을 표현하는 기법입니다. 각 점은 위치 뿐만 아니라 그 지점의 색상과 텍스쳐 등 다양한 속성도 가질 수 있습니다. 여기서 객체를 표현하는데 사용된 점들의 집합을 Point Cloud라고 합니다. 이 Point Cloud가 조밀할수록 더욱 세밀한 형태를 표현할 수 있습니다. Point Based Graphics는 복잡한 형상을 기존 기법보다 더 효율적이고 자세하게 표현할 수 있다는 장점이...
-
Software Combining
Intro 지난 포스트들에서는 구체적인 자료구조 (BST, List 등)을 concurrent하게 어떻게 구현할 수 있을지를 살펴보았다. 이번에는 조금 더 일반적인 트릭인 software combining 에 대해서 알아보자. 표현이 조금 모호할 수 있으나, 이 주제의 관심사는 ‘여러 스레드가 효율적으로 하나의 shared object에 연산을 하는 방법’의 한 갈래로, 한 스레드가 여러개의 스레드의 연산을 한꺼번에 처리해주는 것에 대한 논의이다. 그렇기 때문에 software ‘combining’이라는 이름으로 불린다. 가장 일반적인 논의는 ‘임의의 sequential한 object를 concurrent하게 wrapping하는 법’인 universal construction에 대한 것이 되겠지만, 이번 포스트에서는...
-
Grid Minor Theorem과 Erdős–Pósa Properties
Introduction : Erdős–Pósa Theorem Feedback Vertex Set (FVS) 이란, 그래프에서 $m$ 개 이하의 정점을 제거하여 forest로 만들 수 있는지를 묻는 문제입니다. 보다 엄밀하게, $G[V - X]$ 에 사이클이 존재하지 않는 $\lvert X \rvert \le m$ 이 존재하는지를 판별하는 문제입니다. 가령 아래 그래프에는 크기 2의 feedback vertex set $\lbrace B, D\rbrace$가 존재합니다. 일반적으로 FVS는 NP-complete 문제임이 알려져 있지만, 제거할 정점의 개수 $m$ 이 상수라고 가정하면 그래프의 크기에 대해서는 다항 시간에 해결할 수 있습니다. 예를 들어 $O(8^{m}...
-
STIR: Reed-Solomon Proximity Testing with Fewer Queries
소개 이 글은 https://eprint.iacr.org/2024/390.pdf에 대해서 설명합니다. STIR의 목표는, Reed-Solomon Code와의 Proximity Testing을 최소한의 query로 하는 것입니다. 동일한 문제를 푸는 알고리즘 중 가장 잘 알려진 FRI는, degree $d$ 문제를 $\lambda$-bit security를 갖게 해결하기 위하여 query를 $\mathcal{O}(\lambda \log d)$개 사용합니다. STIR는, 그에 비해 $\mathcal{O}(\log d + \lambda \cdot \log \log d)$만큼의 query를 사용하여, 더 적은 query를 사용하게 됩니다. query의 개수는 STARK proof의 크기와 연결되어 있기 때문에, FRI를 STIR로 대체하여 STARK의 proof size 및 verifier time을 줄일 수...
-
Concurrent Augmented Tree
Intro 이전의 글에서 Concurrent Non-Blocking Binary Search Tree를 알아보았다. 이번에는 단순히 Insert, Delete, Find만 지원하는 트리가 아니라, Range Query를 지원하는 자료구조에 대해서 알아보자. Key Points & Brainstorming 이전의 글에서 알아봤던 lock-free-locks로 만든 leaf tree, 그리고 Ellen Tree는 모두 Insert, Delete, 그리고 Find (혹은 Lookup) 연산만을 지원한다. 아주 중요한 연산들이지만, 실제로 자료구조를 사용할 때는 더 다양한 종류의 연산들이 필요한 경우가 많다. 흔히 Seqential한 환경에서 생각해볼 수 있는 연산은, Range sum 연산이다. key_l과 key_r이 주어졌을 때, 트리...