2025년 10-10 가우스 석학강연

2025년 10-10 가우스 석학강연

675
일자 2025-09-30
강연자 David Gamarnik
장소 상산수리과학관 101호
안녕하십니까. 서울대학교 수리과학부 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).
4164041378713795241.4164044294985222600@dooray.com?type=raw


프린트