-
bound entanglement
서론 양자 얽힘 (quantum entanglement)는 크게 두 가지로 분류할 수 있다. 대부분의 entanglement는 free enntanglement이며, 일부가 bound entanglement이다. 특히, bound entanglement는 아직 한국에 잘 소개되지 않았으며, 한국어 명칭도 정착되지 않은 개념이다. 그리고 bound entanglement와 깊게 관련된 LOCC(Local Operations and Classical Communication)도 일반 사람들을 대상으로 많이 소개되지 않아 이에 대해 이번 글에서 간단히 소개해 보고자 한다. 양자 상태부터 설명을 시작해서 bound entanglement까지 설명하기에는 너무 긴 분량이 될 것이므로 초반부는 간략하게 설명하였으니 이 글을 읽고 흥미가 생긴...
-
Advanced Graph Algorithms and Optimization: Convexity and Second Derivatives, Gradient Descent and Acceleration
Advanced Graph Algorithms and Optimization: Convexity and Second Derivatives, Gradient Descent and Acceleration 2021년 발표된 Minimum Cost Flow가 Almost-Linear Time에 풀린다는 결과는 현대적인 Convex Optimization 기법들이 전통적인 알고리즘 문제를 해결하는 아주 강력한 도구를 제공함을 보여주는 상징적인 순간이라고 할 수 있다. 요즘은 기계 학습의 인기가 워낙 엄청나기 때문에 Convex Optimization은 대개 기계 학습의 관점에서 다뤄지지만, Convex Optimization은 현대 전산학 전반에 있어서 중요도가 아주 높으며, 그래프 알고리즘적인 관점에서 Convex Optimization을 다뤘을 때 얻어갈 수 있는 것이 아주...
-
Size of struct
서론 이 글은 구조체를 사용할 때 구조체가 차지하는 메모리가 어떻게 계산되는지를 다룬다. Problem Solving을 할 때 조금이나마 도움이 되기를 바란다. 구조체의 메모리 계산 예시 PS가 아닌 개발을 목적으로 한 프로그래밍을 할 때에는 보통 가독성을 중요하게 생각한다. 다음과 같은 c++ 코드를 생각해 보자. const int SIZE = 1000000; struct User{ char sex; short age; long long id; } db[SIZE]; 유저의 성별, 나이, 고유한 id를 설정해야 하는 상황이다. 우선 위와 같이 설정한 이유를 간략히 설명하겠다. 성별은 ‘M’...
-
Linear-Time Encodable Linear Code
Error-correcting code $[n, k, d]$ code: 길이 $k$인 message $m$을 길이 $n$인 codeword $Enc(m)$으로 인코딩하는 $Enc$에 대해, 서로 다른 두 message의 codeword의 hamming distance (서로 다른 entry의 개수)가 항상 $d$ 이상일 때 이를 $[n, k,d]$ code라 합니다. 이 때 가장 가까운 두 codeword가 서로 다른 비율을 나타내는 $\Delta = \frac{d}{n}$을 code의 relative distance라고 부릅니다. Example: Repitition code 예를 들어, “0101”을 “000111000111”로 encoding하는, 원래의 비트를 세 번씩 반복하는 repitition code의 경우 이는 $[3k, k, 3]$ 코드이고,...
-
sweepline MO
개요 다음 문제를 생각해 봅시다. Static Range Inversions Query 길이가 $N$인 수열 $A = (A_1, A_2, \dots, A_{N})$가 주어지면, 다음 $Q$개의 쿼리를 수행해야 합니다. $(1 \leq N \leq 10^5, 1 \leq Q \leq 10^5, 0 \leq A_i \leq 10^9)$ $1 \leq l \leq r \leq N$을 만족하는 $l,r$이 주어지면, $l \leq i < j \leq r, A_i > A_j$ 를 만족하는 $(i,j)$쌍(=inversion)의 개수를 출력한다. 이 글에서는 다음의 내용들을 다룰 것입니다. Static Range Inversions Query 문제를...