Обсудим субэкспоненциальные алгоритмы: введём $SERF$-сведение и докажем полноту относительно него для некоторых задач. Также рассмотрим вопрос о доказательстве нижних оценок. Рассмотрим нижние оценки для $AC^0$. Покажем, что с большой долей вероятности случайные полиномы второй степени для $GF(2)$ требуют экспоненциальный размер для схем $\Sigma_3^k$ при $k=o(\log \log n)$. Как следствие, получим пcевдослучайный генератор.

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