City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Лекция 7
Communication Complexity

What: Lecture
When: Saturday, 07 March 2009, 12:25–13:55
Where: ПОМИ РАН

Description

Теорема о переделывании общего источника в частный с увеличением сложности на \( O(\log n): R_{\epsilon+\delta}(f) \) не превосходит \( R^{pub}_{\epsilon}(f)+O(\log n-\log \delta)) \). Нижняя оценка \( R^{pub}_{\epsilon}(f) \) методом трудных распределений вероятностей на входных парах. Неоднородность (discrepancy) функции для данного распределения и оценка трудности распределения через неоднородность. Линейная нижняя оценка для \( R^{pub}_{\epsilon}(IP) \). Нижняя оценка для неоднородности предиката DISJ: для любого распределения \( \mu \) выполнено \( disc_\mu(DISJ) n > 1 \).

Video