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.)
andrei.pdf
Reply all
Reply to author
Forward
0 new messages