na pravakh (samo)reklamy
11 views
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 :https://cnrs.zoom.us/j/95176624010?pwd=VnJraXVheTdERDZ5d050Y3BzRXlNQT09
Meeting ID: 951 7662 4010
Passcode: 3YsFwf
Best regards
— Andrei
-------------
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 :https://cnrs.zoom.us/j/95176624010?pwd=VnJraXVheTdERDZ5d050Y3BzRXlNQT09
Meeting ID: 951 7662 4010
Passcode: 3YsFwf
Best regards
— Andrei
Reply all
Reply to author
Forward
0 new messages