-
Nearly optimal communication complexity of Bipartite Maximum Matching
Introduction Bipartite Maximum Matching (BMM)은 Bipartite graph $(V = X \sqcup Y, E \subseteq X \times Y)$에 대해 크기 $F$ 이상인 Matching이 존재하는지를 묻는 decision problem, 혹은 Maximum Matching의 크기를 계산하는 문제를 이야기합니다. 굉장히 오래 전부터 연구되어 온 문제이고, 정점이 $n$개, 간선이 $m$개인 BMM은 $m^{1 + o(1)}$ 시간 안에 해결할 수 있다는 것이 알려졌습니다. 원본 문제의 시간 복잡도가 subpolynomial 수준에서 사실상 optimum을 달성했기 때문에, 비전형적인 세팅에서 BMM을 해결하는 기법들이 등장하기 시작했습니다. 그 예시가 multi-party communication으로,...
-
SAT problem의 변형과 Schaefer’s Dichotomy Theorem
Boolean Formula, SAT $(x \lor \neg y) \land (\neg x \lor z)$와 같은 식을 Boolean formula라 한다. Boolean formula의 변수(variable)는 True/False (또는 1/0이라고도 한다)의 두가지 값만을 가질 수 있다. 위 boolean formula의 variable은 $x, y, z$이다. 각 연산자에 대해 알아보면 $\lor$ 와 $\land$는 각각 logical OR(disjunction)/ logical AND (conjunction)를 나타내고, $\neg$(negation)는 NOT을 나타내는 연산자로 피연산자가 True였다면 False로, False였다면 True로 바꿔주는 역할을 한다. 식에서 각각의 항 $x, \neg y, \neg x, z$는 literal이라 한다. $x, y$와...
-
Mining Multi-Label Samples from Single Positive Labels (NeurIPS'22) 눈문 소개
올해 11월 말에 열릴 머신러닝 학회인 NeurIPS 2022에 제가 제출했던 논문 “Mining Multi-Label Samples from Single Positive Labels”이 어셉되어서 리뷰하고자 합니다. 소개 자연에 존재하는 많은 이미지 데이터셋은 여러 가지의 속성을 가지고 있습니다. 예를 들어, 얼굴 이미지 데이터셋은 검은 머리, 웃는 표정, 남성과 같은 속성을 가질 수 있습니다. 일반적으로 이런 다중 속성을 모두 조작하여 이미지를 생성하기 위해서는 모든 속성의 존재 여부가 레이블링된(다중 레이블) 데이터셋을 사용해야 하는데 이는 대채로 매우 비쌉니다. “Mining Multi-Label Samples from Single Positive...
-
Sum-Check Protocol and Applications
Introduction 최근 개인적인 사정으로 공부를 제대로 못하다가 정신을 차리고 Thaler의 책을 읽고 있습니다. 그 내용 중 일부분인 Sum-Check Protocol과 이를 활용한 application들에 대해서 짚고 넘어가고자 합니다. 이번 글에서는 다루지 않으나, 최근 등장한 HyperPLONK도 역시 Sum-Check Protocol에 기반하고 있으니, 이를 공부하기 위해서라도 Sum-Check에 대해서 제대로 공부해놓는 것이 좋아보입니다. The Sum-Check Protocol $v$-variate polynomial $g$가 유한체 $\mathbb{F}$ 위에서 정의되었다고 합시다. 목표는 \[H = \sum_{(b_1, \cdots, b_v) \in \{0,1\}^v} g(b_1, \cdots , b_v)\] 가 성립함을 증명하는 것인데, 특히...
-
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$)가 존재하고, 각각의...