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

[PDMI seminars]

Семинар по теории сложности вычислений

Тема: Применение критерия Юкны для нижних оценок в системе доказательств Cutting Planes
Место: Zoom
Время: 22.05.2020, 18:10
Докладчик: Артур Рязанов (ПОМИ РАН)

Abstract:
Это продолжение предыдущего доклада. Мы рассмотрим взвешенный критерий Стасиса Юкны для доказательства нижних оценок на монотонную вещественную схемную сложность. Затем мы покажем, как его применить для доказательства экспоненциальной нижней оценки на сложность опровержения бинарного принципа Дирихле в системе доказательств Cutting Planes (результат Павла Пудлака и Павла Грубеша).

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

[Dmitry M. Itsykson]

Семинар состоится сегодня в 18-10, подключиться к нему можно по ссылке

https://us02web.zoom.us/j/81094325097?pwd=amJLMmFrd2lXbkRTNE5KUnBranFqZz09

Идентификатор конференции: 810 9432 5097
Пароль: 489503

--
Вы получили это сообщение, поскольку подписаны на группу "spb-complexity".
Чтобы отменить подписку на эту группу и больше не получать от нее сообщения, отправьте письмо на электронный адрес spb-complexit...@googlegroups.com.
Чтобы посмотреть обсуждение на веб-странице, перейдите по ссылке https://groups.google.com/d/msgid/spb-complexity/000000000000db21f105a5e72a8e%40google.com.

[Alexander V. Smal]

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

Саша

> Чтобы посмотреть обсуждение на веб-странице, перейдите по ссылке https://groups.google.com/d/msgid/spb-complexity/CAMEOFDvj%2B57_wg2hO0DKuUYmaTWR47QcRQSPO%2BCeKdsH5wNGHg%40mail.gmail.com.



--
Alexander V. Smal
St. Petersburg Department of Steklov Mathematical Institute
27 Fontanka, St. Petersburg, 191023, Russia