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..
이직
지난 달 말에 이전 회사를 퇴사하고, 조금의 휴식기를 가진 후, 센드버드라는 또 다른 회사로 이직했다. 원래는 이직 생각이 크게 없었지만, 산업기능요원 편입과 관련해 다소 좋지 못한 일이 있었어서, 결국 이직 했고, 지난 주 부터 산업기능요원으로 근무하고 있다. (몰로코가 절대 나쁜 회사는 아니다. 다만, 당분간 산업기능요원을 뽑지 못할 뿐이다.) 비록, 이직의 시작은 불가항력적인 사유였으나, 좋은 기회를 잡게 되어 매우 감사하고 있다. 회사에서 내가 어떤 일을 하게 될 지 차차 알아가면서 일하는 중인데, 너무 재밌고 챌린징해 보이는 태스크들이 많아서 만족스럽다. 그 외에 회사 문화나 급여, 복지 등의 부분도 매우 만족스럽다. (이직의 시작은 불가항력적인 사유였지만, compensation 또한 꽤 많이..
