2021 아벨상 수상자 아비 위그더슨

수학과 계산을 연결하는 아비 위그더슨의 업적

노르웨이 학술원은 2021년의 아벨상 수상자로 컴퓨터 과학과 이산 수학 연구에 이바지한 수학자 로바스 라슬로^{Lovász László}와 컴퓨터 과학자 아비 위그더슨^{Avi Wigderson}을 선정하였습니다. 두 분의 아벨상 수상을 진심으로 축하하며, 이 글에서는 위그더슨 교수가 수학과 컴퓨터 과학의 교차점에서 걸어온 삶을 짧게 조명해보는 시간을 가지고자 합니다.

컴퓨팅 이론

최초의 범용 디지털 컴퓨터는 1941년에 등장했습니다. 그러나 이보다 5년 전 앨런 튜링은 오늘날 튜링 기계^{Turing machine}라고 불리는 것을 고안했습니다. 튜링 기계는 디지털 컴퓨팅 장치를 위한 수학적 프레임 워크로서 새로운 장치의 개발을 이끌어 왔으며, 컴퓨터가 가질 수 있는 궁극적인 능력과 한계를 모두 시사하고 있습니다. 예를 들어 어떤 알고리즘도 정지 문제^{halting problem}를 해결할 수 없다는 증명의 논리는, 컴퓨터 과학을 전공한 학부생이라면 누구나 이해할 수 있을 만큼 간단한 동시에 오늘날까지도 컴퓨터 과학 분야의 명확한 논리적 사고의 정점으로 남아있습니다.

컴퓨터가 개발된 이후 많은 시간이 지나 디지털 기술이 일반화되고 사용자가 자신의 프로그램을 작성하기 시작하면서, 컴퓨터 과학의 초점은 점차 ‘효율성’에 주목하기 시작했습니다. 예를 들어 버블 정렬^BubbleSort은 n개의 요소를 정렬하기 위해 2차 숫자 O (n²)의 비교를 발생시키는 반면 합병 정렬^MergeSort은 O (n log n)번의 비교만으로도 충분합니다. 이와 같이 알고리즘별로 계산에 필요한 시간이 달라지기 때문에 알고리즘의 최적성 문제가 발생합니다. 이 문제를 해결하기 위해 튜링에 의해 시작된 질적 계산 가능성 이론을 정량적으로 개선한 계산 복잡성 이론이 고안되었습니다. 예를 들어 스티븐 쿡^{Stephen A. Cook}의 “NP-complete”에 기초한 1971년 논문은 증명 이론^{Proof Theory}에서 영감을 받았는데, 알프레드 타르스키^{Alfred Tarski}가 이전에 고안한 다항식 시간 개선법을 활용하였습니다.

위그더슨의 첫 번째 논문

그래프 채색 문제^{Graph Coloring}는 NP-complete임이 잘 알려져 있었는데, 위그더슨은 1982년 그의 첫 번째 논문 “A new approximate graph coloring algorithm“에서 이 문제에 대한 새로운 근사 알고리즘을 고안하고 분석했습니다.

그래프 G = (V, E)의 채색이란 모서리의 두 끝 점이 서로 다른 색상을 갖도록 정점에 색상을 할당하는 것을 뜻합니다. 색수 χ (G) ≤ |V|는 그래프 G를 채색하기에 충분한 최소 색상수입니다. 주어진 그래프 G에 대한 채색을 계산하는 알고리즘 A를 고려한다고 생각해봅시다. |A (G)|는 알고리즘에서 사용된 색상의 수를 나타내고 근사 비율을 Â (G) = |A (G)| / χ (G)로 줄여서 표시합니다.

χ (G) = 3인 경우와 χ (G) ≥4인 경우를 구별하는 것은 NP- 완전이므로 P = NP가 아니면 다항식 시간 알고리즘 A는 Â <4/3를 달성할 수 없습니다. 이전에 가장 좋은 알고리즘은 Â = O (n / log n)를 가졌습니다. 여기서 n = |V|은 그래프가 가진 꼭짓점의 수를 나타냅니다. 특히, 색수 3의 그래프가 주어지면 이 알고리즘은 O (n / log n) 색상으로 채색을 할 수 있습니다.

