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

 (awards.acm.org)
1P by GN⁺ | ★ favorite | 댓글 1개
  • ACM은 Avi Wigderson을 2023년 ACM A.M. Turing Award 수상자로 선정하며, 계산 이론과 계산에서 무작위성의 역할을 새로 이해하게 만든 공로를 인정함
  • Wigderson은 Institute for Advanced Study의 Herbert H. Maass Professor로, 계산 복잡도 이론과 알고리듬, 암호학, 병렬·분산 계산, 조합론, 그래프 이론을 폭넓게 이끈 인물임
  • 핵심 업적은 hardness for randomness 연구로, 널리 믿어지는 계산 가정 아래 확률적 다항시간 알고리듬을 결정론적으로 시뮬레이션할 수 있음을 보인 점임
  • 관련 논문들은 의사난수 생성기, BPP의 부분지수 시간 시뮬레이션, hardness-vs-randomness 절충을 제시하며 이론 컴퓨터 과학 여러 영역에 영향을 줌
  • Turing Award는 Google 지원으로 100만 달러 상금이 수여되며, Wigderson은 기술적 성과뿐 아니라 젊은 연구자를 이끈 멘토로도 평가받음

ACM Turing Award 수상 배경

  • ACM은 Avi Wigderson을 2023년 ACM A.M. Turing Award 수상자로 선정함
  • 수상 사유는 계산 이론에 대한 기초적 기여, 계산에서 무작위성의 역할에 대한 이해를 재구성한 업적, 이론 컴퓨터 과학에서 수십 년간 보인 지적 리더십임
  • Wigderson은 뉴저지 프린스턴의 Institute for Advanced Study 수학부 Herbert H. Maass Professor임

  • 주요 활동 분야

    • 계산 복잡도 이론
    • 알고리듬과 최적화
    • 무작위성과 암호학
    • 병렬·분산 계산
    • 조합론과 그래프 이론
    • 이론 컴퓨터 과학과 수학·과학의 연결
    • ACM A.M. Turing Award는 “컴퓨팅의 노벨상”으로 불리며, Google, Inc.의 재정 지원으로 100만 달러 상금이 제공됨
    • 이 상은 컴퓨팅의 수학적 기초를 정립한 영국 수학자 Alan M. Turing의 이름을 따서 명명됨

이론 컴퓨터 과학이 다루는 질문

  • 이론 컴퓨터 과학은 컴퓨터 과학의 수학적 토대를 다루며, “이 문제가 계산으로 풀릴 수 있는가”, “풀린다면 시간과 자원이 얼마나 필요한가” 같은 질문을 다룸
  • 이 분야는 효율적인 알고리듬 설계 원리도 탐구함
  • 알고리듬은 일상에서 쓰이는 컴퓨팅 기술을 가능하게 하는 기반임
  • 이론 컴퓨터 과학은 당장 실용 응용을 개선하지 않는 지적 도전도 다루지만, 연구 돌파구는 여러 영역의 발전으로 이어질 수 있음
    • 암호학
    • 계산 생물학
    • 네트워크 설계
    • 기계 학습
    • 양자 컴퓨팅

계산에서 무작위성이 중요한 이유

  • 컴퓨터는 근본적으로 결정론적 시스템이며, 주어진 입력에 대해 알고리듬의 명령 집합이 계산과 출력을 유일하게 결정함
  • 무작위성은 사건이나 결과에서 명확한 패턴 또는 예측 가능성이 없는 상태를 뜻함
  • 현실 세계에는 날씨 시스템, 생물학적 현상, 양자 현상처럼 무작위적으로 보이는 사건이 많음
  • 컴퓨터 과학자들은 효율성을 높이기 위해 알고리듬이 계산 과정에서 무작위 선택을 하도록 확장해 왔음
  • 효율적인 결정론적 알고리듬이 알려지지 않았던 많은 문제도 작은 오류 확률을 가진 확률적 알고리듬으로 효율적으로 풀 수 있음
    • 이 오류 확률은 효율적으로 줄일 수 있음
  • 핵심 질문은 무작위성이 필수인지, 제거 가능한지, 확률적 알고리듬 성공에 필요한 무작위성의 품질이 무엇인지임
  • 계산에서 무작위성과 의사무작위성의 동작을 더 잘 이해하면 더 나은 알고리듬 개발과 계산 자체의 본성 이해로 이어질 수 있음

Wigderson의 핵심 연구 기여

  • Wigderson은 40년간 이론 컴퓨터 과학 연구를 이끈 인물로, 계산에서 무작위성과 의사무작위성의 역할을 이해하는 데 기초적 기여를 함
  • 컴퓨터 과학자들은 무작위성과 계산 난이도, 즉 효율적 알고리듬이 없는 자연스러운 문제를 식별하는 일 사이의 중요한 연결을 발견함
  • Wigderson과 공동 연구자들은 hardness for randomness를 다룬 영향력 있는 연구들을 발표함
  • 이 연구들은 표준적이고 널리 믿어지는 계산 가정 아래 모든 확률적 다항시간 알고리듬을 효율적으로 결정론화할 수 있음을 보임
  • 이 결과는 효율적 계산에 무작위성이 반드시 필요하지 않을 수 있음을 보여줌
  • 해당 연구 흐름은 계산에서 무작위성의 역할과 무작위성에 대한 사고방식을 바꿈

  • 대표 논문 3편

