Вторник 19.06. Navid Talebanfard (Institute of Mathematics of the Academy of Sciences of the Czech Republic): "Structure in Proof Complexity: The Case of Tseitin and Tree Decompositions"

Докладчик: 
Navid Talebanfard (Institute of Mathematics of the Academy of Sciences of the Czech Republic)
Дата: 
Tuesday, June 19, 2018 - 12:00
Место: 
402
Аннотация: 

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.