이번에 필즈상을 받은 허준이 교수의 업적이 어떻게 실생활이나 산업에 응용되는지 궁금해하시는 분들이 있어서 질문도 종종 받게 되네요. 순수수학 하는 사람들은 원래 흥미로운 수학적 현상의 본질적인 원리를 규명하려는 호기심으로 연구를 하기 때문에 응용 가능성을 생각하고 연구를 하는 것도 아니고 실제 응용이 되더라도 연구자 본인이 자기 연구가 어떻게 응용되는지 모를 수도 있습니다. 그렇지만 수학이라는 것이 활용이 되면 정말 파급이 큽니다. 우리가 이 글을 보기 위하여 인터넷을 접속할때부터 이 글을 읽을 때까지 정말 여러 곳에서 수학이 활용되고 있다고 할 수 있습니다. 아울러 수학은 오랜 시간이 지나 활용되는 사례도 여럿 있구요. 그러다보니 수학자들에게 이런 질문을 하면 100년이 지나면 사용될지도 모른다 같은 식의 모호한 답을 하기 마련인데 기자분들은 이런 답을 들으면 답답하실 거에요. 수학자들은 틀린 답은 안 하도록 직업적 훈련을 받는 사람들이라 아닌 걸 맞다라고 하진 못하거든요.
허준이 교수 필즈상 수상 관련 대한수학회 보도자료에서 “허준이 교수의 연구 업적들은 정보통신, 반도체 설계, 교통, 물류, 기계학습, 통계물리 등 여러 응용 분야의 발달에 기여하고 있다.”라고 표현하긴 했는데 어쩌면 일반 대중을 위해서 약간 양념을 칠 수도 있지 않나 하면서 읽었는데요.
하지만 놀랍게도 허준이 교수의 연구 결과를 사용하여 수학자와 이론전산학자가 협업하여 효율적인 알고리듬을 고안하는데 도움을 준 경우도 있더군요! 필즈상 시상식때 허준이 교수의 업적을 소개하는 강연을 한 Gil Kalai 교수도 이 부분을 살짝 언급을 하셔서 알게 되었습니다.
바로 이 결과는 스탠포드대학 전산과 Nima Anari 교수, 워싱턴대학 전산과의 Shayan Oveis Gharan 교수, 그리고 노스캐롤라이나대학 수학과의 Cynthia Vinzant 교수가 2018년에 발표한 내용입니다.
이 논문에서는 랭크가 $r$인 매트로이드에서 그 베이스(base)의 갯수를 오차 비율 $2^{O(r)}$배 이내로 근사하는 다항식 시간 알고리듬을 처음으로 제시합니다. 이 논문은 이론전산학 분야 최고 학회라고 할 수 있는 FOCS 2018에서 발표되었고, 나중에 매우 좋은 수학 저널 중 하나인 Duke Math Journal에 2021년 출판되었습니다. 이 논문 초록을 보면 허준이 교수와 공저자들의 논문 2개를 언급하면서 거기서 개발한 조합적 호지 이론을 활용하여 알고리듬을 만들 수 있었다고 합니다.
이 분들의 논문에서는 매트로이드를 아무 거나 가져와도 그것의 베이스(base)들의 생성 함수에 로그를 취하면 오목함수가 된다는 것을 증명하고 그걸 이용하여 매트로이드의 베이스가 몇 개인지를 오차비율 $2^{O(r)}$배 이내로 답할 수 있는 다항식 시간 알고리듬을 만들어냅니다.
이 분들은 여러 후속 논문에서도 허준이 교수와 그 공저자들의 연구를 널리 활용하여 갯수를 근사하는 알고리듬, 그리고 같은 비율로 베이스를 랜덤하게 뽑는 방법에 관한 연구를 하였습니다.
매트로이드는 워낙 다양한 상황을 묘사할 수 있는 수학적 대상이라서 이런 범용의 알고리듬이 나오면 이런 종류의 알고리듬을 만들어야 할때 그것이 매트로이드란 것을 먼저 보이기만 하면 활용할 수 있게 되어 매우 좋은 결과라고 할 수 있지요. 예를 들어 주어진 그래프에서 선 k개로 만들어진 회로를 만들지 않는 선의 부분집합은 몇 개일까 세는 알고리듬을 만들어야 한다면 그런 집합은 매트로이드를 이루기 때문에 이 결과를 쓰면 빠른 속도로 근사값을 구할 수 있다는 것을 알게 됩니다.
물론 이렇게 글을 써도 매트로이드가 뭐길래 라고 하실 것이 분명해서 이야기가 더 길어지기 전에 그만 쓰겠습니다. 😉
[1] N. Anari, S. O. Gharan, and C. Vinzant. Log-concave polynomials, I: entropy and a deterministic approximation algorithm for counting bases of matroids. Duke Math. J., 170(16):3459–3504, 2021.
허준이 교수의 필즈상 수상을 진심으로 축하합니다. 참고로, 허준이 교수의 필즈상 수상을 축하하며 수학동아에 간략하게 허준이 교수를 소개하는 글을 써보았습니다.
[엄상일 교수가 설명하는 허준이 교수 업적] 난제인 조합수학을 대수기하학이란 도구로 해결한 아이디어맨
그리고 위의 사진은 2020년에 허준이 교수가 IBS 이산수학그룹에 와서 discrete math seminar에서 발표를 할 때 제가 찍은 사진입니다.