Пятница 07.08. Ярослав Алексеев (СПбГУ): "Нижняя оценка для обобщения системы PC и моделирование системы Res-Lin"
PDMI seminars
Тема: Нижняя оценка для обобщения системы PC и моделирование системы Res-Lin
Место: Zoom
Время: 07.08.2020, 11:00
Докладчик: Ярослав Алексеев (СПбГУ)
Abstract:
Мы рассмотрим обобщение системы Polynomial Calculus, в котором дополнительно можно извлекать квадратный корень из многочлена и вводить новые переменные, записывающие многочлены от исходных переменных. Мы докажем экспоненциальную нижнюю оценку на размер опровержения в этой системе равенства $BVP_n$ ($1 + 2 x_1 + 2^2 x_2 + ... + 2^n x_n = 0$), при этом для доказательства нижней оценки на размер доказательства нам не потребуется нижняя оценка на степень. Благодаря тому, что эта система полиномиально моделирует Res-Lin (систему, оперирующую дизъюнкциями линейных уравнений; введена Разом и Цамеретом), мы получим альтернативное доказательство нижней оценки Парта и Цамерета на размер доказательств $BVP_n$ в Res-Lin.
Семинар будет проходить онлайн в конференции zoom. Ссылка для подключения будет выслана в рассылку за пару часов до доклада.
Alexander V. Smal
Ссылка для доклада:
https://us02web.zoom.us/j/8141238054?pwd=Q2RMak9XU2dQSFlZcm5xV3VzZzdPZz09
Саша
> Вы получили это сообщение, поскольку подписаны на группу "spb-complexity".
> Чтобы отменить подписку на эту группу и больше не получать от нее сообщения, отправьте письмо на электронный адрес spb-complexit...@googlegroups.com.
> Чтобы посмотреть обсуждение на веб-странице, перейдите по ссылке https://groups.google.com/d/msgid/spb-complexity/000000000000c5c95605ac24fcb0%40google.com.
--
Alexander V. Smal
St. Petersburg Department of Steklov Mathematical Institute
27 Fontanka, St. Petersburg, 191023, Russia