놀랍도록 간결한 위그더슨의 첫 번째 다항식 시간 알고리즘은 3색이 가능한 그래프에서 n^⅓ 색상을 찾을 수 있는 방법을 보장합니다. 이를 기반으로 그는 두 번째 알고리즘 A를 추가로 고안하였는데요, 주어진 그래프 G에 대해 다항식 시간 내에 χ(G)·n^{1-1/(χ(G)-1)}-채색을 찾습니다. 다시 말해서 Â ≤ n^1−1/(χ-1)를 달성하는 것이죠. 따라서 이전 알고리즘의 제수 log n을 n^1/(χ-1)-거듭 제곱으로 개선하여 특히 작은 색수를 가지는 경우에 특히 효과적입니다.

위의 두 가지 개선으로 말미암아 전 세계의 컴퓨터 과학자들이 점점 더 효율적인 알고리즘을 고안하고 분석하는 경쟁의 시대가 열렸고, 괄목할 만한 성취를 이끌어냈습니다. 오늘날 가장 잘 알려진 다항식 시간 알고리즘은 O(n^0.2038)-개의 색깔을 이용해 3색 그래프를 채색할 수 있고[Kawarabayashi & Thorup’12], 임의의 주어진 그래프에 대해서는 O(n^1-3/(χ+1))개의 색깔을 이용한 채색이 가능하다는 것이 알려졌습니다.[Karger & Motwani & Sudan’98]

위그더슨은 1982년 첫 논문을 발표한 이후 40년 동안 수학과 계산을 중심으로 연구를 진행해오고 있습니다.

계산 복잡성 이론

계산 복잡성 이론이란 계산 문제의 해법에 “내재”되어 있는 (즉, 그 과정에서 필요하고 충분한) 알고리즘 비용을 연구하는 분야입니다.

n개의 주어진 항목을 오름차순으로 정렬하는 문제를 고려해 봅시다. 버블 정렬^BubbleSort은 이 문제를 해결하는데 O (n²)만큼 비교 및 ​​복사 작업을 발생시키는 알고리즘입니다. 힙 정렬^HeapSort은 동일한 문제를 해결하는 또 다른 알고리즘으로, 이보다 적은 O (n log n)만큼의 비용만을 소요합니다. 그리고 이는 비교 기반 정렬 알고리즘에서 반드시 필요한 비용으로 알려져 있습니다. 따라서 이는 최적의 해로 문제에 내재된 셈이 됩니다. 더 나은 효율성을 가진 솔루션을 찾는 데 더 이상의 시간과 노력을 들이지 않을 수 있다는 것입니다.

계산 복잡성 이론은 정렬을 훨씬 뛰어넘는 고급 문제에 대한 질문을 중심으로 진행됩니다. 그것은 앞서 언급한 그래프 채색과 같은 주제를 포함하는 이산 수학과 함께 발전했습니다. 실제로 위그더슨의 최신 저서 『수학과 계산 : 기술과 과학을 혁신하는 이론^{Mathematics and Computation: A Theory Revolutionizing Technology and Science}』 (Princeton University Press, 2019)은 수학과 계산 간의 깊은 연결관계에 대해 자세히 다루고 있습니다.

위그더슨이 아벨상을 수상한 배경으로 언급되는 계산 복잡성 이론에 대한 그의 기여를 간단히 살펴보기 위해, 몇몇 계산적 복잡도의 개념들에 대해서 이야기해보려고 합니다. 예를 들어 P vs NP Millennium Prize Problem에서 P는 입력 길이를 변수로 할 때 다항식 시간 내에 풀 수 있는 모든 결정 문제들을 모아놓은 공간입니다. 알고리즘의 러닝타임은 계산 복잡성 이론에서 일반적으로 고려되는 알고리즘 비용의 여러 척도 중 하나입니다. PSPACE는 다항식 메모리 비트 수를 사용하여 결정할 수 있는 모든 문제를 포함합니다. Borodin’77의 결과에 따르면, 이는 다항식 병렬 러닝 타임에서 결정할 수 있는 문제들과 동치입니다. 분산 컴퓨팅에서 일반적으로 쓰이는 알고리즘 비용의 다른 척도에는 프로세서 수 또는 통신 볼륨이 포함됩니다. LOGSPACE에는 로그 함수적 메모리 양을 사용하여 해결할 수 있는 모든 문제가 포함됩니다.

