Пятница 02.10. Пётр Смирнов: "Квазиполиномиальные опровержения цейтинских формул в Cutting Planes"

[PDMI seminars]

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

Тема: Квазиполиномиальные опровержения цейтинских формул в Cutting Planes
Место: Zoom
Время: 02.10.2020, 18:00
Докладчик: Пётр Смирнов

Abstract:
В докладе для любой цейтинской невыполнимой формулы на графе G мы построим опровержение в системе Cutting Planes (CP) длины $2^D (nD)^O(log n)$, где n — число вершин графа G, а D — его максимальная степень.

Опровержение строится следующим образом: мы рассматриваем (построенное ранее в другой работе) квазиполиномиальное опровержение в более сильной системе Stabbing Planes, замечаем структурное свойство этого опровержения, а затем перестраиваем любое опроверждение с таким свойством в систему CP.

Таким образом, этим результатом была опровергнута гипотеза о том, что цейтинские формулы экспоненциально сложны для CP.

Доклад основан на статье Daniel Dadush и Samarth Tiwari «On the Complexity of Branching Proofs» [https://homepages.cwi.nl/~dadush/papers/branching.pdf].

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

[Dmitry M. Itsykson]

Ссылка для семинара: https://us02web.zoom.us/j/8141238054?pwd=Q2RMak9XU2dQSFlZcm5xV3VzZzdPZz09

вт, 29 сент. 2020 г., 11:06 PDMI seminars <pdmi.l...@gmail.com>:

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