Kolmogorov seminar 06 April

[kozmath]

Dear participants 

This monday 06 April, 18:30 Msk (17:30 Paris), zoom link:

https://us06web.zoom.us/j/84203550652?pwd=azOmtrm5wrHFaE4aVeuqhzHHF57hKd.1

Sasha Kozachinskiy will give the following talk:

The language generation in the limit framework [Kleinberg, Mullainathnan, NeurIPS 2024] is as follows. There is a known family F of languages (subsets of {0,1}^*). An adversary elects one of the languages L from F and starts writing down its words in some order. In each step, our task is to indicate a word that belongs to L but hasn’t been written down so far by the adversary. It turns out that for any countable F there is an algorithm that achieves this goal for all but finitely many steps.

I will explain a recent work of Kleinberg and Wei [Focs 2025], where it is shown how to do this and make sure that the subset of L that we generate is dense in it. That is, I will explain a simple version of their result – one can make sure that for infinitely many n, among the first n words of L in the lexicographic order, we have generated at least 0.49n. They also show that this is possible for all but finitely many n (and for some small positive constant instead of 0.49).

Best,

Sasha

[Nikolay Vereshchagin]

Dear participants of Kolmogorov seminar.

On next Monday, May 11, 18:30 Msk (17:30 Paris), our 6th year students  will present their graduate Diploma papers:

1. Darya Belogortseva,  "Information complexity of communication protocols", 

"Внутреннее разглашение информационных протоколов"

The talk will be in Russian

2. Gleb Volgin, Rotation protocol resilience.

The talk will be in English

3. Rustam Zyavgarov, On obstacles to materialization of the mutual information in well-mixing graphs,

 О препятствиях для материализации взаимной информации в графах со свойством быстрого перемешивания.

The talk will be in Russian

zoom link:

https://us06web.zoom.us/j/84203550652?pwd=azOmtrm5wrHFaE4aVeuqhzHHF57hKd.1