Название спецкурса на русском языке
Сложность булевых функций, часть 2
Перевод названия курса на английский язык
Boolean complexity, part 2
Авторы курса
Чашкин Александр Викторович
Целевая аудитория
2 курс
3 курс
4 курс
5 курс
6 курс
Подразделение
[Кафедра дискретной математики]
Семестр
Полгода (весна)
Тип курса
Спецкурс по выбору кафедры
Учебный год
2021/22
Аудитория
[Неприменимо]
Аннотация
В курсе рассматриваются следующие вопросы. Линейное хеширование в булевом кубе. Оценки ранга совершенных линейных хеш-функций. Вычисление булевых функций схемами в произвольном базисе. Сложность
вычисления частичных булевых функций. Сложность вычисление частичных булевых функций с заданным числом единиц. Сложность вычисление недоопределенных функций. Оценки сложности монотонных булевых функций. Средняя сложность. Оценки средней сложности булевых функций с заданным числом единиц. Оценки средней сложности монотонных булевых функций. Соотношения между средней и схемной сложностью. Соотношения между рандомизированной и детерминированой сложностью булевых функций.