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

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

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

• Topics in Circuit Complexity, Ryan Williams, Stanford, 2011
• Circuit Complexity and Communication Complexity, Ran Raz, Institute for Advanced Study, 2004
• Combinatorial Methods in Complexity Theory, Eric Allender, Rutgers, 1998
• Boolean Circuit Complexity, Uri Zwick, Berkeley, 1997

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

• Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009
• John E. Savage, Models of Computation: Exploring the Power of Computing, Addison-Wesley, 1998
• Ingo Wegener. The Complexity of Boolean Functions. John Wiley and Sons Ltd, 1987