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

Санкт-Петербург [compsciclub.ru], весна 2017

Описание

Булевы функции — это одни из наиболее важных и наиболее изученных объектов в теоретической информатике. Множество важнейших теоретических и прикладных вопросов можно переформулировать на языке булевых функций. На данном семинаре мы будем изучать сложность булевых функций — будем доказывать нижние оценки на размеры описания булевых функций в виде формул, схем и некоторых других представлений. Основные материалы, обсуждаемые на семинаре, будут из книги Boolean Function Complexity: Advances and Frontiers, Stasys Jukna, 2012.

Семинар входит в магистерскую программу теоретическая информатика Академического университета.

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

Список лекций