Анализ булевых функций и приложения
Название спецкурса на английском языке
Analysis of boolean functions and related issues
Пререквизиты
Базовые знания математического анализа, линейной и высшей алгебры.
Целевая аудитория
1-2 курс
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра дискретной математики]
Семестр
Год
Тип курса
Спецкурс по выбору студента
Учебный год
2024/25
Список тем
Преобразование Уолша булевой функции и его свойства.
Полиномиальные представления булевой функции, их свойства и следствия.
Теорема Нисана-Сегеди о максимальном числе существенных переменных и ее усиления.
Теорема Симона-Вегенера и следствия из нее.
Регулярные булевы функции и их свойства.
Сложностные характеристики булевой функции и их взаимосвязь.
Деревья решений.
Приложения анализа булевых функций в теории сложности.
Нелинейность булевых функций.
Корреляционно-иммунные и устойчивые булевы функции.
Приложения анализа булевых функций в криптологии.
Полиномиальные представления булевой функции, их свойства и следствия.
Теорема Нисана-Сегеди о максимальном числе существенных переменных и ее усиления.
Теорема Симона-Вегенера и следствия из нее.
Регулярные булевы функции и их свойства.
Сложностные характеристики булевой функции и их взаимосвязь.
Деревья решений.
Приложения анализа булевых функций в теории сложности.
Нелинейность булевых функций.
Корреляционно-иммунные и устойчивые булевы функции.
Приложения анализа булевых функций в криптологии.
Список источников
O’Donnell R. Analysis of boolean functions. Cambridge University Press, 2014.
Wegener I., The complexity of boolean functions, Wiley-Teubner Series in Computer Science, Teubner, Stuttgart, 1987.
Carlet C. Boolean functions for cryptography and coding theory. Cambridge University Press, 2021.
Таранников Ю. В. О корреляционно-иммунных и устойчивых булевых функциях. Математические вопросы кибернетики, 2002, вып. 11, с. 91-148.
Nisan N., Szegedy M. On the degree of boolean functions as real polynomials, Computational Complexity 4 (1994), p. 301-313.
Chiarelli J., Hatami P., Saks M., An asymptotically tight bound on the number of relevant variables in a bounded degree boolean function, Combinatorica 40 (2020), p. 237-244.
Wellens J., Relationships between the number of inputs and other complexity measures of boolean functions, arXiv:2005.00566v2, 2022.
Huang H. Induced subgraphs of hypercubes and a proof of the sensitivity conjecture, arXiv:1907.00847v2, 2019.
Nisan N., CREW PRAMs and decision trees, SIAM J. Comput. 20 (6) (1991), p. 999 -1007.
Rubinstein D., Sensitivity vs. block sensitivity of Boolean functions, Combinatorica 15 (2) (1995), p. 297-299.
Buhrman H., de Wolf R. Complexity measures and decision tree complexity: a survey, Theoretical Computer Science 288 (2002), p. 21-43.
Wegener I., The complexity of boolean functions, Wiley-Teubner Series in Computer Science, Teubner, Stuttgart, 1987.
Carlet C. Boolean functions for cryptography and coding theory. Cambridge University Press, 2021.
Таранников Ю. В. О корреляционно-иммунных и устойчивых булевых функциях. Математические вопросы кибернетики, 2002, вып. 11, с. 91-148.
Nisan N., Szegedy M. On the degree of boolean functions as real polynomials, Computational Complexity 4 (1994), p. 301-313.
Chiarelli J., Hatami P., Saks M., An asymptotically tight bound on the number of relevant variables in a bounded degree boolean function, Combinatorica 40 (2020), p. 237-244.
Wellens J., Relationships between the number of inputs and other complexity measures of boolean functions, arXiv:2005.00566v2, 2022.
Huang H. Induced subgraphs of hypercubes and a proof of the sensitivity conjecture, arXiv:1907.00847v2, 2019.
Nisan N., CREW PRAMs and decision trees, SIAM J. Comput. 20 (6) (1991), p. 999 -1007.
Rubinstein D., Sensitivity vs. block sensitivity of Boolean functions, Combinatorica 15 (2) (1995), p. 297-299.
Buhrman H., de Wolf R. Complexity measures and decision tree complexity: a survey, Theoretical Computer Science 288 (2002), p. 21-43.
Дополнительная информация
Связь с лектором по эл. почте yutarann@gmail.com
День недели
суббота
Время
16:45-18:20
Аудитория
468
Дата первого занятия
Аудитория первого занятия
468
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.