Parameterised Proof Complexity
Seminar Room 1, Newton Institute
AbstractI will start by introducing the basic notion of a parameterised proof as defined by B. Martin, S. Szeider and myself back in 2007, and will discuss a complexity gap theorem theorem for generic parameterisation of tree-like resolution. I will then move onto results that have been obtained since them by various researchers, including parameterised lower bounds for the pigeon-hole principle in resolution and for the maximum clique in random graphs in tree-like resolution. I will conclude with some new results due to B. Martin and myself on parameterised proofs for W as well as with some open problems.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.