Laboratory of Mathematical Logic at PDMI

Пятница, 21 октября, комната 106. Начало в 17:30.

Докладчик: Д. Ицыксон.

Тема: Нижние оценки для схем константной глубины.

Abstract

Доклад по диссертации Johanа Hastadа.

Будет доказано, что любая логическая схема, состоящая из операций AND, OR, NOT, вычисляющая сумму n битов по модулю два, имеющая константную глубину, имеет экспоненциальный размер.