NP는 ‘지수 검색 알고리즘’으로 해결할 수 있는 문제의 부류로 간주될 수 있습니다. NP-완전이라는 것은 본질적으로 힙 병렬^HeapSort이 정렬에 최적인 것처럼, 이러한 알고리즘이 최적이기 때문에 더 이상 개선할 수 없다는 것입니다. 이는 보통 해당 문제의 효율적인 해결 가능성에 대한 나쁜 소식으로 간주됩니다. 흥미롭게도 이러한 한계에는 긍정적인 측면도 있는데, 해독이 어려울수록 좋은 암호학과 같은 분야가 바로 그런 경우입니다. 위그더슨은 암호학에도 상당한 기여를 했습니다.

무작위 알고리즘은 P에 속하지 않는 많은 계산 문제를 효율적으로 해결합니다. 따라서 BPP^{Bounded-error Probabilistic Polynomial time}와 같은 무작위 복잡성 클래스에 대한 연구가 많은 관심을 받았습니다. 한편으로 디지털 컴퓨터는 지난 수십 년간 고급 전기 공학을 통해 본질적으로 가장 안정적이고 강력한 결정론적 프로세스 중 하나가 되었지만, 진정한 랜덤 비트를 생성하는 것은 여전히 ​​어렵고 느립니다. 따라서 실무자들은 주로 소수의 임의 비트만 시드로 사용하여 결정론적 유사 난수를 생성합니다. 이로 인해 임의의 비트가 계산 리소스로 간주되고 그 수는 알고리즘 비용의 새로운 척도로 간주됩니다. Derandomization은 위그더슨이 연구를 진행해온 분야 중 하나입니다.

위그더슨의 업적

앞서 언급했듯이 위그더슨의 첫 번째 논문은 P = NP가 아니라면 다항식 시간 내에 정확히 풀 수 없는 그래프 채색 문제에 대한, 새로운 다항식 시간 근사 알고리즘을 고안하고 분석한 것입니다. 이후 위그더슨은 계산 복잡성 이론에 크고 중요한 공헌들을 하며 여러 하위 분야를 크게 발전시켰습니다. 분산/병렬 컴퓨팅, 암호학 및 De/randomization의 세 가지 영역을 예로 들어 설명해보겠습니다.

• 분산/병렬 컴퓨팅 : 위그더슨은 두 번째 논문은 1982년 공동 저자인 대니 돌레브^{Danny Dolev}와 함께 집필한 “분산 시스템에서 다자간 프로토콜의 보안”입니다. 분산/병렬 컴퓨팅에 대한 그의 가장 최근 작업은 2020년으로, 병렬 컴퓨팅의 중요한 모델인 Circuit Complexity에 관련된 것입니다. (“On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions”, 2017 크누스 상^{Knuth Prize} 수상자인 오데드 골드라이히^{Oded Goldreich}와 공동 저술)

• 암호화에서 단방향 인코딩 단사 함수는 계산하기 쉽지만 (예: 다항식 시간) 역변환/디코딩이 어렵습니다. 한 가지 유명한 예는 일부 개별 그룹에서 전원을 공급하는 문제입니다. 위그더슨은 세 번째 논문에서 역변환이 얼마나 어려운지 탐구합니다.(SToC’1983, “How Discreet is the Discrete Log”) 암호학에 관한 그의 최신 논문은 2019년 작으로 오데드 골드라이히^{Oded Goldreich}, 실비오 미칼리^{Silvio Micali}와 공동으로 저술한 “Proofs that yield nothing but their validity and a methodology of cryptographic protocol design”입니다.

