Home

Семинар 23 марта 2007 года

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

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

Тема: Миникурс по сложности формул и схем. Третья лекция.

Abstract

В третьей лекции мы займемся формульной сложностью так называемых threshold функций.

Будут рассмотрены

- неконструктивный метод Вэлиэнта, показывающий сущестовование монотонных формул размера $ O(n^{5.3}) $ для majority,

- конструктивное доказательство Фридмана верхней оценки $ O(n*log n) $ для threshold-k (при k=const),

- доказательство Вегенера нижней оценки $ Omega(n*log n) $ для threshold-k (при k=const).

Все перечисленные результаты используют достаточно красивые комбинаторные идеи.

НИКАКИХ ПРЕДВАРИТЕЛЬНЫХ ЗНАНИЙ НЕ ТРЕБУЕТСЯ (определение сложности формулы при необходимости будет повторено).