Laboratory of Mathematical Logic at PDMI

Пятница, 15 мая, Zoom. Начало в 18:10.

Докладчик: Артур Рязанов (ПОМИ РАН).

Тема: Критерий Юкны для доказательства нижних оценок на монотонные вещественные схемы.

Abstract

В докладе мы рассмотрим критерий Стасиса Юкны для оценки сложности вычисления булевых функций монотонными вещественнымт схемами. Монотонная вещественная схема отличается от булевой тем, что в каждый гейт помечен монотонной функцией от двух вещественных переменных. Критерий Юкны связывает монотонную сложность булевой функции с её простыми комбинаторными свойствами.

У доклада планируется продолжение, в котором мы обсудим применение критерия Юкны для получения нижних оценок на сложность доказательств в системе Cutting Plane.

Видео доклада: https://www.youtube.com/watch?v=rz1LjaZSu7c