Speaker:
George Barmpalias (Chinese Academy of Sciences)
Time:
- 11:00AM(Time in Beijing)
- 4:00PM(Time in Auckland)
- March 11, 2021 (Thursday)
Address:
Online meeting
VooVmeeting:
ID: 222 489 953 Password: 202103
Link:
https://meeting.tencent.com/s/OgG2rzHAiky1
Abstract:
Randomness is a precious resource in computation and modeling, where access to a random source with specific properties is needed. Transforming one type of randomness to another is often needed as the available source may not have the desired distribution. In 1951, von Neumann addressed this problem, also giving a way to transform a Bernoulli distribution of unknown bias to a uniformly distributed bit-stream. Such methods have since found applications in algorithmic learning and complexity. Yet there are situations where such translations are hard, or even impossible. Suppose that you are given access to a random stream and you need to transform it into k distinct streams, without large entropy-loss. We show that this task, even when the total number of bits remains the same, is as hard as it can be. This is a general phenomenon, and there is a curious parallel with Levin’s impossibility of randomized completions of Peano arithmetic: the hardness of randomly obtaining formally consistent answers to all 300-bit sentences in arithmetic is equal the hardness of re-arranging an incompressible bit-string into an array of 300 incompressible strings with the same total number of bits.
In my talk I will explore the interactions between probability, randomness, computation and logic, guided by the above discovery which is understood without specialized background, but is hopefully also interesting to the specialist. This is joint work with Wang Wei (Guangzhou).
Speaker Bio:
George is a researcher working in mathematical logic, theory of computation, learning and information, as well as the dynamics of social networks and other decentralized interaction protocols. He is a Professor at the State Key Lab of Computer Science, Chinese Academy of Sciences, and has previously worked and taught in Leeds, Amsterdam and Wellington. His recent research includes the discovery of optimal high-entropy coding methods, surprising dynamic phase transitions in models of social mobility, as well as implementations of network dynamics and graphical coding games. More info: http://barmpalias.net
Organizers:
Bakhadyr Khoussainov, Jiamou Liu, and Mingyu Xiao