Home

Семинар 5 октября 2007 года

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

Докладчик: А. Куликов.

Тема: Матричные методы доказательства нижних оценок.

Abstract

Доклад по статье А.А.Разборова "Application of matrix methods to the theory of lower bounds in computational complexity".

We present some criteria for obtaining lower bounds for the formula size of Boolean functions. In the monotone case we get the bound $ n^{Omega(log(n))} $ for the function "MINIMUM COVER" using methods considerably simpler than all previously known. In the general case we are only able to prove that the criteria yield an exponential lower bound when applied to almost all functions. Some connections with graph complexity and communication complexity are also given.