Home

Семинар 28 октября 2005 года

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

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

Тема: Нижние оценки для древовидных систем доказательств Ловаса-Шрайвера.

Abstract

Доклад по статье P.Beame, T.Pitassi, and N.Segerlind ``Lower bounds for Lovasz-Schrijver systems and beyond follow from multiparty communication complexity''.

В статье показывается связь нижних оценок для коммуникационной сложности с несколькими участниками, не знающими свою информацию (multiparty number-on-the-forehead communication complexity), и древовидных систем доказательств Ловаса-Шрайвера. В частности, данным методом доказывается нижняя оценка $ n^{\Omega(1)} $ для древовидной системы Ловаса-Шрайвера на цейтинских формулах.