Combinatorial Nullstellensatz
1. Combinatorial Nullstellensatz Theorem. (Combinatorial Nullstellensatz) 체 $\mathbb{F}$와 다항식 $f \in \mathbb{F}[x_1, x_2, \cdots, x_n]$ 이 있다고 하자. $\deg(f) = d = \sum_{i=1}^n d_i$ 이고, $\prod_{i=1}^n x_i^{d_i} \neq 0$ 라면, $\lvert L_i \rvert > d_i$인 $\mathbb{F}$의 부분집합 $L_1, L_2, \cdots, L_n$에 대해 $a_1 \in L_1, a_2 \in L_2, \cdots, a_n \in L_n$이 존재해 $f(a_1, a_2, \cdots, a_n) \neq 0$ 를 만족시킨다. Proof. $..
랜덤한 교란 순열을 생성하는 card-based 프로토콜 (1)
1. Introduction Symmetric group $S_n$의 원소, 즉, $[n]$ 상의 순열 가운데 fixed point가 없는 것들을 Derangement(교란 순열)이라고 부른다. 이제, 한 가지 예를 들어, $n$ 명의 학생이 있는 학급에서 마니또 행사를 한다고 가정해보자. 학생 $i$의 마니또가 $p_i$라 할 때, $p_i \neq i$ 여야 하며, $i \neq j$ 이면, $p_i \neq p_j$ 여야 할 것이다. 즉, ${p_i}$ 가 derangement 여야 한다. 또한, 학생 $i$는 $p_i$의 값 외에 다른 정보를 알지 않아야 한다. 이렇듯, 현실에는 각자 자신에게 배정된 수 외의 정보를 알 수 없는 상태에서 derangement를 랜덤하게 생성해야 하는 (암호학적인 ..
2-SAT 및 그의 응용
1. 2-SAT 문제란? 2-SAT 문제란 참/거짓의 값을 가지는 불리언 변수 $n$개 $x_1, x_2, \cdots, x_n$ 와 2-CNF가 있을 때, 2-CNF를 참으로 만들기 위해 $x_i$ 들에 적당한 값을 할당하는 문제이다. 2-CNF란 2개의 변수를 $\lor$ (or)한 식(절) 여러 개에 $\land$ 연산을 취해 만들어지는 식을 의미한다. 예를 들어, $(x_1 \lor x_2) \land (\bar x_3 \lor x_4)$ 는 2-CNF이다. 그리고, $x_1 = true$, $x_2 = false$, $x_3 = false$, $x_4 = false$ 는 이 식을 만족 시키는 하나의 방법이다. 반대로, $(x_1 \lor x_1) \land (\bar x_1 \lor \bar x..
레이블과 소수자성
요즘 들어 나의 글쓰기 실력이 지속적으로 줄어가는 것을 느꼈다. 고로, 내가 했던 생각들을 짧게나마 기록하는 습관을 들이려 노력해본다. 우리 사회는 사람들에게 레이블을 붙이는 것을 참 좋아하는 것 같다. 예를 들어, 사회가 나에게 붙여준 레이블은 대학생, 개발자, 20대 등이 있다. 이렇듯, 사회의 각 구성원은 여러 레이블을 단 채로 살아간다. 그런데, 한 사람이 여러 레이블을 달고서 살아간다고 한들, 사회는 모든 레이블에 균등한 가중치를 두고 바라보지 않는다. 두 명의 20대 남성 개발자가 있다고 하더라도, 한 명에게는 20대라는 사실에, 다른 한 명에게는 개발자라는 사실에 더 초점을 두고 바라볼 수도 있는 법이다. 즉, 사회가 개인을 바라볼 때 더 우선적으로 바라보게 되는 레이블이 존재하는 것이다. ..