talk tomorrow (4 december)

29 views

Skip to first unread message

Alexander Shen

unread,

Dec 3, 2023, 10:23:04 AM12/3/23

to Kolmogorov seminar on complexity

Rectangles, complexity and games (A.Shen, based on discussions with
A.Kozachinsky and A.Romashchenko)

There are several cases that allow translation between probabilisitic,
combinatorial and complexity ststements. We look at some inequalities
(form papers of Romashchenko, Kaced, Zimand, Vereshchagin), extend them
for multidimensional case and observe that they have a natural game
interpretation. So the question (open) is to find a direct combinatorial
proof for the corresponding combinatorial statements. (It could be
interesting since the complexity proof uses some tricks more than once.)

Monday, November 27⋅16:30 – 19:15
Weekly on Monday
Zoom link:
https://u-bordeaux-fr.zoom.us/j/88402787361?pwd=WktCdEhBT3pXN0pLUGg4Z3RuMlpsQT09

andrei.pdf

Nikolay Vereshchagin

unread,

Dec 4, 2023, 12:47:08 AM12/4/23

to Kolmogorov seminar on complexity

Date: December 4, 2023

Time: 18:30 (MSK), 16:30 (CET)

Speaker: Alexander Shen

Title: Rectangles, complexity and games (based on discussions with A.Kozachinsky and A.Romashchenko)

There are several cases that allow translation between probabilisitic,
combinatorial and complexity ststements. We look at some inequalities
(form papers of Romashchenko, Kaced, Zimand, Vereshchagin), extend them
for multidimensional case and observe that they have a natural game
interpretation. So the question (open) is to find a direct combinatorial
proof for the corresponding combinatorial statements. (It could be
interesting since the complexity proof uses some tricks more than once.)

Zoom link:
https://u-bordeaux-fr.zoom.us/j/88402787361?pwd=WktCdEhBT3pXN0pLUGg4Z3RuMlpsQT09