Вторник, 19 июня, 402. Начало в 12:00.
Докладчик: Navid Talebanfard (Institute of Mathematics of the Czech Academy of Sciences).
Тема: Structure in Proof Complexity: The Case of Tseitin and Tree Decompositions.
Abstract
One of the main challenges in proving lower bounds in proof complexity is that we cannot (seemingly) make structural assumptions about the proof and thus our argument should work against any conceivable proof (which may not even exist). I will survey a few results showing that in some cases it is possible to prove structural properties of proofs of specific formulas or minimal proofs of arbitrary formulas. In particular I will give a more direct proof of our result with Galesi and Toran showing that the width of Tseitin formulas is the same in general and regular resolution.
