21.11.2013 (Ваня Михайлин) Вариации Direct Sum Theorem для запросовой и коммуникационной сложности.

В докладе будет рассказано о том, какими соотношениями связаны запросовые и коммуникационные сложности протоколов для вычисления одиночной функции со сложностью протоколов для вычисления большого числа копий этой функции (от независимых входов). Для запросовой сложности будет доказана линейная по числу копий оценка. Для коммуникационной сложности будет рассказан план доказательства нижней оценка пропорциональной корню из числа копий.