Alexander Shen
unread,Feb 23, 2024, 6:23:24 AMFeb 23Sign in to reply to author
Sign in to forward
You do not have permission to delete messages in this group
Either email addresses are anonymous for this group or you need the view member email addresses permission to view the original message
to Kolmogorov seminar on complexity
Seminar meeting: March 04, European time 16.30 (Moscow time 18.30)
Combinatorial rectangles, Kolmogorov complexity and experts' aggregation
There is a classical result in communication complexity saying that if
some communication protocol is applied to jointly distributed inputs a
and b, then the transcript \pi has a non-negative "triple information
with a and b". We will discuss its meaning, extension to partitions,
Kolmogorov complexity version for one rectangle, implication for a
combinatorial game and interpretation of this game in terms of
aggregation experts' opinions. (An _incomplete_ draft attached FYI)