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

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

Date:

Friday, May 8, 2020 - 18:10

Abstract:

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

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

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