-
Introduction to Hardness Proofs and 3SUM Conjecture
Introduction to Hardness Proofs and 3SUM Conjecture Introduction 어떤 문제를 푸는 가능한 한 빠른 알고리즘을 찾아내는 것은 이론전산학 분야의 주된 관심사 중 하나입니다. 어떠한 문제든 우리가 원하는 만큼 빠른 알고리즘이 존재한다면 좋겠지만, 아쉽게도 이는 사실이 아닙니다. 예를 들어, $N$개의 정수를 크기 순으로 정렬하는 데에는 적어도 $\mathcal{O}(N\log N)$ 시간이 필요하다는 사실이 알려져 있습니다. 그렇다면 질문을 바꿔서, 어떤 문제를 해결하는 알고리즘의 시간 복잡도의 하한을 알 수는 있을까요? 이를 다른 말로 해당 문제의 hardness을 알아낸다고 말하는데, 이 역시도...
-
Noise or Signal: The Role of Image Backgrounds in Object Recognition (ICLR 2021)
Noise or Signal: The Role of Image Backgrounds in Object Recognition (ICLR 2021) Deep learning 분야에서, 모델의 generalization을 올리는 것은 굉장히 중요한 일입니다. Generalization이 떨어지는 모델의 경우, 주어진 학습 데이터에만 과적합하여 이외의 다른 데이터들에 대해서는 성능이 낮아지는 문제가 발생할 수 있으며, 주어진 train data들만이 가지는 특성들에 대해 큰 bias를 가지게 될 수 있습니다. 이러한 문제를 해결하기 위한 방법론들은 굉장히 다양한 접근들로 제시되어왔습니다. Train data를 건드리는 data augmentation들도 존재하고, train 과정에서 과적합되는 것을 방지하기 위한 sharpness-aware,...
-
Quantum Graph
서론 그래프는 수학과 컴퓨터 과학에서 굉장히 중요하게 다루는 내용이다. 알고리즘 문제풀이만 하더라도 그래프와 관련된 알고리즘이 수 없이 많다. 이러한 그래프 이론은 최단 경로, 효율적인 네트워크 구조, 데이터 분석 등에 폭넓게 응용된다. 다들 기존에 자주 보던 그래프 (고전 그래프)에 대해서는 어느정도 익숙할 것이라 생각한다. 양자 컴퓨팅 분야가 발전하면서 고전 컴퓨팅에 존재하던 다양한 개념들을 양자 컴퓨팅으로 옮겨오는 연구들도 많이 진행되었다. 이는 한 학문이 발전하면서 흔히 보이는 현상이다. 본 글에서는 Graph의 개념을 옮겨온 Quantum Graph에 대해 소개해 보고자...
-
Near-Linear time Laplacian Equation Solver
Introduction Graph $G$의 Laplacian은 많은 graph problem에 관여하는 중요한 object입니다. 과거 Matrix-Tree theorem에 대해 다룬 글에서 볼 수 있듯 Laplacian의 determinant는 $G$의 스패닝 트리 개수와도 관계가 있고, 오늘 다룰 Laplacian system을 푸는 것도 굉장히 중요한 문제입니다. 또한 Laplacian의 고유값(eigenvalue)들 또한 graph의 well-connectedness와 관련이 있는 유의미한 지표로 사용할 수 있습니다. 정점이 $n$개, 간선이 $m$개인 무방향 그래프 $G$의 Laplacian $L _ {G}$는 $D - A$로 정의합니다. 여기서 $D$는 $D _ {i, i} = \deg(i)$를 만족하는 대각행렬이고, $A$는...
-
ZKP and Block Hash Oracles
이 내용은 ZK-School에서 멘토링한 자료에 기반합니다. ZKP의 목표 영지식 증명, Zero Knowledge Proof는 기본적으로 일련의 계산이 제대로 되었음을 간단하게 증명하는 것을 목표로 하고 있습니다. Zero Knowledge라는 부분도 중요하지만, 가장 핵심은 보통 Proof에 있습니다. 일단 Proof가 되어야지 Zero Knowledge를 이야기를 하겠죠? 그래서 대강 압축을 하자면, Alice가 $f(x)$라는 값을 알고 싶은데 이를 직접 계산하기에는 컴퓨팅 파워가 부족하다면, 그 컴퓨팅 파워가 있는 Bob이 $f(x)$를 직접 계산해서 $y = f(x)$라는 사실을 알아내고, Alice에게 단순히 $y$의 값을 넘기는 것이 아니라,...