Title：Complexity of Enumerations and Games

Speaker：George Barmpalias (Chinese Academy of Sciences)

Time: 2025/3/18 (Tuesday) 15:10-18:00

Location: Room 215, Natural Sciences Teaching Building (理教), Peking University

Abstract:

I will give an introduction to ways we can measure the complexity of objects, with an emphasis on descriptive complexity: the length of the shortest description of the object. This is known as Kolmogorov complexity, captures the amount of intrinsic information, is related to compression and 2-player games are often used towards determining it. Then I will present some results on the compressibility of enumerations and demonstrate how one can reduce the solution of a problem to solving a corresponding 2-player game (find a winning strategy for one of the players).

Joint work with B. Zhan, X. Zhang.

Arxiv: https://arxiv.org/abs/2304.03030

Game: http://barmpalias.net/share/games/even.html