• De/randomization과 관련한 위그더슨의 첫 번째 논문과 최신 출판물을 참고할 수 있습니다.

위그더슨은 컴퓨터 과학 분야에서 큰 발전을 이끌어냈습니다. 예를 들어, 오메르 라인골드^{Omer Reingold}, 살릴 바단^{Salil Vadhan}과 함께 Zig-Zag Product를 발명했습니다. 이는 일반 무방향 그래프에서 놀랍도록 간단하면서도 강력한 작업으로, 위그더슨은 이 업적을 바탕으로 2009년 괴델상을 수상했습니다. Zig-Zag product는 constant-degree expander와 extractor graph의 명시적 구성을 가능하게 했으며, 라인골드^Reingold(2005)가 발표한 의무방향 그래프 연결을 위한 LOGSPACE 알고리즘의 설계 및 분석의 기초가 되었습니다.

전기

아비 위그더슨^{Avi Wigderson, אבי ויגדרזון}은 1956년 9월 9일 이스라엘 하이파의 홀로 코스트 생존자들 사이에서 태어났습니다. 그는 리처드 립턴^{Richard Lipton}의 지도 하에 1983년 프린스턴 대학에서 컴퓨터 과학으로 박사학위를 받았습니다.

이후 위그더슨은 여러 자리를 거쳐 히브리 대학교의 교수로 오랫동안 재직했고(1986-2003), 1999년부터는 프린스턴에 있는 고등과학원 교수로 재직 중입니다. 위그더슨이 수상한 주요 상으로는 1994년 네반린나상, 2009년 괴델상(Omer Reingold 및 Salil Vadhan과 함께 공동수상)과 2021년 아벨상(László Lovász와 공동수상)이 있습니다.

DBLP(컴퓨터 과학 분야의 참고문헌 데이터베이스)에 따르면 위그더슨은170명 이상의 공동 저자와 함께 370편이 넘는 논문을 저술했습니다. 그는 100명이 넘는 박사후 연구원을 멘토링 했으며, 그중 다수는 활발히 활동 중인 유명한 학자들입니다. (가령 스콧 아론슨^{Scott Aaronson}, 이리트 디누르^{Irit Dinur}, 수바시 캇^{Subhash Khot}, 마리오 세게디^{Mario Szegedy} 등이 있습니다.)

요약

40년 동안 아비 위그더슨은 계산 복잡성 이론과 계산 수학 분야에서 탁월한 지적 추진력을 발휘해 왔습니다. 독자 여러분께 그의 저서인 『수학과 계산 : 기술과 과학을 혁신하는 이론^{Mathematics and Computation: A Theory Revolutionizing Technology and Science}』을 읽어 보도록 권하고 싶고, 적어도 위키피디아에서 Zig-Zag Product의 정의와 속성만 찾아보아도 매우 흥미로울 것이라고 말씀드릴 수 있습니다. 아비 위그더슨에 대한 자세한 정보는 위그더슨의 IAS 홈페이지에서 찾을 수 있으며, 아벨상 전기에도 여러 흥미로운 내용들이 소개되어 있습니다.

아벨상 시상식과 강연은 5월 25일과 26일 한국시간으로 오후 10시에 온라인으로 열렸습니다.

Avi Wigderson’s work linking between Mathematics and Computation

On the occasion of Avi Widgerson receiving the 2021 Abel Prize (shared with László Lovász), we review his scientific life on the intersection and connecting between Mathematics and Computer Science.

Theory of Computing

The first universal digital computer became operational in 1941; yet already five years before, Alan Turing had devised what we nowadays call the Turing machine: a mathematical framework for digital computing devices that has continued to guide their development and until today serves to exhibit both their ultimate abilities and limitations. For example the proof (by contradiction) that no algorithm will ever be able to solve the Halting Problem stands out to this very day as a pinnacle of clear logical thinking accessible to any undergraduate student in Computer Science.

