Home

Семинар 29 февраля 2008 года

Пятница, 29 февраля, комната 106. Начало в 17:30.

Докладчик: А. Кожевников.

Тема: Multiparty Communication Complexity of Disjointness.

Abstract

(доклад по статье A. Chattopadhyay, A. Ada )

The paper proves lower bounds of $ n^{Omega(1)} $ on the communication complexity in the "Number on the Forehead" model needed by k players to compute the Disjointness function, provided k is a constant. We also discuss applications of these lower bounds to proof complexity.