Булевы схемы: недавние результаты и открытые задачи

Булевы схемы представляют собой простую, естественную и выразительную модель вычислений, достаточно мощную, чтобы моделировать алгоритмы. Схемы имеют применения в таких областях компьютерных наук, как алгоритмы, теория сложности, криптография, формальная верификация, проектирование аппаратуры, машинное обучение, SAT-солверы.

Я расскажу про недавние результаты нашей группы в области синтеза схем и нижних оценок на размер схем и время работы алгоритмов. Отдельное внимание уделю открытым задачам и перспективным, на мой взгляд, направлениям для сотрудничества в этой области.