When digital technology later became common and users started writing their own programs, focus began to shift towards efficiency. For instance BubbleSort incurs a quadratic number O(n²) of comparisons to sort n elements, whereas MergeSort suffices with O(n log n): arising the question of algorithmic optimality. For this purpose, Computational Complexity Theory was devised (see below): again a heavily mathematical framework, quantitative refinement of the previous qualitative Computability Theory initiated by Turing. For example Stephen A. Cook’s seminal 1971 publication underlying “NP-completeness” is clearly inspired by Proof Theory and employs a polynomial-time refinement of computable reduction formalized earlier by Alfred Tarski.

Avi’s First Publication

Graph Coloring was well-known NP-complete, when Dr. Wigderson wrote his first paper “A new approximate graph coloring algorithm”(1982), he devises and analyzes new approximation algorithms for this problem.

Recall that a coloring of a graph G=(V,E) assigns colors to its vertices such that the two endpoints of any edge have different colors; and the chromatic number χ(G)≤|V|  is the least numbers of colors sufficient for coloring G. Consider some algorithm A calculating a coloring to any given graph G, let |A(G)| denote the number of colors used, and abbreviate with Â(G)=|A(G)|/χ(G) its approximation ratio.

Since distinguishing χ(G)=3 from χ(G)≥4 is NP-complete, no polynomial-time algorithm A will ever achieve Â<4/3, unless P=NP. Conversely, the best previous algorithms had Â=O(n/log n), where n=|V| denotes the number of vertices. In particular, given a graph with chromatic number 3, this algorithm would by guaranteed to find a coloring with O(n/log n) colors.

For comparison, Avi’s first (and surprisingly concise) polynomial time algorithm would be designed and guaranteed to find, given any 3-colorable graph, an n^⅓-coloring. Building on this, a second and equally elegant algorithm A manages to find, to any given graph G and within polynomial time, a χ(G)·n^{1-1/(χ(G)-1)}-coloring, i.e., with  ≤ n^1−1/(χ-1). This thus improves the previous algorithm’s divisor log n to the fractional power n^1/(χ-1), which is particularly effective for small chromatic numbers.

These two improvements set off a veritable race, inspiring computer scientists throughout the world to devise and analyze a series of increasingly involved algorithms―with incremental success: Today the best known polynomial-time algorithms use O(n^0.2038) colors to color a given 3-colorable graph[Kawarabayashi&Thorup’12]; and O(n^1-3/(χ+1)) colors for an arbitrary given graph.[Karger&Motwani&Sudan’98]

Throughout the next 40 years, Avi’s many research contributions have continued to revolve around Mathematics and Computation.

Computational Complexity Theory

studies the algorithmic costs that are intrinsic (namely necessary and sufficient) to the solution of computational problems.

Consider for example the problem of sorting N given items in increasing order. BubbleSort is an algorithm solving this problem, incurring O(N²) comparison and copy operations; HeapSort is another algorithm solving the same problem, sufficing with asymptotically less cost O(N·log N). And the latter is known necessary among comparison-based sorting algorithms, hence optimal and intrinsic to the problem: We can stop wasting efforts on finding better solutions!

Computational Complexity Theory revolves around such questions for advanced problems far beyond sorting. It proceeds in seminal synthesis with Discrete Mathematics, involving topics such as the aforementioned Graph Coloring. Indeed, Avi’s latest book is pointedly titled “Mathematics and Computation: A Theory Revolutionizing Technology and Science” (Princeton University Press, October 2019, ISBN 9780691189130) delves over 300 pages on the connection between Mathematics and Computation.

Let us briefly recall some major complexity classes relevant to the selected contributions of Dr. Wigderson mentioned below. P for instance, from the P/NP Millennium Prize Problem, consists of all decision problems solvable in time polynomial in the input length. Runtime is but one of many measures of algorithmic cost commonly considered in Computational Complexity Theory. PSPACE contains all problems decidable using a polynomial number of memory bits; equivalently (Borodin’77): decidable in polynomial parallel runtime. Other measures of algorithmic cost common in distributed computing include the number of processors or communication volume. LOGSPACE contains all problems solvable using a logarithmic amount of memory (not counting the input).

