공통
2025년 서울대학교 10-10 프로젝트 「SNU 10-10 Private AI 가우스 석학강연」안내
작성자
admie
작성일
2025-09-24
조회
107
서울대학교 수리과학부 10-10 프로젝트에서 2025년 9월 30일(화)과 10월 1일(수) MIT의 David Gamarnik 교수님을 모시고
가우스 석학강연을 개최하여 알려드리니 관심있는 학생들의 많은 참여 바랍니다.
가우스 석학강연을 개최하여 알려드리니 관심있는 학생들의 많은 참여 바랍니다.
○ 일시: 2025년 9월 30일(화) ~ 10월 1일(수) 오후 4시 ~ 5시 30분
○ 장소: 서울대학교 상산수리과학관 101호
○ 연사: David Gamarnik 교수 (MIT)
○ 주최: 서울대학교 수리과학부 10-10 프로젝트
○ 강연제목: Turing in the Shadows of Nobel and Abel: An Algorithmic Story Behind Two Recent Prizes
○ 강연초록: The 2021 Nobel Prize in physics was awarded to Parisi “for the discovery of the interplay of disorder and fluctuations in physical systems.” The 2024 Abel Prize in mathematics was awarded to Talagrand “for his groundbreaking contributions to probability theory and functional analysis, with outstanding applications in mathematical physics and statistics.” What remained largely absent in the popular descriptions of these prizes, however, is the profound contributions their works have had to the field of algorithms and computation. The methods developed by Parisi and Talagrand have revolutionized the way we think algorithmically about optimization problems involving randomness, both classical and quantum.
In our talks we will explain how these ideas led to a remarkably precise characterization of which optimization problems admit fast algorithms, versus those which do not. The key obstruction to algorithms comes in the particular form of the solution space geometry, specifically the Overlap Gap Property (OGP), which we will define, and which originates in the works of Parisi and Talagrand. A range of examples we will consider include combinatorial optimization on random graphs, spin glasses, random perceptron, random number partitioning, and many others.
In Part I of the lecture we will consider how OGP is an obstruction to classical' algorithms such as those based on low degree polynomials and shallow Boolean circuits. In Part II we will discuss how OGP obstructs quantum algorithms both for classical and quantum Hamiltonians (objective functions).
