GN⁺: 2023년 ACM 튜링상, Avi Wigderson 교수에게 수여

• 이론 컴퓨터 과학은 컴퓨팅 분야의 수학적 기반을 다룸. "이 문제가 컴퓨팅을 통해 해결 가능한가?", "이 문제가 컴퓨팅으로 해결 가능하다면 얼마나 많은 시간과 자원이 필요한가?"와 같은 질문을 제기함. 또한 효율적인 알고리즘 설계 방법을 탐구함. 우리 삶에 영향을 미치는 모든 컴퓨팅 기술은 알고리즘으로 가능해짐. 강력하고 효율적인 알고리즘의 원리를 이해하는 것은 컴퓨터 과학뿐만 아니라 자연의 법칙에 대한 이해를 심화시킴. 이론 컴퓨터 과학은 흥미로운 지적 도전을 제시하는 분야로 알려져 있고, 종종 컴퓨팅의 실용적 응용 개선과 직접 관련되지 않지만, 이 분야의 연구 혁신은 암호학, 계산생물학, 네트워크 설계, 기계학습, 양자 컴퓨팅 등 거의 모든 분야의 발전으로 이어짐.

• 기본적으로 컴퓨터는 결정론적 시스템임. 알고리즘의 명령어 집합을 특정 입력에 적용하면 계산이 고유하게 결정되고, 특히 출력이 결정됨. 즉, 결정론적 알고리즘은 예측 가능한 패턴을 따름. 반면에 무작위성은 잘 정의된 패턴이나 사건/결과의 예측 가능성이 부족함. 우리가 살고 있는 세계는 무작위 사건(날씨 시스템, 생물학적/양자 현상 등)으로 가득 차 있어 보이기 때문에, 컴퓨터 과학자들은 알고리즘의 효율성을 높이기 위해 계산 과정에서 무작위 선택을 할 수 있도록 알고리즘을 보강해 왔음. 실제로 효율적인 결정론적 알고리즘이 알려지지 않은 많은 문제들이 확률적 알고리즘에 의해 효율적으로 해결되었음(약간의 오류 확률을 가지고 있지만 효율적으로 감소시킬 수 있음). 그러나 무작위성이 필수적인 것인가, 아니면 제거할 수 있는 것인가? 확률적 알고리즘의 성공을 위해 필요한 무작위성의 품질은 무엇인가?

• 아비 비그더슨 박사는 40년 동안 이론 컴퓨터 과학 연구를 선도해 왔으며, 컴퓨팅에서 무작위성과 유사 무작위성의 역할에 대한 이해에 근본적인 공헌을 해왔음. 컴퓨터 과학자들은 무작위성과 계산 난이도(효율적인 알고리즘이 없는 자연스러운 문제 식별) 사이에 주목할 만한 연결고리를 발견했음. 비그더슨 박사는 동료들과 함께 무작위성을 위해 어려움을 거래하는 것에 대한 매우 영향력 있는 일련의 연구를 수행했음. 그들은 표준적이고 널리 믿어지는 계산 가정 하에서, 모든 확률적 다항 시간 알고리즘이 효율적으로 무작위성을 제거할 수 있음을 증명했음(즉, 완전히 결정론적으로 만들 수 있음). 다시 말해, 무작위성은 효율적인 계산에 필수적이지 않음. 이 일련의 연구는 컴퓨팅에서 무작위성의 역할에 대한 우리의 이해와 무작위성에 대한 생각 방식을 혁신했음.

비그더슨 박사의 공헌

• "Hardness vs. Randomness" (Noam Nisan과 공동 저술): 이 논문은 다른 것들 중에서도 새로운 유형의 유사 무작위 생성기를 도입했고, 이전에 알려진 것보다 훨씬 약한 가정 하에서 무작위화된 알고리즘의 효율적인 결정론적 시뮬레이션이 가능함을 증명했음.

• "BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs" (László Babai, Lance Fortnow, Noam Nisan과 공동 저술): 이 논문은 "hardness amplification"을 사용하여 bounded-error probabilistic polynomial time(BPP)이 더 약한 가정 하에서 무한히 많은 입력 길이에 대해 subexponential time에서 시뮬레이션될 수 있음을 입증했음.

• "P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma" (Russell Impagliazzo와 공동 저술): 이 논문은 본질적으로 최적의 hardness vs randomness tradeoff를 가진 더 강력한 유사 무작위 생성기를 소개했음.

• 랜덤성과 관련된 연구를 넘어서 비그더슨 박사는 다중 증명자 대화형 증명, 암호학, 회로 복잡도 등 이론 컴퓨터 과학의 여러 다른 분야에서 지적 리더십을 발휘해 왔음.

GN⁺의 의견

• 수학적 측면에서 랜덤성과 계산 복잡도 사이의 관계를 입증한 비그더슨의 연구는 컴퓨터 과학과 수학의 접목이란 측면에서 큰 의의가 있음. 특히 랜덤성에 의존하던 많은 알고리즘들이 사실은 결정론적으로 동일하게 구현될 수 있음을 입증한 것은 컴퓨터 과학의 새로운 지평을 연 것으로 평가됨.

• 또한 효율성과 난해성의 관계에 대해 수학적으로 접근한 것 역시 이론 컴퓨터과학의 중요한 연구 주제가 될 것으로 보임. 난해한 문제일수록 그에 비례해 더 효율적인 알고리즘이 존재할 가능성이 있다는 것은 직관적이지 않은 통찰력임.

• 한편 비그더슨 교수가 이론 컴퓨터 과학 분야의 발전을 위해 수학과 컴퓨터과학의 접목을 강조하고 후학을 양성하는 데에도 힘썼다는 점은 학문 후속세대를 위한 좋은 귀감이 될 것으로 보임. 특히 수학의 아벨상과 컴퓨터과학의 튜링상을 모두 수상한 경력은 이론 컴퓨터 과학의 중요성을 보여주는 상징적 사례라 할만함.

[neo]

Hacker News 의견

• Avi Wigderson이 2023년 ACM A.M. Turing Award를 수상함. 계산 이론에 대한 기본적인 공헌, 특히 계산에서 무작위성의 역할에 대한 이해를 재구성하고 이론 컴퓨터 과학 분야에서 수십 년 간 지적 리더십을 발휘한 공로를 인정받음.

• Wigderson은 계산복잡도 이론, 알고리즘과 최적화, 무작위성과 암호학, 병렬 및 분산 컴퓨팅, 조합론, 그래프 이론 등의 분야에서 선도적인 인물이었으며, 이론 컴퓨터 과학과 수학 및 과학 간의 연결고리 역할도 수행함.

• Wigderson의 주요 업적 중 하나는 무작위성과 계산 난이도 사이의 놀라운 연관성을 발견한 것임. 그의 연구는 무작위성이 효율적인 계산에 반드시 필요하지 않다는 사실을 밝혀냄.

• 2021년에는 Abel Prize도 수상하여 이론/추상 수학과 컴퓨터 과학 분야 최고 영예를 모두 거머쥔 독특한 이력을 가짐.

• Wigderson의 책 "Mathematics and Computation"이 최근 출간되어 호평을 받고 있음.

• 그의 연구 결과에 따르면 어떤 명제가 증명 가능하다면 제로 지식 증명(zero-knowledge proof)도 가능하며, 유사 난수를 확률적 알고리즘에 적용하면 동일 문제에 대한 효율적인 결정적 알고리즘을 얻을 수 있다고 함. 이는 AI 등 확률적 계산 모델의 복잡도를 크게 줄일 수 있음을 시사함.