파신 마누랑시: 컴퓨터가 할 수 없는 것을 증명하기
2011년 7월, 태국의 휴양지 파타야에서 태국 사상 처음으로 제23회 국제정보올림피아드(IOI)가 개최되었고, 아피싯 웻차치와(Abhisit Vejjajiva) 당시 총리가 그의 마지막 공식 일정 중 하나로 대회 개막을 알렸습니다. 참가한 태국 선수단 중 방콕 기독교 대학(Bangkok Christian College) 출신의 한 학생은 524점으로 303명의 참가자 중 14위를 차지하며 2년 연속 금메달을 획득했습니다. 그는 기자들에게 14위라는 성적에 만족하며, 524점은 기대 이상의 점수였고, 이번 올림피아드 개최가 태국 청소년들의 컴퓨터에 대한 관심을 높이는 계기가 되기를 바란다고 말했습니다. 15년이 지난 지금, 파신 마누랑시(Pasin Manurangsi)는 어떤 문제가 해결 불가능한지를 컴퓨터 과학 분야에 알리는 연구원 중 한 명이 되었습니다.
올림피아드 여정
마누랑시의 대회 기록은 개선을 위한 통제된 실험과도 같습니다. 2009년 불가리아 IOI에서 그는 516점으로 301명 중 67위를 기록하며 은메달을 땄습니다. 2010년 캐나다에서는 704점으로 297명 중 12위를 기록하며 금메달을 거머쥐었습니다. 2011년 본국에서 열린 대회에서는 다시 금메달을 획득하며 태국이 사상 처음으로 주최한 대회에서 팀 금메달을 차지하는 데 기여했습니다. 세 번의 출전, 두 개의 금메달과 하나의 은메달, 그리고 첫 번째와 두 번째 도전 사이의 세계 랭킹 55계단 상승은 패배를 판결이 아닌 개선을 위한 사양서(specification document)로 대우한 사람의 궤적을 보여줍니다.
MIT와 충분히 가까워지기 문제
마누랑시는 매사추세츠 공과대학교(MIT)에서 학사와 석사 학위를 받았으며, 다나 모슈코비츠(Dana Moshkovitz)의 지도하에 프로젝션 게임(projection games)을 위한 근사 알고리즘에 관한 석사 연구를 수행했습니다. 이 주제는 그 이후 모든 연구의 방향을 결정지었습니다. 근사(Approximation)는 이 분야의 실용적인 타협안으로, 문제가 합리적인 시간 내에 정확히 해결될 수 없을 때, 최적해의 특정 계수 내에 있음을 보장하는 답을 찾는 것입니다. 흥미로우면서도 마누랑시가 끊임없이 돌아온 질문은, 수학적 벽에 부딪히기 전까지 그 보장 수준을 얼마나 높일 수 있는가 하는 것이었습니다.
버클리: P와 NP 사이의 나라
그는 2019년 5월 캘리포니아 대학교 버클리(University of California, Berkeley)에서 박사 학위를 취득했으며, 루카 트레비산(Luca Trevisan)과 프라사드 라가벤드라(Prasad Raghavendra)가 공동 지도했고 니킬 스리바스타바(Nikhil Srivastava)가 위원회에 참여했습니다. 논문 제목은 근사와 경도: P와 NP를 넘어(Approximation and Hardness: Beyond P and NP)였으며, 제목에서 그 포부가 드러납니다. 고전 복잡도 이론은 문제를 해결 가능한(P) 문제와 악명 높은 어려운(NP-완전) 문제로 분류합니다. 마누랑시의 논문은 의도적으로 그 범주가 다루지 않는 영역을 탐구했습니다. P에도 속하지 않고 NP-난해로 알려지지도 않은 문제들, 예를 들어 k-지배 집합(k-dominating set), k-클리크(k-clique), k-비클리크(k-biclique), 방향성 스타이너 네트워크(directed Steiner network), 격자 문제(lattice problems) 등과, 가장 직관에 어긋나게도 P 내부에서 편안하게 자리 잡고 있으면서도 빠른 근사가 어려운 문제들(최근접 쌍(closest pair), 최대 내적(maximum inner product) 등)을 다뤘습니다. 초록에 따르면 이 연구는 매개변수 복잡도(parameterized complexity) 분야의 두 가지 오랜 미해결 문제를 해결하고 여러 문제에 대한 최선의 근사 불가능성 계수를 제시했습니다. 이는 경계를 넘는 것이 아니라 경계를 그리는 것에 관한 논문입니다.
가장 밀도가 높은 k-서브그래프 벽
그의 이름을 알린 단일 결과는 '가장 밀도가 높은 k-서브그래프(Densest k-Subgraph)' 문제와 관련이 있습니다. 네트워크가 주어졌을 때 연결이 가장 촘촘한 k개의 노드를 찾는 것입니다. 마누랑시는 지수 시간 가설(exponential time hypothesis) 하에서, n의 1/(log log n) 거듭제곱(상수 배)보다 나은 근사 비율을 달성할 수 있는 다항 시간 알고리즘은 없음을 증명했습니다. 그리고 더 강력한 Gap-ETH 가정하에서는 그 장벽이 0으로 수렴하는 모든 함수 f에 대해 n^f(n)으로 좁혀지는데, 이는 거의 다항식 수준의 난도와 같습니다. 결정적으로 이 구성은 분야에서 이른바 '완전 완벽성(perfect completeness)'을 갖추고 있습니다. 이는 k-클리크를 실제로 포함하는 그래프와 모든 k-서브그래프가 희소한 그래프를 구분합니다. 이 논문은 이론 컴퓨터 과학의 주요 학회인 STOC 2017에서 대니 르윈 최우수 학생 논문상(Danny Lewin Best Student Paper Award)을 수상했습니다.
구글, 개인정보 보호 및 공정 분할
2019년 7월부터 마누랑시는 구글 리서치(Google Research)에서 연구 과학자로 근무하고 있으며, 알고리즘 및 이론, 기계 지능, 악용 방지 분야를 담당하며 100편 이상의 논문을 발표했습니다. 무게 중심은 순수 근사 불가능성에서 차분 프라이버시(differential privacy), 학습 이론, 계산 사회 선택(공정 분할, 합의 절반 나누기, 개인 정보 보호 랭킹 집계, 합성 데이터 생성 등)으로 옮겨갔습니다. 최근 연구 결과 중 하나는 단조 효용을 가진 n명의 에이전트에 대해 O(√(n log n)) 수준까지의 합의 절반 나누기가 항상 존재함을 보였으며, 이는 기존의 경계를 개선한 것입니다. 그는 WAOA 2021 최우수 논문상, ALT 2021 최우수 학생 논문상, FORC 2026 최우수 논문상 및 최우수 논문 가작을 수상했으며, IJCAI 2021과 2023에서 탁월한 프로그램 위원회 인정을, NeurIPS 2023에서 최고 검토자 지위를 획득했습니다.
귀국
2022년부터 그는 태국 정보올림피아드 및 수학올림피아드 캠프의 코칭 팀에 합류했으며, 2024년 IOI에서는 태국 대표단 초청 위원으로 활동했습니다. 2023년부터는 CMKL 대학교의 겸임 교수로 재직하며 알고리즘, 데이터 구조, 개인 정보 보호 알고리즘을 가르치고 있습니다. 그를 길러낸 교육 시스템이 이제는 그가 운영을 돕는 시스템이 되었습니다.
파신이 천재라고 불리는 이유
여기서 문제 삼는 인지적 능력은 매우 구체적이며, 단순한 속도가 아닙니다. 올림피아드의 성공은 시간 제한 내에 빠르고 정확한 문제 해결을 보상하지만, 근사 난도 연구는 정반대의 보상을 요구합니다. 즉, 알고리즘 클래스 전체가 파멸임을 증명하기 위해 복잡한 축소(reduction)를 구축하는 인내심입니다. 마누랑시는 이 두 가지를 높은 수준에서 모두 수행했다는 점에서 드문 사례이며, 버클리 박사 학위 논문이 그 증거입니다. 이 논문은 음수 결과(negative results)는 발표하기 어렵고 정확히 구현하기 어렵다는 이유로 대부분의 연구자가 기피하는 영역을 개척했습니다. 축소 과정에서의 사소한 논리적 실수는 모든 것을 무효로 만듭니다.
정직한 반론 또한 상당합니다. 그 자신의 홈페이지, 구글 리서치 프로필, 박사 학위 논문, 혹은 당시의 태국 언론 보도 등 모든 출처에서 그를 '천재'라고 묘사하는 곳은 없습니다. 그가 받은 상들은 시대의 정신을 대표하는 천재가 아닌, 특정 공간에서의 최우수 논문을 인정하는 학회 위원회의 동료상입니다. 이론 컴퓨터 과학은 또한 끊임없이 협업이 이루어지는 분야입니다. 그가 발표한 100여 편의 논문은 공동 저자, 세미나, 그리고 해당 분야의 가장 강력한 복잡도 이론가 두 명이 이끄는 버클리 그룹의 산물입니다. 그의 IOI 기록은 훌륭하지만 67위라는 성적도 포함되어 있습니다. 과장 없이 말할 수 있는 것은 더 좁고 흥미로운 사실입니다. 그는 수학의 가장 기술적으로 까다로운 구석 중 하나에서 일류 전문가이며, 그의 결정적인 연구 결과는 수년간 미해결 상태였던 질문을 종결지었습니다. 이것이 천재와 같은 것은 아니며, 본인 역시 그렇게 주장한 적이 없습니다.
전망
마누랑시의 경력은 이론가로서는 독특한 형태를 띠고 있습니다. 불가능성 증명이 먼저였고, 응용 개인 정보 보호 연구가 그 뒤를 이었습니다. 차분 프라이버시와 공정 분할로의 이동은 벽이 어디에 있는지 확인한 후 이제 그 안에서 무언가를 구축하고 싶어 하는 사람의 모습을 보여줍니다. 태국 올림피아드 코칭은 그가 남길 가장 지속적인 유산이 될지도 모릅니다. IOI를 한 번 개최했던 나라가 이제는 IOI에서 우승하는 인재들을 길러내고 있기 때문입니다.
