Пятница 13.07. Д. Соколов: "От доказательств к вычислениям"

Докладчик: 
Д. Соколов
Дата: 
Friday, July 13, 2018 - 13:30
Место: 
203
Аннотация: 

Монотонные Span Programs (mSP) были предложены Карчмером и Вигдерсоном в начале 90-х годов, позднее было
доказано, что они моделируют монотонные булевы формулы. Также известно квазиполиномиальное разделение между
mSP над полем F_2 и монотонными схемами.

Пользуясь недавними теоремами о лифтинге мы покажем, что задача о разделении данных моделей вычислений следует из разделения резолюционной системы доказательств и Nullstellensatz. Мы предъявим экспоненциальное разделение данных систем.