Элементы теории сложности схем
Название спецкурса на английском языке
Elements of circuit complexity
Пререквизиты
Представление о булевых функциях и схемах из функциональных элементов из курса “Теория дискретных функций”. Базовые знания теории вероятностей.
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра дискретной математики]
Семестр
Полгода (весна)
Тип курса
Спецкурс по выбору кафедры
Учебный год
2024/25
Список тем
Оценки сложности схем ограниченной глубины. Лемма о переключении.
Оценки сложности схем в монотонном базисе. Лемма о подсолнухах.
Метод приближений.
Оценки сложности схем в монотонном базисе. Лемма о подсолнухах.
Метод приближений.
Список источников
S. Arora, B. Barak. Computational complexity: the modern approach
Дополнительная информация
Известно, что существуют булевы функции, которые невозможно вычислить схемами небольшого размера (и, более того, таковы почти все булевы функции). Несмотря на это, доказательства того, что конкретная булева функция имеет высокую сложность, известны лишь для некоторых (и весьма ограниченных) классов схем.
Спецкурс посвящен изложению классических результатов такого типа.
Связь с лектором: yuri.kombarov@gmail.com
День недели
четверг
Время
16:45-18:20
Аудитория
470а
Аудитория первого занятия
Ещё не назначена
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.