Пятница 05.06. Дмитрий Соколов (СПбГУ, ПОМИ): "Нижние оценки на систему AC_0-Frege"

Докладчик: 
Дмитрий Соколов (СПбГУ, ПОМИ)
Дата: 
Friday, June 5, 2020 - 16:00
Место: 
Zoom
Аннотация: 

В этом докладе мы обсудим детали доказательства нижней оценки на систему доказательств AC_0-Frege. Нашей основной целью будет разобраться в технических деталях switching леммы для паросочетаний из классической статьи Urquhart, Fu ``Simplified Lower Bounds for Propositional Proofs''.