영향 범위와 추가 업적

  • Wigderson의 세 논문은 무작위성과 결정론화 영역을 넘어 이론 컴퓨터 과학 여러 분야에 영향을 줌
  • 이 논문들의 아이디어는 이후 여러 주요 연구자의 영향력 있는 논문에 활용됨
  • Omer Reingold, Salil Vadhan, Michael Capalbo와의 논문에서는 expander graph의 첫 효율적 조합론적 구성을 제시함
    • expander graph는 강한 연결 특성을 가진 희소 그래프임
    • 수학과 이론 컴퓨터 과학 모두에서 중요한 응용을 가짐
  • 무작위성 외에도 Wigderson은 다음 분야에서 지적 리더십을 보임
    • multi-prover interactive proofs
    • 암호학
    • 회로 복잡도

멘토링과 평가

  • Wigderson은 획기적인 기술적 기여뿐 아니라 많은 젊은 연구자를 지도한 존경받는 멘토이자 동료로 인정받음
  • 방대한 지식, 기술적 능력, 친근함, 열정, 관대함은 우수한 젊은 연구자들이 이론 컴퓨터 과학 경력을 추구하도록 이끈 요소로 꼽힘
  • ACM President Yannis Ioannidis는 Wigderson이 수학 분야 평생 업적의 가장 중요한 영예로 여겨지는 Abel Prize도 받았다고 밝힘
  • Ioannidis는 수학이 컴퓨터 과학의 토대이며, Wigderson의 작업이 다양한 수학 하위 분야를 이론 컴퓨터 과학과 연결했다고 평가함
  • Google Senior Vice President Jeff Dean은 Wigderson의 무작위성 및 다른 주제 연구가 지난 30년간 이론 컴퓨터 과학의 의제를 설정했다고 밝힘
  • Dean은 Wigderson이 아이디어와 연구 방향을 만들고, 젊은 연구자들이 그 방향에서 연구하도록 동기를 부여한 멘토였다는 점도 강조함

