본문 바로가기

Unique Games Conjecture에 대한 노트 본인은 최근 들어 Theoretical Computer Science 분야 중에서도 Computational Hardness에 관련한 결과들을 다루는 스터디에 참여하고 있고, Unique Games Conjecture와 관련하여 발표할 일이 있었다. 나름 의미가 있는 주제임에도 불구하고, 이와 관련한 국문 자료는 (본인이 검색해본 한에서는) 전혀 찾아볼 수 없었어서 이 글을 작성하게 되었다. 이 글은 Unique Games Conjecture가 무엇이고, 이를 통해 어떤 결과들을 얻을 수 있는지에 대해 전달하는 것을 목표로 한다. Unique Games Conjecture에서 어떤 형태로 reduction을 구성할 수 있는지 그 느낌 또한 전달하는 것 또한 목표로 하되, reduction에 대한 form..
The Short-Side Advantage in Random Matching Markets 이 글은 L. Cai와 C. Thomas의 논문 The Short-Side Advantage in Random Matching Markets 의 결과를 간략하게 정리한 것이다. 1. Introduction Stable Matching Problem은 남-여 간의 짝 매칭, 의사와 병원간의 매칭, 학생과 지도교수 간의 매칭 등 여러 상황에서 응용될 수 있는 문제로 다음과 같은 상황을 다룬다. $n$ 명의 의사 $\mathcal{D} = {d_1, d_2, \cdots, d_n}$ 와 $m$ 개의 병원 $\mathcal{H} = {h_1, h_2, \cdots, h_m}$ 이 있다. 각각의 의사는 병원에 대한 선호하는 순서($\prec_d$)가 존재하고, 각각의 병원은 의사에 대한 선호하는 순서($\prec..
Computational Complexity Classes 최근 https://github.com/koosaga/project-hardness 의 스터디에 참여하고 있다. 해당 스터디에서 공부한 내용을 아주 간략히 (주로 informal 하다.) 간혹 정리해볼 예정. P와 NP P와 FP $\mathbb{P}$는 다항 시간(입력 $x$의 크기에 대해 다항식 scale로 bound 됨을 의미)에 풀리는 문제들의 class이다. 유의 사항: 정수 $n$은 $\log_2 n$ 개의 비트로 표현할 수 있으므로 $n$을 입력으로 줄 때 입력의 크기는 $\log_2 n$ 이다. (흔히들 Subset Sum 등을 $\mathbb{P}$라 생각하면서 하는 오해...) $\mathbb{FP}$는 다항 시간에 계산 가능한 함수들의 class이다. 어떤 계산 모델을 가정할 것인가?..