Коммуникационная сложность и глубина схем (А. Головнёв)
Сложность булевых функций


Что: Лекция
Когда: Воскресенье, 06 ноября 2011, 13:00–14:35
Где:
Слайды: boolean_functions_complexity_lecture_061111.pdf

Описание

Коммуникационная сложность, игры Карчмера-Вигдерсона, покрытие прямоугольниками, связь с глубиной схем: \( cc(f)=D(f) \), монотонная глубина, примеры.

Материалы

Приложенные файлы