Turing Award와 Wigderson의 추가 주요 논문

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 발표에서 언급된 Wigderson의 주요 논문 두 편은 잘 알려진 온라인 강의 From Nand to Tetris를 만든 교수 중 한 명인 Noam Nisan과 공저임

    • Nisan 교수도 대단한 인물임. 계산 이론에서 일급 성과를 낸 뒤, 꽤 다른 분야인 알고리즘 게임 이론에서도 큰 영향을 남겼음
      한 사람이 이렇게 다양한 성취를 할 수 있다는 점도 좋고, 그런 유연성을 허용한 시스템도 인상적임
    • 책도 있음. 최근에 2판이 나왔음

  • Quanta의 좋은 기사도 있음: https://www.quantamagazine.org/avi-wigderson-complexity-theo...
    Wigderson에게 시킨 포즈가 다양해서 재미있었음. 너무 어색해 보임. “자, 이 의자에 앉아서 창밖을 그윽하게 바라보세요” 같은 느낌

    • “무작위성의 불합리한 효과성”이 Wigderson으로 하여금 무작위성 자체의 본질을 생각하게 했다는 대목이 흥미로움
      복잡도 클래스는 최악의 경우 성능을 다루는 것으로 이해하고 있는데, 좋은 의사난수 생성기와 좋은 무작위화 알고리즘이 있어도 RNG + seed + problem instance의 어떤 조합도 지수 시간이 걸리지 않는다는 걸 어떻게 증명하는지 개략적으로 알고 싶음
    • 정정문을 보면 원래 기사에는 Wigderson이 University of Haifa를 다녔다고 했지만 실제로는 이스라엘 하이파의 Technion을 졸업했다고 되어 있음
      기자가 이걸 어떻게 헷갈렸는지 궁금함
    • “의자에 앉아 창밖을 보는” 포즈는 Martin Scorsese나 Sopranos식 포즈 같음. 요양원에 있는 늙은 갱스터 같은 장면임

  • Scott Aaronson이 Avi Wigderson의 강연 하나가 자신의 진로에 어떤 영향을 줬는지 적어 둔 글이 있음: https://scottaaronson.blog/?p=2925

  • “Israeli Wins Turing Prize, Computing's Highest Honor, for Insights on Randomness”에 추가 정보가 있음: [1] 및 보관본 [2]
    [1] https://www.haaretz.com/israel-news/2024-04-10/ty-article/.p...
    [2] https://archive.is/e8uix

  • Wigderson 연구 중 어려움과 무작위성의 교환 쪽을 따라잡으려면 어디서 시작하면 좋을지 궁금함
    Turing상 수상자를 전혀 들어본 적 없는 경우가 흔치 않은데, 이 사람은 완전히 시야 밖에 있었음

    • 그의 책을 보면 됨: https://www.math.ias.edu/avi/book
    • “표준적이고 널리 믿어지는 계산 가정”이 무엇인지 궁금함
      아마 NP-완전 문제에 대한 확률적 근사도 다항 시간은 아니라는 뜻인가 싶고, 아니면 무작위성을 제거한 버전도 여전히 근사 알고리즘이라는 뜻인지 헷갈림

  • Wigderson의 책을 막 집어 들었는데 지금까지는 마음에 듦: https://press.princeton.edu/books/hardcover/9780691189130/ma...

    • 개인 연구와 교육 목적이라면 책의 최종 초안을 여기서 볼 수 있음: https://www.math.ias.edu/avi/book
    • 책을 봤는데 대학원생이나 상급 학부생에게 더 맞는 수준으로 보임
      컴퓨터과학/수학 학부 배경이 좀 녹슨 사람에게 계산 주제를 더 기초적으로 다루는 책을 추천해 줄 수 있는지 궁금함

  • 관련 기사에 이런 문장이 있음: https://www.quantamagazine.org/avi-wigderson-complexity-theo...
    “어떤 명제가 증명 가능하다면, 그것은 영지식 증명도 가진다”라니 머리가 터지는 느낌임
    또 “무작위 비트 대신 의사난수 비트를 확률적 알고리즘에 넣으면 같은 문제에 대한 효율적인 결정적 알고리즘이 된다”는 것도 말이 안 되게 놀라움
    AI도 확률적 계산이니까, 내가 제대로 읽은 거라면 현재 모델의 복잡도를 몇 자릿수 줄일 수 있다는 뜻 아닌가 싶음. 초보자의 착각이면 누가 꺼내줬으면 함

    • 정확히 무슨 말인지는 모르겠지만 적어도 그 뜻은 아님. AI는 이미 의사난수를 쓰고 결정적임
      효율을 높이려고 아날로그 계산을 쓰는 특이한 AI 가속기 칩 같은 예외는 있음
    • 아쉽지만 아님. 첫째, 그 결과는 탐색 문제가 아니라 결정 문제에 적용됨
      둘째, 만들어지는 결정적 알고리즘은 무작위화 알고리즘보다 훨씬 덜 효율적임. 다만 약한 가정하에서 같은 복잡도 클래스에 속할 뿐임

  • 기사 중 이 부분이 좋았음: “응용이 동기는 아니지만, 기초 연구에서도 쓰임새를 찾을 수 있다는 건 안다. Alan Turing을 생각해 보라. 그는 Entscheidungsproblem에 대한 논리학 수학 논문을 잘 알려지지 않은 저널에 썼다. 응용이 동기는 아니었다”
    Feynman의 접시 일화와 비슷함. 대학 식당에서 본 것을 가볍게 반응한 데서 시작해 결국 Nobel상으로 이어졌음
    요지를 더 넓히면, 현대 학계는 바로 이런 호기심 기반 탐구를 억누르는 쪽으로 가고 있음

  • ACM에 따르면 Avi Wigderson은 계산에서 무작위성의 역할에 대한 이해를 재편하는 등 계산 이론에 기초적 기여를 했고, 이론 컴퓨터과학에서 수십 년간 지적 리더십을 보여 2023 ACM A.M. Turing Award 수상자로 선정됨
    Wigderson은 뉴저지 프린스턴 Institute for Advanced Study 수학부의 Herbert H. Maass Professor이며, 계산 복잡도 이론, 알고리즘과 최적화, 무작위성과 암호학, 병렬·분산 계산, 조합론, 그래프 이론, 이론 컴퓨터과학과 수학·과학의 연결 등에서 핵심 인물로 활동해 왔음
    2021년에 Abel상도 받아서, 이론/추상 수학과 컴퓨터과학의 최고 영예를 함께 받은 꽤 독특한 조합이 됨

    • 이론 컴퓨터과학과 수학의 겹침은 대부분이 아는 것보다 훨씬 큼
      간단한 예로 MIT의 이론 컴퓨터과학 과목 목록 https://catalog.mit.edu/subjects/6/을 보면, 얼마나 많은 과목이 수학인 course 18과 교차 개설되는지 확인할 수 있음
    • 엄밀히 말하면 수학의 최고 영예는 Fields Medal임
      물론 내가 뭐라고 할 처지는 아니지만

  • 확률/무작위성과 계산 주제로 초급 친화적인 것부터 고급까지 공부할 만한 자료 추천이 궁금함
    Google에서는 Eli Upfal과 Michael Mitzenmacher의 “Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis”가 나오지만, 초급/입문용 책·글·영상을 잘 못 찾겠음

답변달기