The Abel lectures: László Lovász and Avi Wigderson
0:30 Introduction by the Abel Prize Committee Chair, Hans Munthe-Kaas
02:42 László Lovász: Continuous limits of finite structures
49:27 Questions and answers
1:00:31 Avi Wigderson: The Value of Errors in Proofs
1:41:24 Questions and answers
1:50:20 Final remarks by John Grue, Chair of the Abel Board
László Lovász - Continuous limits of finite structures
The idea that a sequence of larger and larger finite structures tends to a limit has been around for quite a while, going back (at least) to John von Neumann's "continuous geometries".
After a brief survey of the history of such constructions, we turn to limits of graph sequences; this theory was worked out for dense graphs and bounded-degree graphs more than a decade ago. The "intermediate" cases (for example, the sequence of hypercubes, or incidence graphs of finite geometries) represent much more difficult problems, and only partial results can be reported. Perhaps surprisingly, the limit objects, whenever known, are best described as Markov chains on measurable spaces.
Why are we making such efforts to construct such limit objects? The talk will show a couple of examples of interesting graph-theoretic problems where graph limits are needed even for the precise statement of the problem, or as the starting point of the solution.
Avi Wigderson - The Value of Errors in Proofs
A few months ago, a group of theoretical computer scientists posted a paper on the Arxiv with the strange-looking title "MIP* = RE", surprising and impacting not only complexity theory but also some areas of math and physics. Specifically, it resolved, in the negative, the "Connes' embedding conjecture" in the area of von-Neumann algebras, and the "Tsirelson problem" in quantum information theory. It further connects Turing's seminal 1936 paper which defined algorithms to Einstein's 1935 paper with Podolsky and Rosen which challenged quantum mechanics. You can find the paper here: https://arxiv.org/abs/2001.04383
As it happens, both acronyms MIP* and RE represent proof systems, of a very different nature. To explain them, we'll take a meandering journey through the classical and modern definitions of proof. I hope to explain how the methodology of computational complexity theory, especially modeling and classification (of both problems and proofs) by algorithmic efficiency, naturally leads to the genaration of new such notions and results (and more acronyms, like NP). A special focus will be on notions of proof which allow interaction, randomness, and errors, and their surprising power and magical properties.
Видео The Abel lectures: László Lovász and Avi Wigderson канала The Abel Prize
02:42 László Lovász: Continuous limits of finite structures
49:27 Questions and answers
1:00:31 Avi Wigderson: The Value of Errors in Proofs
1:41:24 Questions and answers
1:50:20 Final remarks by John Grue, Chair of the Abel Board
László Lovász - Continuous limits of finite structures
The idea that a sequence of larger and larger finite structures tends to a limit has been around for quite a while, going back (at least) to John von Neumann's "continuous geometries".
After a brief survey of the history of such constructions, we turn to limits of graph sequences; this theory was worked out for dense graphs and bounded-degree graphs more than a decade ago. The "intermediate" cases (for example, the sequence of hypercubes, or incidence graphs of finite geometries) represent much more difficult problems, and only partial results can be reported. Perhaps surprisingly, the limit objects, whenever known, are best described as Markov chains on measurable spaces.
Why are we making such efforts to construct such limit objects? The talk will show a couple of examples of interesting graph-theoretic problems where graph limits are needed even for the precise statement of the problem, or as the starting point of the solution.
Avi Wigderson - The Value of Errors in Proofs
A few months ago, a group of theoretical computer scientists posted a paper on the Arxiv with the strange-looking title "MIP* = RE", surprising and impacting not only complexity theory but also some areas of math and physics. Specifically, it resolved, in the negative, the "Connes' embedding conjecture" in the area of von-Neumann algebras, and the "Tsirelson problem" in quantum information theory. It further connects Turing's seminal 1936 paper which defined algorithms to Einstein's 1935 paper with Podolsky and Rosen which challenged quantum mechanics. You can find the paper here: https://arxiv.org/abs/2001.04383
As it happens, both acronyms MIP* and RE represent proof systems, of a very different nature. To explain them, we'll take a meandering journey through the classical and modern definitions of proof. I hope to explain how the methodology of computational complexity theory, especially modeling and classification (of both problems and proofs) by algorithmic efficiency, naturally leads to the genaration of new such notions and results (and more acronyms, like NP). A special focus will be on notions of proof which allow interaction, randomness, and errors, and their surprising power and magical properties.
Видео The Abel lectures: László Lovász and Avi Wigderson канала The Abel Prize
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
Alex Lubotzky: Simple groups, buildings and applicationsSijue Wu: The Quartic Integrability and Long Time Existence of Steep Water Waves in 2dTristan Riviere: The work of Louis Nirenberg on Partial Differential EquationsYves Meyer Acceptance Speech - The Abel PrizeOfer Zeitouni: Large Deviations at WorkJalal Shatah: Recent Advances in Wave Turbulence Theory and PracticeJacques Tits: Algebraic simple groups and buildingsGregory Margulis: A lifelong relationship with mathematics (2022)John Thompson: Dirichlet series and SL(2,Z)John Tate - The Abel Prize interview 2010The 2022 Abel Prize Award CeremonyWelcome to the online Abel Prize celebrationsLuis Caffarelli: Non-linear and non-local surface structure problems and some of its applicationsAvi Wigderson’s reaction to winning the Abel PrizeLouis Nirenberg - The 2015 Abel Prize LaureateClaire Voisin: Mixed Hodge structures and the topology of algebraic varietiesAbel Award ceremony 2016 — Andrew WilesYakov Sinai Acceptance Speech - The Abel PrizeUlrike Tillmann: Advice to Young Mathematicians (2023)Interview with Yves MeyerThe Abel Prize announcement 2016 - Andrew Wiles