na pravakh (samo)reklamy

Skip to first unread message

Alexander Shen

Oct 23, 2023, 4:57:06 PM10/23/23
to Kolmogorov seminar on complexity
Message from Andrei Romashchenko that I mentioned today:


Dear colleagues,

The next meeting of the online seminar on Algorithmic Aspects of Information Theory is scheduled on Wednesday October 25, 8:00-9h15am Pacific / 17h-18h15 CET.

Our speaker is Alexander Shen (CNRS - LIRMM, Montpellier)

Title of the talk: Information theoretic proofs (a survey).

Abstract: Some theorems that have nothing to do with information theory can be proven using an information-theoretic argument (entropy, or Kolmogorov complexity, or counting via compression). For example, why are there infinitely many prime numbers? If there were only M prime numbers, then each integer could be encoded by the list of M exponents in its prime decomposition, so we could specify each n-bit number by only M×O(log n) bits, a contradiction. We will discuss several examples of proofs of that type, including other bounds for the distribution of prime numbers, but not only them.

Link to the Zoom session :

Meeting ID: 951 7662 4010
Passcode: 3YsFwf

Best regards
— Andrei

Reply all
Reply to author
0 new messages