Appears in collection : 2016 - T1 - WS2 - Fundamental inequalities and lower bounds theme

Patrascu showed a connection between the problem of proving lower bounds on dynamic data-structure and proving lower bounds for an intriguing communication problem with advice. He made tempting conjectures on the communication problem that if true would yield polynomial lower bounds for dynamic data-structure. In this talk, we will show that the communication problem is more delicate than what one may believe on first sight. In particular, the strongest form of Patrascu's conjecture turns out to be false!