Пятница 08.05. Артур Рязанов (ПОМИ РАН): "Критерий Юкны для доказательства нижних оценок на монотонные вещественные схемы"

Speaker: 
Артур Рязанов (ПОМИ РАН)
Date: 
Friday, May 8, 2020 - 18:10
Place: 
Zoom
Abstract: 

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

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

Номер конференции Zoom и пароль будут отправлены на рассылку семинара за несколько часов до доклада.