Mathematical Logic and Discrete Mathematics at PDMI

Пятница, 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).

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

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