NP can be considered as a class of problems solvable by ‘exponential search algorithms’. Being NP-complete essentially means that such algorithms are optimal, much like HeapSort is optimal for sorting, and cannot be improved―which is easily regarded as bad news against efficient solvability of said problem. Interestingly, such “hardness” can also be turned positively, namely in cryptography where one wants decoding to be hard. Avi has made significant contributions to cryptography.

Randomized Algorithms efficiently solve many computational problems not known to belong to P. Thus arose the study of randomized complexity classes like BPP. On the other hand, after decades of advanced electrical engineering, digital computers are among the most reliable and robust(=deterministic) processes in nature—while creating truly random bits remains both difficult and slow. Hence practitioners commonly use only few random bits as seed to feed a deterministic pseudo-random number generator. This has led to random bits being considered as computational resource, and their number as a new measure of algorithmic cost. Derandomization is an area which Avi has been working on as well.

Avi Wigderson’s Work

As mentioned above, Avi’s first publication had devised and analyzed a new polynomial-time approximation algorithm for the Graph Coloring problem, which cannot be solved exactly in polynomial time unless P=NP. Since then, he has made many more important contributions to Computational Complexity Theory, and has thereby significantly advanced the development of several subfields. We expand on three example areas: distributed/parallel computing, cryptography and de/randomization.

• Distributed/parallel computing: Avi’s second paper, also from 1982, is “On the Security of Multi-Party Protocols in Distributed Systems”  with co-author Danny Dolev. His most recent work on distributed/parallel computing is from 2020 and concerned with Circuit Complexity, an important model of parallel computing: “On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions”, together with Oded Goldreich (Knuth prize 2017).

• In cryptography, an injective one-way encoding function is easy to compute (for example in polynomial time), but hard to invert/decode. One popular example is powering in some discrete group; and Avi in his third paper explores how hard this is to invert: SToC’1983, “How Discreet is the Discrete Log”. His most recent publication on cryptography from 2019 explores, jointly with Oded Goldreich (same) and Silvio Micali, “Proofs that yield nothing but their validity and a methodology of cryptographic protocol design”.

• Regarding de/randomization, we only mention Avi’s first publication  and his most recent.

Avi’s technical contributions have enabled major breakthroughs in the field. For example, together with Omer Reingold and Salil Vadhan, he invented the Zig-Zag Product: a surprisingly simple yet powerful operation on regular undirected graphs that was awarded the 2009 Gödel Prize due to its many applications. The Zig-Zag Product has for instance enabled the explicit construction of constant degree expander and extractor graphs, and it underlies the design and analysis of the famous LOGSPACE algorithm for undirected graph connectivity by Reingold (2005).

Biography

Avi Wigderson^{אבי ויגדרזון} was born 9 September 1956 in Haifa, Israel to Holocaust survivors. He received his Ph.D. in computer science at Princeton University in 1983 under the supervision of Richard Lipton.

In addition to holding several visiting positions, he was faculty member of the Hebrew University(1986-2003) and since 1999 is professor at the Institute for Advanced Study, Princeton. Among his many awards, the 1994 Nevanlinna Prize the 2009 Godel Prize (together with Omer Reingold and Salil Vadhan) and the 2021 Abel Prize (shared with László Lovász) stand out particularly.

Avi has written over 370 publications with over 170 co-authors according to DBLP. He has mentored more than 100 postdocs, many of whom became famous themselves. (such as Scott Aaronson, Irit Dinur, Subhash Khot, or Mario Szegedy, to name just a few)

Summary

For 40 years, Avi Widgerson has been an intellectual driving force in Computational Complexity Theory and the Mathematics of Computing. The reader is encouraged to peruse his conclusive book “Mathematics and Computation: A Theory Revolutionizing Technology and Science”; or at least to recall the definition and properties of the Zig-Zag Product, for example from Wikipedia. More information on Avi Wigderson can be found from his professional home page. We also mention his Abel Prize biography. The Award Ceremony and Lecture took place online on May 25 and 26, 3pm CEST.