Сложность булевых функций

Санкт-Петербург [compsciclub.ru], осень 2011

Описание

Семинар посвящен одному из самых известных и сложных направлений theoretical computer science — схемной сложности булевых функций. Схема является очень естественной моделью вычисления булевых функций. Из мощностных соображений легко следует, что для почти любой булевой функции \( f \colon \{0,1\}^n \rightarrow \{0,1\} \) размер минимальной вычисляющей её схемы экспоненциален. Несмотря на это, до сих пор не известно ни одной явно заданной функции, требующей схем более чем линейного размера. По этой причине интенсивно изучаются ограниченные модели вычислений (такие как монотонные схемы, схемы ограниченной глубины, формулы, ветвящиеся программы). На семинаре будут рассмотрены различные методы доказательства нижних оценок для таких моделей. Семинар будет основан на новой книге Стасиса Юкны Boolean Function Complexity: Advances and Frontiers.

Заинтересованным студентам будут выданы темы для доклада на семинаре. Подготовка к докладу подразумевает тщательное изучение выданной темы и подготовку слайдов. В конце семинара будет проведён экзамен.

Курсы по схемной сложности (с lecture notes!)

Дополнительная литература

Преподаватели